Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rafael Mendes de Oliveira:

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

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 >>>

TR14-157 | 27th November 2014
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

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 >>>

TR14-056 | 18th April 2014
Zeev Dvir, Rafael Mendes de Oliveira

Factors of Sparse Polynomials are Sparse

Revisions: 1 , Comments: 1

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 >>>

TR14-003 | 10th January 2014
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Testing Equivalence of Polynomials under Shifts

Revisions: 2 , Comments: 1

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 >>>

ISSN 1433-8092 | Imprint