Michael A Forbes

If you made any changes in Pure these will be visible here soon.

Research Output

  • 15 Conference contribution
  • 5 Article
Filter
Conference contribution
2018

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

Forbes, M. A. & Shpilka, A., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 87-99 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Pseudorandom generators for read-once branching programs, in any order

Forbes, M. A. & Kelley, Z., Nov 30 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 946-955 10 p. 8555171. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Spatial isolation implies zero knowledge even in a quantum world

Chiesa, A., Forbes, M. A., Gur, T. & Spooner, N., Nov 30 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 755-765 11 p. 8555155. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Towards blackbox identity testing of log-variate circuits

Forbes, M. A., Ghosh, S. & Saxena, N., Jul 1 2018, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Kaklamanis, C., Marx, D., Chatzigiannakis, I. & Sannella, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 54. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 107).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2017

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

Forbes, M. A., Shpilka, A. & Volk, B. L., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 653-664 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zero knowledge protocols from succinct constraint detection

Ben-Sasson, E., Chiesa, A., Forbes, M. A., Gabizon, A., Riabzev, M. & Spooner, N., Jan 1 2017, Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings. Kalai, Y. & Reyzin, L. (eds.). Springer-Verlag, p. 172-206 35 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10678 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2016

Identity testing and lower bounds for read-k oblivious algebraic branching programs

Anderson, M., Forbes, M. A., Saptharishi, R., Shpilka, A. & Volk, B. L., May 1 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 30:1-30:25 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Proof complexity lower bounds from algebraic circuit complexity

Forbes, M. A., Shpilka, A., Tzameret, I. & Wigderson, A., May 1 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 32:1-32:17 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2015

Deterministic Divisibility Testing via Shifted Partial Derivatives

Forbes, M. A., Dec 11 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, Vol. 2015-December. p. 451-465 15 p. 7354409

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Dimension expanders via rank condensers

Forbes, M. A. & Guruswami, V., Aug 1 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Garg, N., Jansen, K., Rao, A. & Rolim, J. D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 800-814 15 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 40).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2014

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

Forbes, M. A., Saptharishi, R. & Shpilka, A., Jan 1 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 867-875 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2013

Explicit Noether normalization for simultaneous conjugation via polynomial identity testing

Forbes, M. A. & Shpilka, A., Oct 15 2013, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. p. 527-542 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8096 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs

Forbes, M. A. & Shpilka, A., Dec 1 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 243-252 10 p. 6686160. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2012

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

Forbes, M. A. & Shpilka, A., Jun 26 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 163-171 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2011

Tensor rank: Some lower and upper bounds

Alexeev, B., Forbes, M. A. & Tsimerman, J., Aug 29 2011, Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. p. 283-291 9 p. 5959837. (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceedingConference contribution