Michael A. Forbes

According to our database, Michael A. Forbes authored at least 29 papers between 2011 and 2024.

Collaborative distances:

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

2024

Low-Depth Algebraic Circuit Lower Bounds over Any Field.

Michael A. Forbes

Proceedings of the 39th Computational Complexity Conference, 2024

2022

Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals.

Robert Andrews, Michael A. Forbes

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2018

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

Michael A. Forbes, Amir Shpilka, Ben Lee Volk

Theory Comput., 2018

A PSPACE construction of a hitting set for the closure of small algebraic circuits.

Michael A. Forbes, Amir Shpilka

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards Blackbox Identity Testing of Log-Variate Circuits.

Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Pseudorandom Generators for Read-Once Branching Programs, in Any Order.

Michael A. Forbes, Zander Kelley

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Spatial Isolation Implies Zero Knowledge Even in a Quantum World.

Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

A Zero Knowledge Sumcheck and its Applications.

Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2017

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.

Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

Electron. Colloquium Comput. Complex., 2017

Zero Knowledge Protocols from Succinct Constraint Detection.

Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Proceedings of the Theory of Cryptography - 15th International Conference, 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

On Probabilistic Checking in Perfect Zero Knowledge.

Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

Proceedings of the 31st Conference on Computational Complexity, 2016

Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity.

Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi

Proceedings of the 31st Conference on Computational Complexity, 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

Complexity Theory Column 88: Challenges in Polynomial Factorization1.

Michael A. Forbes, Amir Shpilka

SIGACT News, 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

Deterministic Divisibility Testing via Shifted Partial Derivatives.

Michael A. Forbes

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Dimension Expanders via Rank Condensers.

Michael A. Forbes, Venkatesan Guruswami

Proceedings of the Approximation, 2015

2014

Polynomial identity testing of read-once oblivious algebraic branching programs.

Michael A. Forbes

PhD thesis, 2014

On the locality of codeword symbols in non-linear codes.

Michael A. Forbes, Sergey Yekhanin

Discret. Math., 2014

Hitting sets for multilinear read-once algebraic branching programs, in any order.

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Proceedings of the Symposium on Theory of Computing, 2014

2013

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Electron. Colloquium Comput. Complex., 2013

Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs.

Michael A. Forbes, Amir Shpilka

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.

Michael A. Forbes, Amir Shpilka

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

On identity testing of tensors, low-rank recovery and compressed sensing.

Michael A. Forbes, Amir Shpilka

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Improved Soundness for QMA with Multiple Provers.

Alessandro Chiesa, Michael A. Forbes

Electron. Colloquium Comput. Complex., 2011

A Survey of Binary Covering Arrays.

Jim Lawrence, Raghu Kacker, Yu Lei, D. Richard Kuhn, Michael A. Forbes

Electron. J. Comb., 2011

Tensor Rank: Some Lower and Upper Bounds.

Boris Alexeev, Michael A. Forbes, Jacob Tsimerman

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011