Edward Pyne

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

Collaborative distances:

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

2024

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

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

Algorithmica, October, 2024

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

Jiatu Li, Edward Pyne, Roei Tell

Electron. Colloquium Comput. Complex., 2024

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

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

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

Pseudorandom Linear Codes Are List-Decodable to Capacity.

Aaron (Louie) Putterman, Edward Pyne

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

Derandomizing Logspace with a Small Shared Hard Drive.

Edward Pyne

Proceedings of the 39th Computational Complexity 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