67 Search Results for "Kabanets, Valentine"

Volume

LIPIcs, Volume 200

36th Computational Complexity Conference (CCC 2021)

CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference)

Editors: Valentine Kabanets

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.31
Synergy Between Circuit Obfuscation and Circuit Minimization

Authors: Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
We study close connections between Indistinguishability Obfuscation (IO) and the Minimum Circuit Size Problem (MCSP), and argue that efficient algorithms/construction for MCSP and IO create a synergy. Some of our main results are: - If there exists a perfect (imperfect) IO that is computationally secure against nonuniform polynomial-size circuits, then for all k ∈ ℕ: NP ∩ ZPP^{MCSP} ⊈ SIZE[n^k] (MA ∩ ZPP^{MCSP} ⊈ SIZE[n^k]). - In addition, if there exists a perfect IO that is computationally secure against nonuniform polynomial-size circuits, then NEXP ∩ ZPEXP^{MCSP} ⊈ P/poly. - If MCSP ∈ BPP, then statistical security and computational security for IO are equivalent. - If computationally-secure perfect IO exists, then MCSP ∈ BPP iff NP = ZPP. - If computationally-secure perfect IO exists, then ZPEXP ≠ BPP. To the best of our knowledge, this is the first consequence of strong circuit lower bounds from the existence of an IO. The results are obtained via a construction of an optimal universal distinguisher, computable in randomized polynomial time with access to the MCSP oracle, that will distinguish any two circuit-samplable distributions with the advantage that is the statistical distance between these two distributions minus some negligible error term. This is our main technical contribution. As another immediate application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that SZK ⊆ BPP^{MCSP}.
Cite as

Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. Synergy Between Circuit Obfuscation and Circuit Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{impagliazzo_et_al:LIPIcs.APPROX/RANDOM.2023.31,
  author =	{Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya},
  title =	{{Synergy Between Circuit Obfuscation and Circuit Minimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.31},
  URN =		{urn:nbn:de:0030-drops-188569},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.31},
  annote =	{Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.12
Improved Learning from Kolmogorov Complexity

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in P/poly, under the uniform distribution and with membership queries. It is still an open problem to get from natural properties learning algorithms that do not rely on membership queries but rather use randomly drawn labeled examples. Natural properties may be understood as an average-case version of MCSP, the problem of deciding the minimum size of a circuit computing a given truth-table. Problems related to MCSP include those concerning time-bounded Kolmogorov complexity. MKTP, for example, asks for the KT-complexity of a given string. KT-complexity is a relaxation of circuit size, as it does away with the requirement that a short description of a string be interpreted as a boolean circuit. In this work, under assumptions of MKTP and the related problem MK^tP being easy on average, we get learning algorithms for boolean functions in P/poly that - work over any distribution D samplable by a family of polynomial-size circuits (given explicitly in the case of MKTP), - only use randomly drawn labeled examples from D, and - are agnostic (do not require the target function to belong to the hypothesis class). Our results build upon the recent work of Hirahara and Nanashima (FOCS, 2021) who showed similar learning consequences but under a stronger assumption that NP is easy on average.
Cite as

Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Improved Learning from Kolmogorov Complexity}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{12:1--12:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.12},
  URN =		{urn:nbn:de:0030-drops-182825},
  doi =		{10.4230/LIPIcs.CCC.2023.12},
  annote =	{Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity}
}
Document
DOI: 10.4230/DagRep.12.9.41
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)

Authors: Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán

Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 2237 "Algebraic and Analytic Methods in Computational Complexity". Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Beside algebraic methods, analytic methods have been used for quite some time in theoretical computer science. These methods can also be used to solve algebraic problems as show by many recent examples in the areas of derandomization, coding theory or circuit lower bounds. These new directions were in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 18391. This Dagstuhl Seminar brought together researchers who are using a diverse array of algebraic and analytic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar played a role in educating a diverse community about the latest new techniques, spurring further progress.
Cite as

Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{blaser_et_al:DagRep.12.9.41,
  author =	{Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo},
  title =	{{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)}},
  pages =	{41--59},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{9},
  editor =	{Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.9.41},
  URN =		{urn:nbn:de:0030-drops-178092},
  doi =		{10.4230/DagRep.12.9.41},
  annote =	{Keywords: (de-)randomization, algebra, circuits, coding, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.16
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Authors: Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990]. In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations: - If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)]. - If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)]. - In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions. - If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)]. - Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/poly-samplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.
Cite as

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16,
  author =	{Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{16:1--16:60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16},
  URN =		{urn:nbn:de:0030-drops-165785},
  doi =		{10.4230/LIPIcs.CCC.2022.16},
  annote =	{Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CCC.2021
LIPIcs, Volume 200, CCC 2021, Complete Volume

Authors: Valentine Kabanets

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
LIPIcs, Volume 200, CCC 2021, Complete Volume
Cite as

Valentine Kabanets. LIPIcs, Volume 200, CCC 2021, Complete Volume. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1-1290, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{kabanets:LIPIcs.CCC.2021,
  title =	{{LIPIcs, Volume 200, CCC 2021, Complete Volume}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{1--1290},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021},
  URN =		{urn:nbn:de:0030-drops-142732},
  doi =		{10.4230/LIPIcs.CCC.2021},
  annote =	{Keywords: LIPIcs, Volume 200, CCC 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CCC.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Valentine Kabanets

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Valentine Kabanets. Front Matter, Table of Contents, Preface, Conference Organization. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kabanets:LIPIcs.CCC.2021.0,
  author =	{Kabanets, Valentine},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.0},
  URN =		{urn:nbn:de:0030-drops-142745},
  doi =		{10.4230/LIPIcs.CCC.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.1
Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The main contribution of this work is a rate amplification procedure for LCC. Our procedure converts any q-query linear LCC, having rate ρ and, say, constant distance to an asymptotically good LCC with q^poly(1/ρ) queries. Our second contribution is a distance amplification procedure for LDC that converts any linear LDC with distance δ and, say, constant rate to an asymptotically good LDC. The query complexity only suffers a multiplicative overhead that is roughly equal to the query complexity of a length 1/δ asymptotically good LDC. This improves upon the poly(1/δ) overhead obtained by the AEL distance amplification procedure [Alon and Luby, 1996; Alon et al., 1995]. Our work establishes that the construction of asymptotically good LDC and LCC is reduced, with a minor overhead in query complexity, to the problem of constructing a vanishing rate linear LCC and a (rapidly) vanishing distance linear LDC, respectively.
Cite as

Gil Cohen and Tal Yankovitz. Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1:1-1:57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2021.1,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{1:1--1:57},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.1},
  URN =		{urn:nbn:de:0030-drops-142750},
  doi =		{10.4230/LIPIcs.CCC.2021.1},
  annote =	{Keywords: Locally decodable codes, Locally correctable codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.2
An Improved Protocol for the Exactly-N Problem

Authors: Nati Linial and Adi Shraibman

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
In the 3-players exactly-N problem the players need to decide whether x+y+z = N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Even though this is such a basic problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This improved protocol has also interesting consequences in additive combinatorics. As we explain below, it yields a higher lower bound on the possible density of corner-free sets in [N]×[N].
Cite as

Nati Linial and Adi Shraibman. An Improved Protocol for the Exactly-N Problem. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 2:1-2:8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{linial_et_al:LIPIcs.CCC.2021.2,
  author =	{Linial, Nati and Shraibman, Adi},
  title =	{{An Improved Protocol for the Exactly-N Problem}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{2:1--2:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.2},
  URN =		{urn:nbn:de:0030-drops-142760},
  doi =		{10.4230/LIPIcs.CCC.2021.2},
  annote =	{Keywords: Communication complexity, Number-On-the-Forehead, Corner-free sets}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.3
Proof Complexity of Natural Formulas via Communication Arguments

Authors: Dmitry Itsykson and Artur Riazanov

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
A canonical communication problem Search(φ) is defined for every unsatisfiable CNF φ: an assignment to the variables of φ is partitioned among the communicating parties, they are to find a clause of φ falsified by this assignment. Lower bounds on the randomized k-party communication complexity of Search(φ) in the number-on-forehead (NOF) model imply tree-size lower bounds, rank lower bounds, and size-space tradeoffs for the formula φ in the semantic proof system T^{cc}(k,c) that operates with proof lines that can be computed by k-party randomized communication protocol using at most c bits of communication [Göös and Pitassi, 2014]. All known lower bounds on Search(φ) (e.g. [Beame et al., 2007; Göös and Pitassi, 2014; Russell Impagliazzo et al., 1994]) are realized on ad-hoc formulas φ (i.e. they were introduced specifically for these lower bounds). We introduce a new communication complexity approach that allows establishing proof complexity lower bounds for natural formulas. First, we demonstrate our approach for two-party communication and apply it to the proof system Res(⊕) that operates with disjunctions of linear equalities over 𝔽₂ [Dmitry Itsykson and Dmitry Sokolov, 2014]. Let a formula PM_G encode that a graph G has a perfect matching. If G has an odd number of vertices, then PM_G has a tree-like Res(⊕)-refutation of a polynomial-size [Dmitry Itsykson and Dmitry Sokolov, 2014]. It was unknown whether this is the case for graphs with an even number of vertices. Using our approach we resolve this question and show a lower bound 2^{Ω(n)} on size of tree-like Res(⊕)-refutations of PM_{K_{n+2,n}}. Then we apply our approach for k-party communication complexity in the NOF model and obtain a Ω(1/k 2^{n/2k - 3k/2}) lower bound on the randomized k-party communication complexity of Search(BPHP^{M}_{2ⁿ}) w.r.t. to some natural partition of the variables, where BPHP^{M}_{2ⁿ} is the bit pigeonhole principle and M = 2ⁿ+2^{n(1-1/k)}. In particular, our result implies that the bit pigeonhole requires exponential tree-like Th(k) proofs, where Th(k) is the semantic proof system operating with polynomial inequalities of degree at most k and k = 𝒪(log^{1-ε} n) for some ε > 0. We also show that BPHP^{2ⁿ+1}_{2ⁿ} superpolynomially separates tree-like Th(log^{1-ε} m) from tree-like Th(log m), where m is the number of variables in the refuted formula.
Cite as

Dmitry Itsykson and Artur Riazanov. Proof Complexity of Natural Formulas via Communication Arguments. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 3:1-3:34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{itsykson_et_al:LIPIcs.CCC.2021.3,
  author =	{Itsykson, Dmitry and Riazanov, Artur},
  title =	{{Proof Complexity of Natural Formulas via Communication Arguments}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{3:1--3:34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.3},
  URN =		{urn:nbn:de:0030-drops-142773},
  doi =		{10.4230/LIPIcs.CCC.2021.3},
  annote =	{Keywords: bit pigeonhole principle, disjointness, multiparty communication complexity, perfect matching, proof complexity, randomized communication complexity, Resolution over linear equations, tree-like proofs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.4
A Lower Bound on Determinantal Complexity

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The determinantal complexity of a polynomial P ∈ 𝔽[x₁, …, x_n] over a field 𝔽 is the dimension of the smallest matrix M whose entries are affine functions in 𝔽[x₁, …, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑_{i = 1}^n x_i^n is at least 1.5n - 3. For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max{n,d}. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max{n,d}, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [Jarod Alper et al., 2017] for the same polynomial.
Cite as

Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{A Lower Bound on Determinantal Complexity}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4},
  URN =		{urn:nbn:de:0030-drops-142781},
  doi =		{10.4230/LIPIcs.CCC.2021.4},
  annote =	{Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.5
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies

Authors: Mark Braverman and Dor Minzer

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
What is the least surface area of a permutation-symmetric body B whose ℤⁿ translations tile ℝⁿ? Since any such body must have volume 1, the isoperimetric inequality implies that its surface area must be at least Ω(√n). Remarkably, Kindler et al. showed that for general bodies B this is tight, i.e. that there is a tiling body of ℝⁿ whose surface area is O(√n). In theoretical computer science, the tiling problem is intimately related to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct non-trivial tilings of ℝⁿ. In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutation-symmetric variant of the tiling problem in ℝⁿ. We show that any permutation-symmetric body that tiles ℝⁿ must have surface area at least Ω(n/√{log n}), and that this bound is tight, i.e. that there is a permutation-symmetric tiling body of ℝⁿ with surface area O(n/√{log n}). We also give matching bounds for the value of the symmetric parallel repetition of Raz’s odd cycle game. Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies.
Cite as

Mark Braverman and Dor Minzer. Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 5:1-5:48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.CCC.2021.5,
  author =	{Braverman, Mark and Minzer, Dor},
  title =	{{Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{5:1--5:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.5},
  URN =		{urn:nbn:de:0030-drops-142796},
  doi =		{10.4230/LIPIcs.CCC.2021.5},
  annote =	{Keywords: PCP, Parallel Repetition, Tilings}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.6
On the Power and Limitations of Branch and Cut

Authors: Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The Stabbing Planes proof system [Paul Beame et al., 2018] was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas - certain unsatisfiable systems of linear equations od 2 - which are canonical hard examples for many algebraic proof systems. In a recent (and surprising) result, Dadush and Tiwari [Daniel Dadush and Samarth Tiwari, 2020] showed that these short refutations of the Tseitin formulas could be translated into quasi-polynomial size and depth Cutting Planes proofs, refuting a long-standing conjecture. This translation raises several interesting questions. First, whether all Stabbing Planes proofs can be efficiently simulated by Cutting Planes. This would allow for the substantial analysis done on the Cutting Planes system to be lifted to practical mixed integer programming solvers. Second, whether the quasi-polynomial depth of these proofs is inherent to Cutting Planes. In this paper we make progress towards answering both of these questions. First, we show that any Stabbing Planes proof with bounded coefficients (SP*) can be translated into Cutting Planes. As a consequence of the known lower bounds for Cutting Planes, this establishes the first exponential lower bounds on SP*. Using this translation, we extend the result of Dadush and Tiwari to show that Cutting Planes has short refutations of any unsatisfiable system of linear equations over a finite field. Like the Cutting Planes proofs of Dadush and Tiwari, our refutations also incur a quasi-polynomial blow-up in depth, and we conjecture that this is inherent. As a step towards this conjecture, we develop a new geometric technique for proving lower bounds on the depth of Cutting Planes proofs. This allows us to establish the first lower bounds on the depth of Semantic Cutting Planes proofs of the Tseitin formulas.
Cite as

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the Power and Limitations of Branch and Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 6:1-6:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.CCC.2021.6,
  author =	{Fleming, Noah and G\"{o}\"{o}s, Mika and Impagliazzo, Russell and Pitassi, Toniann and Robere, Robert and Tan, Li-Yang and Wigderson, Avi},
  title =	{{On the Power and Limitations of Branch and Cut}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{6:1--6:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.6},
  URN =		{urn:nbn:de:0030-drops-142809},
  doi =		{10.4230/LIPIcs.CCC.2021.6},
  annote =	{Keywords: Proof Complexity, Integer Programming, Cutting Planes, Branch and Cut, Stabbing Planes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.7
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

Authors: Prerona Chatterjee

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The motivating question for this work is a long standing open problem, posed by Nisan [Noam Nisan, 1991], regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question remains open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011]) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards resolving the VF_{nc} vs VBP_{nc} question, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n²-variate degree d abecedarian polynomial f_{n,d}(𝐱) such that - f_{n, d}(𝐱) can be computed by an abecedarian ABP of size O(nd); - any abecedarian formula computing f_{n, log n}(𝐱) must have size at least n^{Ω(log log n)}. We also show that a super-polynomial lower bound against abecedarian formulas for f_{log n, n}(𝐱) would separate the powers of formulas and ABPs in the non-commutative setting.
Cite as

Prerona Chatterjee. Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 7:1-7:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chatterjee:LIPIcs.CCC.2021.7,
  author =	{Chatterjee, Prerona},
  title =	{{Separating ABPs and Some Structured Formulas in the Non-Commutative Setting}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.7},
  URN =		{urn:nbn:de:0030-drops-142812},
  doi =		{10.4230/LIPIcs.CCC.2021.7},
  annote =	{Keywords: Non-Commutative Formulas, Lower Bound, Separating ABPs and Formulas}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.8
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications

Authors: Alexander Golovnev and Ishay Haviv

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The orthogonality dimension of a graph G = (V,E) over a field 𝔽 is the smallest integer t for which there exists an assignment of a vector u_v ∈ 𝔽^t with ⟨ u_v,u_v ⟩ ≠ 0 to every vertex v ∈ V, such that ⟨ u_v, u_{v'} ⟩ = 0 whenever v and v' are adjacent vertices in G. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant c such that for every sufficiently large integer t, it is NP-hard to decide whether the orthogonality dimension of an input graph over ℝ is at most t or at least 3t/2-c. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free n-vertex graphs whose complement has orthogonality dimension over the binary field at most n^{1-δ} for some constant δ > 0. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.
Cite as

Alexander Golovnev and Ishay Haviv. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.CCC.2021.8,
  author =	{Golovnev, Alexander and Haviv, Ishay},
  title =	{{The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.8},
  URN =		{urn:nbn:de:0030-drops-142829},
  doi =		{10.4230/LIPIcs.CCC.2021.8},
  annote =	{Keywords: Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs}
}
  • Refine by Author
  • 23 Kabanets, Valentine
  • 12 Impagliazzo, Russell
  • 8 Kolokolova, Antonina
  • 4 Lu, Zhenjian
  • 3 Bläser, Markus
  • Show More...

  • Refine by Classification
  • 13 Theory of computation → Circuit complexity
  • 12 Theory of computation → Algebraic complexity theory
  • 9 Theory of computation → Computational complexity and cryptography
  • 7 Theory of computation → Communication complexity
  • 7 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 6 circuit lower bounds
  • 5 circuit complexity
  • 5 communication complexity
  • 5 lower bounds
  • 4 circuits
  • Show More...

  • Refine by Type
  • 66 document
  • 1 volume

  • Refine by Publication Year
  • 47 2021
  • 4 2017
  • 3 2015
  • 3 2019
  • 3 2023
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact