Ben lee Volk

Comput. Complex., December, 2024

SIGACT News Complexity Theory Column.

[BibT_eX]

[DOI]

SIGACT News, September, 2024

SIGACT News Complexity Theory Column 121.

[BibT_eX]

[DOI]

SIGACT News, June, 2024

SIGACT News Complexity Theory Column 120.

[BibT_eX]

[DOI]

SIGACT News, March, 2024

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

[BibT_eX]

[DOI]

Ashish Dwivedi

Zeyu Guo

Electron. Colloquium Comput. Complex., 2024

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

[BibT_eX]

[DOI]

Varun Ramanathan

Electron. Colloquium Comput. Complex., 2024

2023

SIGACT News Complexity Theory Column 119.

[BibT_eX]

[DOI]

SIGACT News, December, 2023

SIGACT News Complexity Theory Column 118.

[BibT_eX]

[DOI]

SIGACT News, 2023

2022

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2022

Lower Bounds on Stabilizer Rank.

[BibT_eX]

[DOI]

Shir Peleg

Quantum, 2022

Tensor Reconstruction Beyond Constant Rank.

[BibT_eX]

[DOI]

Shir Peleg

Electron. Colloquium Comput. Complex., 2022

Extractors for Images of Varieties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A Lower Bound on Determinantal Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 2022

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.

[BibT_eX]

[DOI]

Comput. Complex., 2022

2021

Guest Column: Algebraic Natural Proofs Ben Lee Volk.

[BibT_eX]

[DOI]

SIGACT News, 2021

Lower Bounds for Matrix Factorization.

[BibT_eX]

[DOI]

Comput. Complex., 2021

2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Noga Alon

Comb., 2020

2019

A Quadratic Lower Bound for Algebraic Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

Identity Testing and Lower Bounds in Arithmetic Complexity

[BibT_eX]

[DOI]

PhD thesis, 2018

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

[BibT_eX]

[DOI]

Theory Comput., 2018

2017

Efficiently Decoding Reed-Muller Codes From Random Errors.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2017

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Pseudorandom Bits for Oblivious Branching Programs.

[BibT_eX]

[DOI]

Rohit Gurjar

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On the Structure of Boolean Functions with Small Spectral Norm.

[BibT_eX]

[DOI]

Avishay Tal

Ben lee Volk

Comput. Complex., 2017

2016

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas.

[BibT_eX]

[DOI]

Rafael Oliveira

Ben lee Volk

Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Matthew Anderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

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

[BibT_eX]

[DOI]

Matthew Anderson

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

2013

On the Structure of Boolean Functions with Small Spectral Norm.

[BibT_eX]

[DOI]