Zobrazeno 1 - 10
of 75
pro vyhledávání: '"TZAMERET, IDDO"'
Autor:
Atserias, Albert, Tzameret, Iddo
The Schwartz-Zippel Lemma states that if a low-degree multivariate polynomial with coefficients in a field is not zero everywhere in the field, then it has few roots on every finite subcube of the field. This fundamental fact about multivariate polyn
Externí odkaz:
http://arxiv.org/abs/2411.07966
Autor:
Tzameret, Iddo, Zhang, Lu-Ming
We develop the theory of cryptographic nondeterministic-secure pseudorandomness beyond the point reached by Rudich's original work (Rudich 1997), and apply it to draw new consequences in average-case complexity and proof complexity. Specifically, we
Externí odkaz:
http://arxiv.org/abs/2304.14700
Publikováno v:
In Annals of Pure and Applied Logic January 2025 176(1)
We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically, we show that the subset-sum variant $\sum_{i,j,k,\ell\in[n]} z_{ijk\e
Externí odkaz:
http://arxiv.org/abs/2205.07175
Semi-algebraic proof systems such as sum-of-squares (SoS) have attracted a lot of attention recently due to their relation to approximation algorithms: constant degree semi-algebraic proofs lead to conjecturally optimal polynomial-time approximation
Externí odkaz:
http://arxiv.org/abs/2105.07531
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?
We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomi
Externí odkaz:
http://arxiv.org/abs/1911.06738
Autor:
Tzameret, Iddo, Cook, Stephen A.
Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzamer
Externí odkaz:
http://arxiv.org/abs/1811.04313
Autor:
Part, Fedor, Tzameret, Iddo
Resolution over linear equations is a natural extension of the popular resolution refutation system, augmented with the ability to carry out basic counting. Denoted Res(lin_R), this refutation system operates with disjunctions of linear equations wit
Externí odkaz:
http://arxiv.org/abs/1806.09383
Autor:
TZAMERET, IDDO1 Iddo.Tzameret@gmail.com, COOK, STEPHEN A.2 sacook@cs.toronto.edu
Publikováno v:
Journal of the ACM. Mar2021, Vol. 68 Issue 2, p1-80. 80p.
Autor:
Pitassi, Tonnian, Tzameret, Iddo
We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problem
Externí odkaz:
http://arxiv.org/abs/1607.00443