Ben Lee Volk

Research Interests

Computational complexity theory, and in particular algebraic complexity, algorithms for algebraic problems, error correcting codes and pseudorandomness.

Publications

• A Lower Bound for Read-Once Parity Branching Programs
  Ben Lee Volk
  Manuscript
• On Deterministically Finding an Element of High Order Modulo a Composite
  Ziv Oznovich and Ben Lee Volk
  SODA 2026
• Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
  Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Ben Lee Volk
  ACM TOCT, 2026
• Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
  Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk
  RANDOM 2024
• Determinants vs. Algebraic Branching Programs
  Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk
  computational complexity, 2024 (preliminary version in ITCS 2024)
• Tensor Reconstruction Beyond Constant Rank
  Shir Peleg, Amir Shpilka, and Ben Lee Volk
  To appear in computational complexity (preliminary version in ITCS 2024)
• Extractors for Images of Varieties
  Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman
  STOC 2023
• Algebraic Natural Proofs
  Ben Lee Volk
  SIGACT News Complexity Column, December 2021 (publisher's version)
• Lower Bounds on Stabilizer Rank
  Shir Peleg, Amir Shpilka, and Ben Lee Volk
  Quantum 2022 (preliminary versions in ITCS 2022 and QIP 2022)
• A Lower Bound on Determinantal Complexity
  Mrinal Kumar and Ben Lee Volk
  computational complexity, 2022 (preliminary version in CCC 2021)
  (video from CCC)
• A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits
  Mrinal Kumar and Ben Lee Volk
  ACM TOCT, 2022 (preliminary version in ITCS 2021)
  (video from ITCS)
• Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
  Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk
  computational complexity, 2022 (An earlier version, titled "A Quadratic Lower bound for Algebraic Branching Programs", appeared in CCC 2020)
• Lower Bounds for Matrix Factorization
  Mrinal Kumar and Ben Lee Volk
  computational complexity, 2021 (preliminary version in CCC 2020)
  (video from CCC)
• Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
  Noga Alon, Mrinal Kumar, and Ben Lee Volk
  Combinatorica, 2020 (preliminary version in CCC 2018)
• Pseudorandom Bits for Oblivious Branching Programs
  Rohit Gurjar and Ben Lee Volk
  ACM TOCT, 2020
• Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
  Michael A. Forbes, Amir Shpilka, and Ben Lee Volk
  Theory of Computing, 2018 (preliminary version in STOC 2017)
• Identity Testing and Lower Bounds for Read-𝑘 Oblivious Algebraic Branching Programs
  Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk
  ACM TOCT, 2018 (preliminary version in CCC 2016)
  (video and slides from WACT 2016 at Tel Aviv University)
• Efficiently decoding Reed-Muller codes from random errors
  Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk
  IEEE TIT, 2017 (preliminary version in STOC 2016)
  (a short video of a talk given at Tel Aviv University, and expanded slides)
• Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
  Rafael Oliveira, Amir Shpilka, and Ben Lee Volk
  computational complexity, 2016 (preliminary version in CCC 2015)
  (slides)
• On The Structure of Boolean Functions with Small Spectral Norm
  Amir Shpilka, Avishay Tal, and Ben Lee Volk
  computational complexity, 2017 (preliminary version in ITCS 2014)
  (video and slides of a lecture given at the Simons Institute, and another set of video and slides of a related lecture)

Postdocs and Graduate Students

• Ziv Oznovich
  M.Sc., Graduated 2025
• Anamay Tengse
  Postdoc, 2023-2024

Teaching

• Advanced Algorithms
  Spring 2023, Spring 2024, Spring 2025, Spring 2026
• Complexity Theory
  Winter 2022-2023, Winter 2023-2024, Winter 2024-2025, Winter 2025-2026
• Data Structures
  Spring 2022
• Algebraic Computation and Algorithms
  Winter 2021-2022, Spring 2024
  Lecture notes (in Hebrew, probably contain some errors!)

Professional Service

• Editor of the complexity column of SIGACT News
  (2023 - Present)
• Program Committees
  STOC 2023, STOC 2027
• Editor of the SICOMP Special Issue
  STOC 2023

Academic Background

• Faculty at the Efi Arazi School of Computer Science, Reichman University
  2021-Present
• Postdoc at the Department of Computer Science, UT Austin, hosted by Dana Moshkovitz and David Zuckerman
  2020-2021
• CMI postdoc at Caltech, hosted by Chris Umans
  2018-2020
• Ph.D. student at Theory of Computation group at the School of Computer Science, Tel Aviv University, advised by Amir Shpilka
  2014-2018