Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-106 | 21st July 2022
Suryajith Chillara, Coral Grichener, Amir Shpilka

On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>


TR22-105 | 18th July 2022
Ilario Bonacina, Nicola Galesi, Massimo Lauria

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>

TR22-104 | 18th July 2022
Nader Bshouty

On One-Sided Testing Affine Subspaces

Revisions: 1

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint