Edward Pyne

According to our database, Edward Pyne authored at least 30 papers between 2021 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

The Structure of In-Place Space-Bounded Computation.

James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan S. Sheffield

CoRR, October, 2025

Efficient Catalytic Graph Algorithms.

James Cook, Edward Pyne

CoRR, September, 2025

Collapsing Catalytic Classes.

Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami

Electron. Colloquium Comput. Complex., 2025

When Connectivity Is Hard, Random Walks Are Easy with Non-determinism.

Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

The Structure of Catalytic Space: Capturing Randomness and Time via Compression.

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Catalytic Communication.

Edward Pyne, Nathan S. Sheffield, William Wang

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

A Fast Coloring Oracle for Average Case Hypergraphs.

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

Proceedings of the Approximation, 2025

2024

Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.

William M. Hoza, Edward Pyne, Salil P. Vadhan

Algorithmica, October, 2024

A Study of Error Reduction Polynomials.

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

Electron. Colloquium Comput. Complex., 2024

Average-Case Local Computation Algorithms.

Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld

CoRR, 2024

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL.

Dean Doron, Edward Pyne, Roei Tell

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Pseudorandom Linear Codes Are List-Decodable to Capacity.

Aaron (Louie) Putterman, Edward Pyne

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness.

Jiatu Li, Edward Pyne, Roei Tell

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Derandomizing Logspace with a Small Shared Hard Drive.

Edward Pyne

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Time-Space Tradeoffs for BPL via Catalytic Computation.

Edward Pyne

Electron. Colloquium Comput. Complex., 2023

Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.

AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan

CoRR, 2023

Near-Optimal Derandomization of Medium-Width Branching Programs.

Aaron (Louie) Putterman, Edward Pyne

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Certified Hardness vs. Randomness for Log-Space.

Edward Pyne, Ran Raz, Wei Zhan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.

AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

On the Power of Regular and Permutation Branching Programs.

Chin Ho Lee, Edward Pyne, Salil P. Vadhan

Proceedings of the Approximation, 2023

Improved Local Computation Algorithms for Constructing Spanners.

Rubi Arviv, Lily Chung, Reut Levi, Edward Pyne

Proceedings of the Approximation, 2023

2022

Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size.

Edward Pyne, Salil P. Vadhan

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Local Access to Random Walks.

Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Hitting Sets for Regular Branching Programs.

Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne

Proceedings of the 37th Computational Complexity Conference, 2022

Fourier Growth of Regular Branching Programs.

Chin Ho Lee, Edward Pyne, Salil P. Vadhan

Proceedings of the Approximation, 2022

2021

Pseudodistributions That Beat All Pseudorandom Generators.

Edward Pyne, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2021

Hitting Sets For Regular Branching Programs.

Edward Pyne

Electron. Colloquium Comput. Complex., 2021

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.

William M. Hoza, Edward Pyne, Salil P. Vadhan

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.

Edward Pyne, Salil P. Vadhan

Proceedings of the Computing and Combinatorics - 27th International Conference, 2021

Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract).

Edward Pyne, Salil P. Vadhan

Proceedings of the 36th Computational Complexity Conference, 2021