Ben lee Volk

According to our database, Ben lee Volk authored at least 33 papers between 2013 and 2025.

Collaborative distances:

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

2025

On Deterministically Finding an Element of High Order Modulo a Composite.

Ziv Oznovich, Ben Lee Volk

CoRR, June, 2025

2024

SIGACT News Complexity Theory Column 123.

Ben Lee Volk

SIGACT News, December, 2024

SIGACT News Complexity Theory Column.

Ben Lee Volk

SIGACT News, September, 2024

SIGACT News Complexity Theory Column 121.

Ben Lee Volk

SIGACT News, June, 2024

SIGACT News Complexity Theory Column 120.

Ben Lee Volk

SIGACT News, March, 2024

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits.

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2024

Tensor Reconstruction Beyond Constant Rank.

Shir Peleg, Amir Shpilka, Ben Lee Volk

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

Determinants vs. Algebraic Branching Programs.

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

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

Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields.

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

Proceedings of the Approximation, 2024

2023

SIGACT News Complexity Theory Column 119.

Ben Lee Volk

SIGACT News, December, 2023

SIGACT News Complexity Theory Column 118.

Ben Lee Volk

SIGACT News, 2023

Extractors for Images of Varieties.

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

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

2022

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

Comput. Complex., 2022

Lower Bounds on Stabilizer Rank.

Shir Peleg, Ben Lee Volk, Amir Shpilka

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

2021

Guest Column: Algebraic Natural Proofs Ben Lee Volk.

Ben Lee Volk

SIGACT News, 2021

A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits.

Mrinal Kumar, Ben Lee Volk

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

A Lower Bound on Determinantal Complexity.

Mrinal Kumar, Ben Lee Volk

Proceedings of the 36th Computational Complexity Conference, 2021

2020

A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits.

Mrinal Kumar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2020

A Quadratic Lower Bound for Algebraic Branching Programs.

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

Proceedings of the 35th Computational Complexity Conference, 2020

Lower Bounds for Matrix Factorization.

Mrinal Kumar, Ben Lee Volk

Proceedings of the 35th Computational Complexity Conference, 2020

2018

Identity Testing and Lower Bounds in Arithmetic Complexity

Ben Lee Volk

PhD thesis, 2018

Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Theory Comput., 2018

Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.

Noga Alon, Mrinal Kumar, Ben Lee Volk

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.

Mrinal Kumar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2017

Pseudorandom Bits for Oblivious Branching Programs.

Rohit Gurjar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2017

Succinct hitting sets and barriers to proving algebraic circuits lower bounds.

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Efficiently decoding Reed-Muller codes from random errors.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Identity Testing and Lower Bounds for Read-<i>k</i> Oblivious Algebraic Branching Programs.

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2015

Decoding high rate Reed-Muller codes from random errors in near linear time.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

CoRR, 2015

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.

Rafael Oliveira, Amir Shpilka, Ben Lee Volk

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

On the structure of boolean functions with small spectral norm.

Amir Shpilka, Avishay Tal, Ben lee Volk

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

On the Structure of Boolean Functions with Small Spectral Norm.

Amir Shpilka, Ben lee Volk

Electron. Colloquium Comput. Complex., 2013