default search action
Michael A. Forbes 0001
Person information
- affiliation: University of Illinois at Urbana-Champaign, Department of Computer Science, Champaign, IL, USA
- affiliation (former): University of California, Simons Institute for the Theory of Computing, Berkeley, CA, USA
- affiliation (former): Princeton University, Department of Computer Science, NJ, USA
- affiliation (former, PhD 2014): Massachusetts Institute of Technology (MIT), Department of Electrical Engineering and Computer Science, Cambridge, MA, USA
Other persons with the same name
- Michael A. Forbes 0002
— University of Queensland, School of Mechanical and Mining Engineering, Brisbane, QLD, Australia
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c18]Michael A. Forbes:
Low-Depth Algebraic Circuit Lower Bounds over Any Field. CCC 2024: 31:1-31:16 - 2022
- [j8]Alessandro Chiesa
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. J. ACM 69(2): 15:1-15:44 (2022) - [c17]Robert Andrews, Michael A. Forbes:
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals. STOC 2022: 389-402 - 2021
- [j7]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Adv. Math. Commun. 17: 1-88 (2021) - [i40]Robert Andrews, Michael A. Forbes:
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals. CoRR abs/2112.00792 (2021) - [i39]Robert Andrews, Michael A. Forbes:
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals. Electron. Colloquium Comput. Complex. TR21 (2021)
2010 – 2019
- 2018
- [j6]Michael A. Forbes, Amir Shpilka
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory Comput. 14(1): 1-45 (2018) - [j5]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. ACM Trans. Comput. Theory 10(1): 3:1-3:30 (2018) - [c16]Alessandro Chiesa, Michael A. Forbes, Tom Gur
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. FOCS 2018: 755-765 - [c15]Michael A. Forbes, Zander Kelley:
Pseudorandom Generators for Read-Once Branching Programs, in Any Order. FOCS 2018: 946-955 - [c14]Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Towards Blackbox Identity Testing of Log-Variate Circuits. ICALP 2018: 54:1-54:16 - [c13]Michael A. Forbes, Amir Shpilka
A PSPACE construction of a hitting set for the closure of small algebraic circuits. STOC 2018: 1180-1192 - [i38]Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. CoRR abs/1803.01519 (2018) - [i37]Michael A. Forbes, Zander Kelley:
Pseudorandom Generators for Read-Once Branching Programs, in any Order. CoRR abs/1808.06265 (2018) - [i36]Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. Electron. Colloquium Comput. Complex. TR18 (2018) - [i35]Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Towards blackbox identity testing of log-variate circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - [i34]Michael A. Forbes, Zander Kelley:
Pseudorandom Generators for Read-Once Branching Programs, in any Order. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c12]Michael A. Forbes, Amir Shpilka
Succinct hitting sets and barriers to proving algebraic circuits lower bounds. STOC 2017: 653-664 - [c11]Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
Zero Knowledge Protocols from Succinct Constraint Detection. TCC (2) 2017: 172-206 - [i33]Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. CoRR abs/1701.05328 (2017) - [i32]Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. CoRR abs/1702.07180 (2017) - [i31]Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:
A Zero Knowledge Sumcheck and its Applications. CoRR abs/1704.02086 (2017) - [i30]Michael A. Forbes, Amir Shpilka:
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. CoRR abs/1712.09967 (2017) - [i29]Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. Electron. Colloquium Comput. Complex. TR17 (2017) - [i28]Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:
A Zero Knowledge Sumcheck and its Applications. Electron. Colloquium Comput. Complex. TR17 (2017) - [i27]Michael A. Forbes, Amir Shpilka:
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. Electron. Colloquium Comput. Complex. TR17 (2017) - [i26]Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - [i25]Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:
A Zero Knowledge Sumcheck and its Applications. IACR Cryptol. ePrint Arch. 2017: 305 (2017) - 2016
- [c10]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. CCC 2016: 30:1-30:25 - [c9]Michael A. Forbes, Amir Shpilka
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CCC 2016: 32:1-32:17 - [c8]Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. CCC 2016: 33:1-33:19 - [i24]Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. CoRR abs/1605.04207 (2016) - [i23]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR abs/1606.05050 (2016) - [i22]Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
On Probabilistic Checking in Perfect Zero Knowledge. CoRR abs/1610.03798 (2016) - [i21]Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
On Probabilistic Checking in Perfect Zero Knowledge. Electron. Colloquium Comput. Complex. TR16 (2016) - [i20]Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - [i19]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - [i18]Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
On Probabilistic Checking in Perfect Zero Knowledge. IACR Cryptol. ePrint Arch. 2016: 988 (2016) - 2015
- [j4]Michael A. Forbes, Amir Shpilka
Complexity Theory Column 88: Challenges in Polynomial Factorization1. SIGACT News 46(4): 32-49 (2015) - [c7]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. APPROX-RANDOM 2015: 800-814 - [c6]Michael A. Forbes:
Deterministic Divisibility Testing via Shifted Partial Derivatives. FOCS 2015: 451-465 - [i17]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs. CoRR abs/1511.07136 (2015) - [i16]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [b1]Michael A. Forbes:
Polynomial identity testing of read-once oblivious algebraic branching programs. Massachusetts Institute of Technology, Cambridge, MA, USA, 2014 - [j3]Michael A. Forbes, Sergey Yekhanin:
On the locality of codeword symbols in non-linear codes. Discret. Math. 324: 78-84 (2014) - [c5]Michael A. Forbes, Ramprasad Saptharishi
Hitting sets for multilinear read-once algebraic branching programs, in any order. STOC 2014: 867-875 - [i15]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. CoRR abs/1411.7455 (2014) - [i14]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j2]Alessandro Chiesa, Michael A. Forbes:
Improved Soundness for QMA with Multiple Provers. Chic. J. Theor. Comput. Sci. 2013 (2013) - [c4]Michael A. Forbes, Amir Shpilka
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. APPROX-RANDOM 2013: 527-542 - [c3]Michael A. Forbes, Amir Shpilka
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. FOCS 2013: 243-252 - [i13]Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. CoRR abs/1303.0084 (2013) - [i12]Michael A. Forbes, Sergey Yekhanin:
On the Locality of Codeword Symbols in Non-Linear Codes. CoRR abs/1303.3921 (2013) - [i11]Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. CoRR abs/1309.5668 (2013) - [i10]Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - [i9]Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c2]Michael A. Forbes, Amir Shpilka
On identity testing of tensors, low-rank recovery and compressed sensing. STOC 2012: 163-172 - [i8]Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. CoRR abs/1209.2408 (2012) - [i7]Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j1]Jim Lawrence, Raghu Kacker, Yu Lei, D. Richard Kuhn, Michael A. Forbes:
A Survey of Binary Covering Arrays. Electron. J. Comb. 18(1) (2011) - [c1]Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
Tensor Rank: Some Lower and Upper Bounds. CCC 2011: 283-291 - [i6]Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
Tensor Rank: Some Lower and Upper Bounds. CoRR abs/1102.0072 (2011) - [i5]Alessandro Chiesa, Michael A. Forbes:
Improved Soundness for QMA with Multiple Provers. CoRR abs/1108.2098 (2011) - [i4]Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. CoRR abs/1111.0663 (2011) - [i3]Boris Alexeev, Michael A. Forbes, Jacob Tsimerman:
Tensor Rank: Some Lower and Upper Bounds. Electron. Colloquium Comput. Complex. TR11 (2011) - [i2]Alessandro Chiesa, Michael A. Forbes:
Improved Soundness for QMA with Multiple Provers. Electron. Colloquium Comput. Complex. TR11 (2011) - [i1]Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. Electron. Colloquium Comput. Complex. TR11 (2011)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-12 21:55 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: