We stand with Ukraine  

Michael A. Forbes

Affiliations:
  • University of Illinois at Urbana-Champaign, Department of Computer Science, Champaign, IL, USA
  • University of California, Simons Institute for the Theory of Computing, Berkeley, CA, USA (former)
  • Princeton University, Department of Computer Science, NJ, USA (former)
  • Massachusetts Institute of Technology (MIT), Department of Electrical Engineering and Computer Science, Cambridge, MA, USA (former, PhD 2014)


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Low-Depth Algebraic Circuit Lower Bounds over Any Field.
[BibTeX]
[DOI]
Michael A. Forbes
Proceedings of the 39th Computational Complexity Conference, 2024

2021
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals.
[BibTeX]
[DOI]
Robert Andrews
,
Michael A. Forbes
Electron. Colloquium Comput. Complex., 2021

2018
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
,
Ben Lee Volk
Theory Comput., 2018

Pseudorandom Generators for Read-Once Branching Programs, in any Order.
[BibTeX]
[DOI]
Michael A. Forbes
,
Zander Kelley
Electron. Colloquium Comput. Complex., 2018

Towards blackbox identity testing of log-variate circuits.
[BibTeX]
[DOI]
Michael A. Forbes
,
Sumanta Ghosh
,
Nitin Saxena
Electron. Colloquium Comput. Complex., 2018

Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
[BibTeX]
[DOI]
Alessandro Chiesa
,
Michael A. Forbes
,
Tom Gur
,
Nicholas Spooner
Electron. Colloquium Comput. Complex., 2018

2017
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
,
Ben Lee Volk
Electron. Colloquium Comput. Complex., 2017

A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
Electron. Colloquium Comput. Complex., 2017

A Zero Knowledge Sumcheck and its Applications.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Manindra Agrawal
,
Michael A. Forbes
,
Sumanta Ghosh
,
Nitin Saxena
Electron. Colloquium Comput. Complex., 2017

Zero Knowledge Protocols from Succinct Constraint Detection.
[BibTeX]
[DOI]
Eli Ben-Sasson
,
Alessandro Chiesa
,
Michael A. Forbes
,
Ariel Gabizon
,
Michael Riabzev
,
Nicholas Spooner
Proceedings of the Theory of Cryptography - 15th International Conference, 2017

2016
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
,
Iddo Tzameret
,
Avi Wigderson
Electron. Colloquium Comput. Complex., 2016

Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.
[BibTeX]
[DOI]
Michael A. Forbes
,
Mrinal Kumar
,
Ramprasad Saptharishi
Electron. Colloquium Comput. Complex., 2016

On Probabilistic Checking in Perfect Zero Knowledge.
[BibTeX]
[DOI]
Eli Ben-Sasson
,
Alessandro Chiesa
,
Michael A. Forbes
,
Ariel Gabizon
,
Michael Riabzev
,
Nicholas Spooner
Electron. Colloquium Comput. Complex., 2016

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
SIGACT News, 2015

Identity Testing and Lower Bounds for Read-<i>k</i> Oblivious Algebraic Branching Programs.
[BibTeX]
[DOI]
Matthew Anderson
,
Michael A. Forbes
,
Ramprasad Saptharishi
,
Amir Shpilka
,
Ben Lee Volk
Electron. Colloquium Comput. Complex., 2015

Deterministic Divisibility Testing via Shifted Partial Derivatives.
[BibTeX]
[DOI]
Michael A. Forbes
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Polynomial identity testing of read-once oblivious algebraic branching programs.
[BibTeX]
[DOI]
Michael A. Forbes
PhD thesis, 2014

Dimension Expanders via Rank Condensers.
[BibTeX]
[DOI]
Michael A. Forbes
,
Venkatesan Guruswami
Electron. Colloquium Comput. Complex., 2014

On the locality of codeword symbols in non-linear codes.
[BibTeX]
[DOI]
Michael A. Forbes
,
Sergey Yekhanin
Discret. Math., 2014

Hitting sets for multilinear read-once algebraic branching programs, in any order.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Michael A. Forbes
,
Ramprasad Saptharishi
,
Amir Shpilka
Electron. Colloquium Comput. Complex., 2013

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
Electron. Colloquium Comput. Complex., 2013

Improved Soundness for QMA with Multiple Provers
[BibTeX]
[DOI]
Alessandro Chiesa
,
Michael A. Forbes
Chic. J. Theor. Comput. Sci., 2013

2012
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
Electron. Colloquium Comput. Complex., 2012

2011
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.
[BibTeX]
[DOI]
Michael A. Forbes
,
Amir Shpilka
Electron. Colloquium Comput. Complex., 2011

Tensor Rank: Some Lower and Upper Bounds.
[BibTeX]
[DOI]
Boris Alexeev
,
Michael A. Forbes
,
Jacob Tsimerman
Electron. Colloquium Comput. Complex., 2011

A Survey of Binary Covering Arrays.
[BibTeX]
[DOI]
Jim Lawrence
,
Raghu Kacker
,
Yu Lei
,
D. Richard Kuhn
,
Michael A. Forbes
Electron. J. Comb., 2011


  Loading...