Ben Lee Volk

❮ ❯

Research Interests

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

Publications

• Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
  Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Ben Lee Volk
  Manuscript
• Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
  Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk
  Manuscript
• Determinants vs. Algebraic Branching Programs
  Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk
  ITCS 2024
• Tensor Reconstruction Beyond Constant Rank
  Shir Peleg, Amir Shpilka, and Ben Lee Volk
  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)

Teaching

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

Professional Service

• Program Committees: STOC 2023
• Editor for the SICOMP Special Issue for STOC 2023
• Editor for the complexity column of SIGACT News

Academic Background

• (2020-2021) postdoc at the UT Austin CS department, hosted by Dana Moshkovitz and David Zuckerman
• (2018-2020) CMI postdoc at Caltech, hosted by Chris Umans
• (2014-2018) Ph.D. student at the Theory of Computation group at Tel Aviv University, advised by Amir Shpilka.

Name guide: My first name is Ben Lee and my last name is Volk. But it's OK, nobody gets it right the first time. If you call me Ben, I will answer without correcting you and not make a big deal out of it. If you spell it as Ben Lee Volk in your *.bib file (with this exact order and capitalization), BibTeX will correctly infer the first and last names. To read a whole lot more about how BibTeX processes names, see this paper, which is also likely to fulfill your lifelong dream of reading a document that contains the phrase "First von Last".