Edward Pyne

According to our database, Edward Pyne authored at least 19 papers between 2020 and 2024.

Collaborative distances:

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

2024

Average-Case Local Computation Algorithms.

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

CoRR, 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

2023

Certified Hardness vs. Randomness for Log-Space.

Edward Pyne, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2023

Time-Space Tradeoffs for BPL via Catalytic Computation.

Edward Pyne

Electron. Colloquium Comput. Complex., 2023

On the Power of Regular and Permutation Branching Programs.

Chin Ho Lee, Edward Pyne, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2023

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

Dean Doron, Edward Pyne, Roei Tell

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

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

Improved Local Computation Algorithms for Constructing Spanners.

Rubi Arviv, Lily Chung, Reut Levi, Edward Pyne

Proceedings of the Approximation, 2023

2022

Near-Optimal Derandomization of Medium-Width Branching Programs.

Aaron (Louie) Putterman, Edward Pyne

Electron. Colloquium Comput. Complex., 2022

Fourier Growth of Regular Branching Programs.

Chin Ho Lee, Edward Pyne, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 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

2021

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

Edward Pyne, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 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

Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract).

Edward Pyne, Salil P. Vadhan

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.

William Hoza, Edward Pyne, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2020