Search Results

Documents authored by Tzameret, Iddo

Document
DOI: 10.4230/LIPIcs.ITCS.2024.95
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness

Authors: Iddo Tzameret and Lu-Ming Zhang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We develop the theory of cryptographic nondeterministic-secure pseudorandomness beyond the point reached by Rudich’s original work [S. Rudich, 1997], and apply it to draw new consequences in average-case complexity and proof complexity. Specifically, we show the following: Demi-bit stretch: Super-bits and demi-bits are variants of cryptographic pseudorandom generators which are secure against nondeterministic statistical tests [S. Rudich, 1997]. They were introduced to rule out certain approaches to proving strong complexity lower bounds beyond the limitations set out by the Natural Proofs barrier of Razborov and Rudich [A. A. Razborov and S. Rudich, 1997]. Whether demi-bits are stretchable at all had been an open problem since their introduction. We answer this question affirmatively by showing that: every demi-bit b:{0,1}ⁿ → {0,1}^{n+1} can be stretched into sublinear many demi-bits b':{0,1}ⁿ → {0,1}^{n+n^{c}}, for every constant 0 < c < 1. Average-case hardness: Using work by Santhanam [Rahul Santhanam, 2020], we apply our results to obtain new average-case Kolmogorov complexity results: we show that K^{poly}[n-O(1)] is zero-error average-case hard against NP/poly machines iff K^{poly}[n-o(n)] is, where for a function s(n):ℕ → ℕ, K^{poly}[s(n)] denotes the languages of all strings x ∈ {0,1}ⁿ for which there are (fixed) polytime Turing machines of description-length at most s(n) that output x. Characterising super-bits by nondeterministic unpredictability: In the deterministic setting, Yao [Yao, 1982] proved that super-polynomial hardness of pseudorandom generators is equivalent to ("next-bit") unpredictability. Unpredictability roughly means that given any strict prefix of a random string, it is infeasible to predict the next bit. We initiate the study of unpredictability beyond the deterministic setting (in the cryptographic regime), and characterise the nondeterministic hardness of generators from an unpredictability perspective. Specifically, we propose four stronger notions of unpredictability: NP/poly-unpredictability, coNP/poly-unpredictability, ∩-unpredictability and ∪-unpredictability, and show that super-polynomial nondeterministic hardness of generators lies between ∩-unpredictability and ∪-unpredictability. Characterising super-bits by nondeterministic hard-core predicates: We introduce a nondeterministic variant of hard-core predicates, called super-core predicates. We show that the existence of a super-bit is equivalent to the existence of a super-core of some non-shrinking function. This serves as an analogue of the equivalence between the existence of a strong pseudorandom generator and the existence of a hard-core of some one-way function [Goldreich and Levin, 1989; Håstad et al., 1999], and provides a first alternative characterisation of super-bits. We also prove that a certain class of functions, which may have hard-cores, cannot possess any super-core.
Cite as

Iddo Tzameret and Lu-Ming Zhang. Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 95:1-95:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tzameret_et_al:LIPIcs.ITCS.2024.95,
  author =	{Tzameret, Iddo and Zhang, Lu-Ming},
  title =	{{Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{95:1--95:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.95},
  URN =		{urn:nbn:de:0030-drops-196234},
  doi =		{10.4230/LIPIcs.ITCS.2024.95},
  annote =	{Keywords: Pseudorandomness, Cryptography, Natural Proofs, Nondeterminism, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.19
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli

Authors: Fedor Part and Iddo Tzameret

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
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 with boolean variables over a ring R, to refute unsatisfiable sets of such disjunctions. Beginning in the work of [Ran Raz and Iddo Tzameret, 2008], through the work of [Dmitry Itsykson and Dmitry Sokolov, 2014] which focused on tree-like lower bounds, this refutation system was shown to be fairly strong. Subsequent work (cf. [Jan Krajícek, 2017; Dmitry Itsykson and Dmitry Sokolov, 2014; Jan Krajícek and Igor Carboni Oliveira, 2018; Michal Garlik and Lezsek Kołodziejczyk, 2018]) made it evident that establishing lower bounds against general Res(lin_R) refutations is a challenging and interesting task since the system captures a "minimal" extension of resolution with counting gates for which no super-polynomial lower bounds are known to date. We provide the first super-polynomial size lower bounds on general (dag-like) resolution over linear equations refutations in the large characteristic regime. In particular we prove that the subset-sum principle 1+ x_1 + ̇s +2^n x_n = 0 requires refutations of exponential-size over ℚ. Our proof technique is nontrivial and novel: roughly speaking, we show that under certain conditions every refutation of a subset-sum instance f=0, where f is a linear polynomial over ℚ, must pass through a fat clause containing an equation f=α for each α in the image of f under boolean assignments. We develop a somewhat different approach to prove exponential lower bounds against tree-like refutations of any subset-sum instance that depends on n variables, hence also separating tree-like from dag-like refutations over the rationals. We then turn to the finite fields regime, showing that the work of Itsykson and Sokolov [Dmitry Itsykson and Dmitry Sokolov, 2014] who obtained tree-like lower bounds over ?_2 can be carried over and extended to every finite field. We establish new lower bounds and separations as follows: (i) for every pair of distinct primes p,q, there exist CNF formulas with short tree-like refutations in Res(lin_{?_p}) that require exponential-size tree-like Res(lin_{?_q}) refutations; (ii) random k-CNF formulas require exponential-size tree-like Res(lin_{?_p}) refutations, for every prime p and constant k; and (iii) exponential-size lower bounds for tree-like Res(lin_?) refutations of the pigeonhole principle, for every field ?.
Cite as

Fedor Part and Iddo Tzameret. Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 19:1-19:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{part_et_al:LIPIcs.ITCS.2020.19,
  author =	{Part, Fedor and Tzameret, Iddo},
  title =	{{Resolution with Counting: Dag-Like Lower Bounds and Different Moduli}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{19:1--19:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.19},
  URN =		{urn:nbn:de:0030-drops-117041},
  doi =		{10.4230/LIPIcs.ITCS.2020.19},
  annote =	{Keywords: Proof complexity, concrete lower bounds, resolution, satisfiability, combinatorics}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2020.5
From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk)

Authors: Iddo Tzameret

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
This talk explores the question of what does logic and specifically proof theory can tell us about the fundamental hardness questions in computational complexity. We start with a brief description of the main concepts behind bounded arithmetic which is a family of weak formal theories of arithmetic that mirror in a precise manner the world of propositional proofs: if a statement of a given form is provable in a given bounded arithmetic theory then the same statement is suitably translated to a family of propositional formulas with short (polynomial-size) proofs in a corresponding propositional proof system. We will proceed to describe the motivations behind the study of bounded arithmetic theories, their corresponding propositional proof systems, and how they relate to the fundamental complexity class separations and circuit lower bounds questions in computational complexity. We provide a collage of results and recent developments showing how bounded arithmetic and propositional proof complexity form a cohesive framework in which both concrete combinatorial questions about complexity as well as meta-mathematical questions about provability of statements of complexity theory itself, are studied. Specific topics we shall mention are: (i) The bounded reverse mathematics program [Stephen Cook and Phuong Nguyen, 2010]: studying the weakest possible axiomatic assumptions that can prove important results in mathematics and computing (cf. [Iddo Tzameret and Stephen A. Cook, 2017; Pavel Hrubeš and Iddo Tzameret, 2015]), and the correspondence between circuit classes and theories. (ii) The meta-mathematics of computational complexity: what kind of reasoning power do we need in order to prove major results in complexity theory itself, and applications to complexity lower bounds (cf. [Razborov, 1995; Rahul Santhanam and Jan Pich, 2019]). (iii) Proof complexity: the systematic treatment of propositional proofs as combinatorial and algebraic objects and their algorithmic applications (cf. [Samuel Buss, 2012; Tonnian Pitassi and Iddo Tzameret, 2016; Noah Fleming et al., 2019]).
Cite as

Iddo Tzameret. From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk). In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{tzameret:LIPIcs.CSL.2020.5,
  author =	{Tzameret, Iddo},
  title =	{{From Classical Proof Theory to P versus NP: a Guide to Bounded Theories}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{5:1--5:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.5},
  URN =		{urn:nbn:de:0030-drops-116482},
  doi =		{10.4230/LIPIcs.CSL.2020.5},
  annote =	{Keywords: Bounded arithmetic, complexity class separations, circuit complexity, proof complexity, weak theories of arithmetic, feasible mathematics}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.32
Proof Complexity Lower Bounds from Algebraic Circuit Complexity

Authors: Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
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 boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem.
Cite as

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. Proof Complexity Lower Bounds from Algebraic Circuit Complexity. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.CCC.2016.32,
  author =	{Forbes, Michael A. and Shpilka, Amir and Tzameret, Iddo and Wigderson, Avi},
  title =	{{Proof Complexity Lower Bounds from Algebraic Circuit Complexity}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.32},
  URN =		{urn:nbn:de:0030-drops-58321},
  doi =		{10.4230/LIPIcs.CCC.2016.32},
  annote =	{Keywords: Proof Complexity, Algebraic Complexity, Nullstellensatz, Subset-Sum}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.412
Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs

Authors: Fu Li, Iddo Tzameret, and Zhengyu Wang

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e. Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the size of the formula proved) is a major open problem in proof complexity, and among a handful of fundamental hardness questions in complexity theory by and large. Non-commutative arithmetic formulas, on the other hand, constitute a quite weak computational model, for which exponential-size lower bounds were shown already back in 1991 by Nisan [STOC 1991], using a particularly transparent argument. In this work we show that Frege lower bounds in fact follow from corresponding size lower bounds on non-commutative formulas computing certain polynomials (and that such lower bounds on non-commutative formulas must exist, unless NP=coNP). More precisely, we demonstrate a natural association between tautologies T to non-commutative polynomials p, such that: (*) if T has a polynomial-size Frege proof then p has a polynomial-size non-commutative arithmetic formula; and conversely, when T is a DNF, if p has a polynomial-size non-commutative arithmetic formula over GF(2) then T has a Frege proof of quasi-polynomial size. The argument is a characterization of Frege proofs as non-commutative formulas: we show that the Frege system is (quasi-)polynomially equivalent to a non-commutative Ideal Proof System (IPS), following the recent work of Grochow and Pitassi [FOCS 2014] that introduced a propositional proof system in which proofs are arithmetic circuits, and the work in [Tzameret 2011] that considered adding the commutator as an axiom in algebraic propositional proof systems. This gives a characterization of propositional Frege proofs in terms of (non-commutative) arithmetic formulas that is tighter than (the formula version of IPS) in Grochow and Pitassi [FOCS 2014], in the following sense: (i) The non-commutative IPS is polynomial-time checkable - whereas the original IPS was checkable in probabilistic polynomial-time; and (ii) Frege proofs unconditionally quasi-polynomially simulate the non-commutative IPS - whereas Frege was shown to efficiently simulate IPS only assuming that the decidability of PIT for (commutative) arithmetic formulas by polynomial-size circuits is efficiently provable in Frege.
Cite as

Fu Li, Iddo Tzameret, and Zhengyu Wang. Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 412-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.CCC.2015.412,
  author =	{Li, Fu and Tzameret, Iddo and Wang, Zhengyu},
  title =	{{Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{412--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.412},
  URN =		{urn:nbn:de:0030-drops-50585},
  doi =		{10.4230/LIPIcs.CCC.2015.412},
  annote =	{Keywords: Proof complexity, algebraic complexity, arithmetic circuits, Frege, non-commutative formulas}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact