All reports by Author Michael Forbes:

__
TR21-172
| 1st December 2021
__

Robert Andrews, Michael Forbes#### Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals

__
TR18-147
| 19th August 2018
__

Michael Forbes, Zander Kelley#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

__
TR18-036
| 21st February 2018
__

Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Towards blackbox identity testing of log-variate circuits

__
TR17-163
| 2nd November 2017
__

Michael Forbes, Amir Shpilka#### A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits

__
TR17-057
| 7th April 2017
__

Alessandro Chiesa, Michael Forbes, Nicholas Spooner#### A Zero Knowledge Sumcheck and its Applications

__
TR17-035
| 23rd February 2017
__

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

__
TR17-007
| 19th January 2017
__

Michael Forbes, Amir Shpilka, Ben Lee Volk#### Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

Revisions: 1

__
TR16-156
| 12th October 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

__
TR16-098
| 16th June 2016
__

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson#### Proof Complexity Lower Bounds from Algebraic Circuit Complexity

__
TR16-045
| 22nd March 2016
__

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi#### Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

__
TR15-184
| 21st November 2015
__

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk#### Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

__
TR14-162
| 28th November 2014
__

Michael Forbes, Venkatesan Guruswami#### Dimension Expanders via Rank Condensers

__
TR13-132
| 23rd September 2013
__

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka#### Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

__
TR13-033
| 1st March 2013
__

Michael Forbes, Amir Shpilka#### Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

__
TR12-115
| 11th September 2012
__

Michael Forbes, Amir Shpilka#### Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

__
TR11-147
| 2nd November 2011
__

Michael Forbes, Amir Shpilka#### On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

__
TR11-110
| 10th August 2011
__

Alessandro Chiesa, Michael Forbes#### Improved Soundness for QMA with Multiple Provers

Revisions: 1

__
TR11-010
| 1st February 2011
__

Boris Alexeev, Michael Forbes, Jacob Tsimerman#### Tensor Rank: Some Lower and Upper Bounds

Robert Andrews, Michael Forbes

We show that any nonzero polynomial in the ideal generated by the $r \times r$ minors of an $n \times n$ matrix $X$ can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial $f$ in this ideal, we construct a small depth-three $f$-oracle circuit that approximates the ... more >>>

Michael Forbes, Zander Kelley

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

Michael Forbes, Sumanta Ghosh, Nitin Saxena

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

Michael Forbes, Amir Shpilka

In this paper we study the complexity of constructing a hitting set for $\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>>

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>

Michael Forbes, Amir Shpilka, Ben Lee Volk

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

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

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ...
more >>>

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).

In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ...
more >>>

Michael Forbes, Venkatesan Guruswami

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>

Michael Forbes, Amir Shpilka

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

Michael Forbes, Amir Shpilka

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

Michael Forbes, Amir Shpilka

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

Alessandro Chiesa, Michael Forbes

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ...
more >>>

Boris Alexeev, Michael Forbes, Jacob Tsimerman

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>