Edward Pyne

55 papers A* 8A 12Misc 1Journal 33Unranked 1
YearRankTypeTitle / Venue / Authors
2026 J jnl
Catalytic Tree Evaluation From Matching Vectors.
CoRR
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
2026 J jnl
Catalytic Tree Evaluation From Matching Vectors.
Electron. Colloquium Comput. Complex.
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
2026 J jnl
Catalytic Tree Evaluation From Matching Vectors.
IACR Cryptol. ePrint Arch.
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
2026 A conf
Efficient Catalytic Graph Algorithms.
ITCS
James Cook, Edward Pyne
2025 A conf
A Fast Coloring Oracle for Average Case Hypergraphs.
APPROX/RANDOM
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025 J jnl
A Fast Coloring Oracle for Average Case Hypergraphs.
CoRR
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025 A conf
Catalytic Communication.
ITCS
Edward Pyne, Nathan S. Sheffield, William Wang
2025 A* conf
Collapsing Catalytic Classes.
FOCS
Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami
2025 J jnl
Collapsing Catalytic Classes.
CoRR
Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami
2025 J jnl
Collapsing Catalytic Classes.
Electron. Colloquium Comput. Complex.
Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami
2025 J jnl
Composing Low-Space Algorithms.
Electron. Colloquium Comput. Complex.
Edward Pyne, Roei Tell
2025 J jnl
Derandomizing Logspace With a Small Shared Hard Drive.
Comput. Complex.
Edward Pyne
2025 J jnl
Efficient Catalytic Graph Algorithms.
CoRR
James Cook, Edward Pyne
2025 A* conf
The Structure of Catalytic Space: Capturing Randomness and Time via Compression.
STOC
James Cook, Jiatu Li, Ian Mertz, Edward Pyne
2025 J jnl
The Structure of In-Place Space-Bounded Computation.
CoRR
James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan S. Sheffield
2025 J jnl
The Structure of In-Place Space-Bounded Computation.
Electron. Colloquium Comput. Complex.
James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan S. Sheffield
2025 J jnl
When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism.
Electron. Colloquium Comput. Complex.
Dean Doron, Edward Pyne, Roei Tell, Ryan Williams
2025 A* conf
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism.
STOC
Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams
2024 J jnl
A Study of Error Reduction Polynomials.
Electron. Colloquium Comput. Complex.
Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz
2024 J jnl
Average-Case Local Computation Algorithms.
CoRR
Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld
2024 J jnl
Catalytic Communication.
Electron. Colloquium Comput. Complex.
Edward Pyne, Nathan S. Sheffield, William Wang
2024 A conf
Derandomizing Logspace with a Small Shared Hard Drive.
CCC
Edward Pyne
2024 A* conf
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness.
FOCS
Jiatu Li, Edward Pyne, Roei Tell
2024 J jnl
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness.
Electron. Colloquium Comput. Complex.
Jiatu Li, Edward Pyne, Roei Tell
2024 J jnl
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.
Algorithmica
William M. Hoza, Edward Pyne, Salil P. Vadhan
2024 A* conf
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL.
STOC
Dean Doron, Edward Pyne, Roei Tell
2024 A conf
Pseudorandom Linear Codes Are List-Decodable to Capacity.
ITCS
Aaron (Louie) Putterman, Edward Pyne
2024 J jnl
The Structure of Catalytic Space: Capturing Randomness and Time via Compression.
Electron. Colloquium Comput. Complex.
James Cook, Jiatu Li, Ian Mertz, Edward Pyne
2023 A* conf
Certified Hardness vs. Randomness for Log-Space.
FOCS
Edward Pyne, Ran Raz, Wei Zhan
2023 J jnl
Certified Hardness vs. Randomness for Log-Space.
CoRR
Edward Pyne, Ran Raz, Wei Zhan
2023 J jnl
Certified Hardness vs. Randomness for Log-Space.
Electron. Colloquium Comput. Complex.
Edward Pyne, Ran Raz, Wei Zhan
2023 A conf
Improved Local Computation Algorithms for Constructing Spanners.
APPROX/RANDOM
Rubi Arviv, Lily Chung, Reut Levi, Edward Pyne
2023 A* conf
Near-Optimal Derandomization of Medium-Width Branching Programs.
STOC
Aaron (Louie) Putterman, Edward Pyne
2023 A conf
On the Power of Regular and Permutation Branching Programs.
APPROX/RANDOM
Chin Ho Lee, Edward Pyne, Salil P. Vadhan
2023 J jnl
On the Power of Regular and Permutation Branching Programs.
Electron. Colloquium Comput. Complex.
Chin Ho Lee, Edward Pyne, Salil P. Vadhan
2023 J jnl
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL.
Electron. Colloquium Comput. Complex.
Dean Doron, Edward Pyne, Roei Tell
2023 J jnl
Pseudorandom Linear Codes are List Decodable to Capacity.
CoRR
Aaron (Louie) Putterman, Edward Pyne
2023 J jnl
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.
CoRR
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
2023 A* conf
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.
FOCS
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
2023 J jnl
Time-Space Tradeoffs for BPL via Catalytic Computation.
Electron. Colloquium Comput. Complex.
Edward Pyne
2022 — conf
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size.
SOSA
Edward Pyne, Salil P. Vadhan
2022 A conf
Fourier Growth of Regular Branching Programs.
APPROX/RANDOM
Chin Ho Lee, Edward Pyne, Salil P. Vadhan
2022 J jnl
Fourier Growth of Regular Branching Programs.
Electron. Colloquium Comput. Complex.
Chin Ho Lee, Edward Pyne, Salil P. Vadhan
2022 A conf
Hitting Sets for Regular Branching Programs.
CCC
Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne
2022 A conf
Local Access to Random Walks.
ITCS
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
2022 J jnl
Near-Optimal Derandomization of Medium-Width Branching Programs.
Electron. Colloquium Comput. Complex.
Aaron (Louie) Putterman, Edward Pyne
2021 J jnl
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size.
CoRR
Edward Pyne, Salil P. Vadhan
2021 J jnl
Hitting Sets For Regular Branching Programs.
Electron. Colloquium Comput. Complex.
Edward Pyne
2021 Misc conf
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.
COCOON
Edward Pyne, Salil P. Vadhan
2021 J jnl
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs.
Electron. Colloquium Comput. Complex.
Edward Pyne, Salil P. Vadhan
2021 J jnl
Local Access to Random Walks.
CoRR
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
2021 A conf
Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract).
CCC
Edward Pyne, Salil P. Vadhan
2021 J jnl
Pseudodistributions That Beat All Pseudorandom Generators.
Electron. Colloquium Comput. Complex.
Edward Pyne, Salil P. Vadhan
2021 A conf
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.
ITCS
William M. Hoza, Edward Pyne, Salil P. Vadhan
2020 J jnl
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs.
Electron. Colloquium Comput. Complex.
William Hoza, Edward Pyne, Salil P. Vadhan