Michael A. Forbes

67 papers A* 10A 5Journal 48Unranked 3
YearRankTypeTitle / Venue / Authors
2024 A conf
Low-Depth Algebraic Circuit Lower Bounds over Any Field.
CCC
Michael A. Forbes
2022 A* conf
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals.
STOC
Robert Andrews, Michael A. Forbes
2022 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
J. ACM
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2021 J jnl
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals.
CoRR
Robert Andrews, Michael A. Forbes
2021 J jnl
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals.
Electron. Colloquium Comput. Complex.
Robert Andrews, Michael A. Forbes
2021 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Theory Comput.
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2018 A* conf
A PSPACE construction of a hitting set for the closure of small algebraic circuits.
STOC
Michael A. Forbes, Amir Shpilka
2018 J jnl
Identity Testing and Lower Bounds for Read-
ACM Trans. Comput. Theory
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2018 A* conf
Pseudorandom Generators for Read-Once Branching Programs, in Any Order.
FOCS
Michael A. Forbes, Zander Kelley
2018 J jnl
Pseudorandom Generators for Read-Once Branching Programs, in any Order.
CoRR
Michael A. Forbes, Zander Kelley
2018 J jnl
Pseudorandom Generators for Read-Once Branching Programs, in any Order.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Zander Kelley
2018 A* conf
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
FOCS
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
CoRR
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits.
Theory Comput.
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2018 A* conf
Towards Blackbox Identity Testing of Log-Variate Circuits.
ICALP
Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
2018 J jnl
Towards blackbox identity testing of log-variate circuits.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
2017 J jnl
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.
CoRR
Michael A. Forbes, Amir Shpilka
2017 J jnl
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2017 J jnl
A Zero Knowledge Sumcheck and its Applications.
CoRR
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
2017 J jnl
A Zero Knowledge Sumcheck and its Applications.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
2017 J jnl
A Zero Knowledge Sumcheck and its Applications.
IACR Cryptol. ePrint Arch.
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
2017 J jnl
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.
CoRR
Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
2017 J jnl
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
2017 J jnl
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds.
CoRR
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 J jnl
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 A* conf
Succinct hitting sets and barriers to proving algebraic circuits lower bounds.
STOC
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
2017 — conf
Zero Knowledge Protocols from Succinct Constraint Detection.
TCC (2)
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
2016 A conf
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity.
CCC
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
2016 J jnl
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.
CoRR
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
2016 J jnl
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
2016 A conf
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.
CCC
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2016 J jnl
On Probabilistic Checking in Perfect Zero Knowledge.
CoRR
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
2016 J jnl
On Probabilistic Checking in Perfect Zero Knowledge.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
2016 J jnl
On Probabilistic Checking in Perfect Zero Knowledge.
IACR Cryptol. ePrint Arch.
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
2016 A conf
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
CCC
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
CoRR
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2016 J jnl
Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
2015 J jnl
Complexity Theory Column 88: Challenges in Polynomial Factorization1.
SIGACT News
Michael A. Forbes, Amir Shpilka
2015 A* conf
Deterministic Divisibility Testing via Shifted Partial Derivatives.
FOCS
Michael A. Forbes
2015 — conf
Dimension Expanders via Rank Condensers.
APPROX-RANDOM
Michael A. Forbes, Venkatesan Guruswami
2015 J jnl
Identity Testing and Lower Bounds for Read-
Electron. Colloquium Comput. Complex.
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2015 J jnl
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs.
CoRR
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
2014 J jnl
Dimension Expanders via Rank Condensers.
CoRR
Michael A. Forbes, Venkatesan Guruswami
2014 J jnl
Dimension Expanders via Rank Condensers.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Venkatesan Guruswami
2014 A* conf
Hitting sets for multilinear read-once algebraic branching programs, in any order.
STOC
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2014 J jnl
On the locality of codeword symbols in non-linear codes.
Discret. Math.
Michael A. Forbes, Sergey Yekhanin
2014 — —
Polynomial identity testing of read-once oblivious algebraic branching programs.
Michael A. Forbes
2013 J jnl
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
CoRR
Michael A. Forbes, Amir Shpilka
2013 — conf
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.
APPROX-RANDOM
Michael A. Forbes, Amir Shpilka
2013 J jnl
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2013 J jnl
Improved Soundness for QMA with Multiple Provers
Chic. J. Theor. Comput. Sci.
Alessandro Chiesa, Michael A. Forbes
2013 J jnl
On the Locality of Codeword Symbols in Non-Linear Codes
CoRR
Michael A. Forbes, Sergey Yekhanin
2013 J jnl
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.
CoRR
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2013 J jnl
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka
2013 A* conf
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs.
FOCS
Michael A. Forbes, Amir Shpilka
2012 A* conf
On identity testing of tensors, low-rank recovery and compressed sensing.
STOC
Michael A. Forbes, Amir Shpilka
2012 J jnl
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
CoRR
Michael A. Forbes, Amir Shpilka
2012 J jnl
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2011 J jnl
A Survey of Binary Covering Arrays.
Electron. J. Comb.
Jim Lawrence, Raghu Kacker, Yu Lei, D. Richard Kuhn, Michael A. Forbes
2011 J jnl
Improved Soundness for QMA with Multiple Provers
CoRR
Alessandro Chiesa, Michael A. Forbes
2011 J jnl
Improved Soundness for QMA with Multiple Provers.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Michael A. Forbes
2011 J jnl
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
CoRR
Michael A. Forbes, Amir Shpilka
2011 J jnl
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.
Electron. Colloquium Comput. Complex.
Michael A. Forbes, Amir Shpilka
2011 J jnl
Tensor Rank: Some Lower and Upper Bounds
CoRR
Boris Alexeev, Michael A. Forbes, Jacob Tsimerman
2011 A conf
Tensor Rank: Some Lower and Upper Bounds.
CCC
Boris Alexeev, Michael A. Forbes, Jacob Tsimerman
2011 J jnl
Tensor Rank: Some Lower and Upper Bounds.
Electron. Colloquium Comput. Complex.
Boris Alexeev, Michael A. Forbes, Jacob Tsimerman