All reports by Author Rafael Mendes de Oliveira:

__
TR19-140
| 7th October 2019
__

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson#### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Revisions: 1

__
TR19-019
| 19th February 2019
__

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi#### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

__
TR17-162
| 26th October 2017
__

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson#### Barriers for Rank Methods in Arithmetic Complexity

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR14-157
| 27th November 2014
__

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk#### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

__
TR14-056
| 18th April 2014
__

Zeev Dvir, Rafael Mendes de Oliveira#### Factors of Sparse Polynomials are Sparse

Revisions: 1
,
Comments: 1

__
TR14-003
| 10th January 2014
__

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka#### Testing Equivalence of Polynomials under Shifts

Revisions: 2
,
Comments: 1

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>

Zeev Dvir, Rafael Mendes de Oliveira

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$

has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees

of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ...
more >>>

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>