20 Search Results for "Koroth, Sajin"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.81
Supercritical Tradeoff Between Size and Depth for Resolution over Parities

Authors: Dmitry Itsykson and Alexander Knop

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res(⊕)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with the same hardness properties, but which additionally admits a resolution refutation of quasi-polynomial size. This establishes a supercritical tradeoff between size and depth for resolution over parities. The proof builds on the framework of Alekseev and Itsykson and relies on a lifting argument applied to the supercritical tradeoff between width and depth in resolution, proposed by Buss and Thapen (IPL 2026).
Cite as

Dmitry Itsykson and Alexander Knop. Supercritical Tradeoff Between Size and Depth for Resolution over Parities. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{itsykson_et_al:LIPIcs.ITCS.2026.81,
  author =	{Itsykson, Dmitry and Knop, Alexander},
  title =	{{Supercritical Tradeoff Between Size and Depth for Resolution over Parities}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{81:1--81:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.81},
  URN =		{urn:nbn:de:0030-drops-253680},
  doi =		{10.4230/LIPIcs.ITCS.2026.81},
  annote =	{Keywords: lifting theorems, resolution depth, resolution over parities, resolution width, supercritical tradeoff}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.55
Lifting to Randomized Parity Decision Trees

Authors: Farzan Byramji and Russell Impagliazzo

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

Abstract
We prove a lifting theorem from randomized decision tree depth to randomized parity decision tree (PDT) size. We use the same property of the gadget, stifling, which was introduced by Chattopadhyay, Mande, Sanyal and Sherif [ITCS 23] to prove a lifting theorem for deterministic PDTs. Moreover, even the milder condition that the gadget has minimum parity certificate complexity at least 2 suffices for lifting to randomized PDT size. To improve the dependence on the gadget g in the lower bounds for composed functions, we consider a related problem g_* whose inputs are certificates of g. It is implicit in the work of Chattopadhyay et al. that for any function f, lower bounds for the *-depth of f_* give lower bounds for the PDT size of f. We make this connection explicit in the deterministic case and show that it also holds for randomized PDTs. We then combine this with composition theorems for *-depth, which follow by adapting known composition theorems for decision trees. As a corollary, we get tight lifting theorems when the gadget is Indexing, Inner Product or Disjointness.
Cite as

Farzan Byramji and Russell Impagliazzo. Lifting to Randomized Parity Decision Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{byramji_et_al:LIPIcs.APPROX/RANDOM.2025.55,
  author =	{Byramji, Farzan and Impagliazzo, Russell},
  title =	{{Lifting to Randomized Parity Decision Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{55:1--55:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.55},
  URN =		{urn:nbn:de:0030-drops-244213},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.55},
  annote =	{Keywords: Parity decision trees, composition}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.33
A Min-Entropy Approach to Multi-Party Communication Lower Bounds

Authors: Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Information complexity is one of the most powerful techniques to prove information-theoretical lower bounds, in which Shannon entropy plays a central role. Though Shannon entropy has some convenient properties, such as the chain rule, it still has inherent limitations. One of the most notable barriers is the square-root loss, which appears in the square-root gap between entropy gaps and statistical distances, e.g., Pinsker’s inequality. To bypass this barrier, we introduce a new method based on min-entropy analysis. Building on this new method, we prove the following results. - An Ω(N^{∑_i α_i - max_i {α_i}}/k) randomized communication lower bound of the k-party set-intersection problem where the i-th party holds a random set of size ≈ N^{1-α_i}. - A tight Ω(n/k) randomized lower bound of the k-party Tree Pointer Jumping problems, improving an Ω(n/k²) lower bound by Chakrabarti, Cormode, and McGregor (STOC 08). - An Ω(n/k+√n) lower bound of the Chained Index problem, improving an Ω(n/k²) lower bound by Cormode, Dark, and Konrad (ICALP 19). Since these problems served as hard problems for numerous applications in streaming lower bounds and cryptography, our new lower bounds directly improve these streaming lower bounds and cryptography lower bounds. On the technical side, min-entropy does not have nice properties such as the chain rule. To address this issue, we enhance the structure-vs-pseudorandomness decomposition used by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24); both papers used this decomposition to prove communication lower bounds. In this paper, we give a new breath to this method in the multi-party setting, presenting a new toolkit for proving multi-party communication lower bounds.
Cite as

Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, and Jiapeng Zhang. A Min-Entropy Approach to Multi-Party Communication Lower Bounds. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.CCC.2025.33,
  author =	{Huang, Mi-Ying (Miryam) and Mao, Xinyu and Wang, Shuo and Yang, Guangxu and Zhang, Jiapeng},
  title =	{{A Min-Entropy Approach to Multi-Party Communication Lower Bounds}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{33:1--33:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.33},
  URN =		{urn:nbn:de:0030-drops-237273},
  doi =		{10.4230/LIPIcs.CCC.2025.33},
  annote =	{Keywords: communication complexity, lifting theorems, set intersection, chained index}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.24
Super-Critical Trade-Offs in Resolution over Parities via Lifting

Authors: Arkadev Chattopadhyay and Pavel Dvořák

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Razborov [Alexander A. Razborov, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter k = k(n), there exists k-CNF formulas over n variables, having resolution refutations of O(k) width, but every tree-like refutation of width n^{1-ε}/k needs size exp(n^Ω(k)). We extend this result to tree-like Resolution over parities, commonly denoted by Res(⊕), with parameters essentially unchanged. To obtain our result, we extend the lifting theorem of Chattopadhyay, Mande, Sanyal and Sherif [Arkadev Chattopadhyay et al., 2023] to handle tree-like affine DAGs. We introduce additional ideas from linear algebra to handle forget nodes along long paths.
Cite as

Arkadev Chattopadhyay and Pavel Dvořák. Super-Critical Trade-Offs in Resolution over Parities via Lifting. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2025.24,
  author =	{Chattopadhyay, Arkadev and Dvo\v{r}\'{a}k, Pavel},
  title =	{{Super-Critical Trade-Offs in Resolution over Parities via Lifting}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.24},
  URN =		{urn:nbn:de:0030-drops-237186},
  doi =		{10.4230/LIPIcs.CCC.2025.24},
  annote =	{Keywords: Proof complexity, Lifting, Resolution over parities}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.8
Amortized Closure and Its Applications in Lifting for Resolution over Parities

Authors: Klim Efremenko and Dmitry Itsykson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The notion of closure of a set of linear forms, first introduced by Efremenko, Garlik, and Itsykson [Klim Efremenko et al., 2024], has proven instrumental in proving lower bounds on the sizes of regular and bounded-depth Res(⊕) refutations [Klim Efremenko et al., 2024; Yaroslav Alekseev and Dmitry Itsykson, 2025]. In this work, we present amortized closure, an enhancement that retains the properties of original closure [Klim Efremenko et al., 2024] but offers tighter control on its growth. Specifically, adding a new linear form increases the amortized closure by at most one. We explore two applications that highlight the power of this new concept. Utilizing our newly defined amortized closure, we extend and provide a succinct and elegant proof of the recent lifting theorem by Chattopadhyay and Dvorak [Arkadev Chattopadhyay and Pavel Dvorak, 2025]. Namely we show that for an unsatisfiable CNF formula φ and a 1-stifling gadget g: {0,1}^𝓁 → {0,1}, if the lifted formula φ∘g has a tree-like Res(⊕) refutation of size 2^d and width w, then φ has a resolution refutation of depth d and width w. The original theorem by Chattopadhyay and Dvorak [Arkadev Chattopadhyay and Pavel Dvorak, 2025] applies only to the more restrictive class of strongly stifling gadgets. As a more significant application of amortized closure, we show improved lower bounds for bounded-depth Res(⊕), extending the depth beyond that of Alekseev and Itsykson [Yaroslav Alekseev and Dmitry Itsykson, 2025]. Our result establishes an exponential lower bound for depth-Ω(n log n) Res(⊕) refutations of lifted Tseitin formulas, a notable improvement over the existing depth-Ω(n log log n) Res(⊕) lower bound.
Cite as

Klim Efremenko and Dmitry Itsykson. Amortized Closure and Its Applications in Lifting for Resolution over Parities. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.CCC.2025.8,
  author =	{Efremenko, Klim and Itsykson, Dmitry},
  title =	{{Amortized Closure and Its Applications in Lifting for Resolution over Parities}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.8},
  URN =		{urn:nbn:de:0030-drops-237023},
  doi =		{10.4230/LIPIcs.CCC.2025.8},
  annote =	{Keywords: lifting, resolution over parities, closure of linear forms, lower bounds, width, depth, size vs depth tradeoff}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.14
On the Automatability of Tree-Like k-DNF Resolution

Authors: Gaia Carenini and Susanna F. de Rezende

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
A proof system 𝒫 is said to be automatable in time f(N) if there exists an algorithm that given as input an unsatisfiable formula F outputs a refutation of F in the proof system 𝒫 in time f(N), where N is the size of the smallest 𝒫-refutation of F plus the size of F. Atserias and Bonet (ECCC 2002), observed that tree-like k-DNF resolution is automatable in time N^{c⋅klog N} for a universal constant c. We show that, under the randomized exponential-time hypothesis (rETH), this is tight up to a O(log k)-factor in the exponent, i.e., we prove that tree-like k-DNF resolution, for k at most logarithmic in the number of variables of F, is not automatable in time N^o((k/log k)⋅log N) unless rETH is false. Our proof builds on the non-automatability results for resolution by Atserias and Müller (FOCS 2019), for algebraic proof systems by de Rezende, Göös, Nordström, Pitassi, Robere and Sokolov (STOC 2021), and for tree-like resolution by de Rezende (LAGOS 2021).
Cite as

Gaia Carenini and Susanna F. de Rezende. On the Automatability of Tree-Like k-DNF Resolution. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carenini_et_al:LIPIcs.CCC.2025.14,
  author =	{Carenini, Gaia and de Rezende, Susanna F.},
  title =	{{On the Automatability of Tree-Like k-DNF Resolution}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.14},
  URN =		{urn:nbn:de:0030-drops-237081},
  doi =		{10.4230/LIPIcs.CCC.2025.14},
  annote =	{Keywords: Proof Complexity, Tree-like k-DNF Resolution, Automatability}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.16
Direct Sums for Parity Decision Trees

Authors: Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.
Cite as

Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan. Direct Sums for Parity Decision Trees. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{besselman_et_al:LIPIcs.CCC.2025.16,
  author =	{Besselman, Tyler and G\"{o}\"{o}s, Mika and Guo, Siyao and Maystre, Gilbert and Yuan, Weiqiang},
  title =	{{Direct Sums for Parity Decision Trees}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{16:1--16:38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.16},
  URN =		{urn:nbn:de:0030-drops-237105},
  doi =		{10.4230/LIPIcs.CCC.2025.16},
  annote =	{Keywords: direct sum, parity decision trees, query complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.36
Lifting with Colourful Sunflowers

Authors: Susanna F. de Rezende and Marc Vinyals

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P.
Cite as

Susanna F. de Rezende and Marc Vinyals. Lifting with Colourful Sunflowers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2025.36,
  author =	{de Rezende, Susanna F. and Vinyals, Marc},
  title =	{{Lifting with Colourful Sunflowers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.36},
  URN =		{urn:nbn:de:0030-drops-237303},
  doi =		{10.4230/LIPIcs.CCC.2025.36},
  annote =	{Keywords: lifting, sunflower, clique, colouring, monotone circuit, cutting planes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.115
On the Complexity of Hazard-Free Formulas

Authors: Leah London Arazi and Amir Shpilka

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
This paper studies the hazard-free formula complexity of Boolean functions. Our first result shows that unate functions are the only Boolean functions for which the monotone formula complexity of the hazard-derivative equals the hazard-free formula complexity of the function itself. Consequently, they are the only functions for which the hazard-derivative approach of Ikenmeyer et al. (J. ACM, 2019) yields optimal bounds. Our second result proves that the hazard-free formula complexity of a uniformly random Boolean function is at most 2^{(1+o(1))n}. Prior to this, no better upper bound than O(3ⁿ) was known. Notably, unlike in the general case of Boolean circuits and formulas, where the typical complexity is derived from that of the multiplexer function with n-bit selector, the hazard-free formula complexity of a random function is smaller than the optimal hazard-free formula for the multiplexer by an exponential factor in n. We provide two proofs of this fact. The first is direct, bounding the number of prime implicants of a random Boolean function and using this bound to construct a DNF of the claimed size. The second introduces a new and independently interesting result: a weak converse to the hazard-derivative lower bound method, which gives an upper bound on the hazard-free complexity of a function in terms of the monotone complexity of a subset of its hazard-derivatives. Additionally, we explore the hazard-free formula complexity of block composition of Boolean functions and obtain a result in the hazard-free setting that is analogous to a result of Karchmer, Raz, and Wigderson (Computational Complexity, 1995) in the monotone setting. We show that our result implies a stronger lower bound on the hazard-free formula depth of the block composition of the set covering function with the multiplexer function than the bound obtained via the hazard-derivative method.
Cite as

Leah London Arazi and Amir Shpilka. On the Complexity of Hazard-Free Formulas. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 115:1-115:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{londonarazi_et_al:LIPIcs.ICALP.2025.115,
  author =	{London Arazi, Leah and Shpilka, Amir},
  title =	{{On the Complexity of Hazard-Free Formulas}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{115:1--115:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.115},
  URN =		{urn:nbn:de:0030-drops-234920},
  doi =		{10.4230/LIPIcs.ICALP.2025.115},
  annote =	{Keywords: Hazard-free computation, Boolean formulas, monotone formulas, Karchmer-Wigderson games, communication complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.78
Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity

Authors: Vladimir Podolskii and Alexander Shekhovtsov

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [Paul Beame and Sajin Koroth, 2023] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that for any m ≥ 4 deterministic decision tree complexity of a function f can be lifted to the so called semi-structured communication complexity of f∘Ind_m, where Ind_m is the Indexing gadget. As our main contribution we extend these results to randomized setting. Our results also apply to a substantially larger set of gadgets. More specifically, we introduce a new complexity measure of gadgets, linear diversity. For all gadgets g with non-trivial linear diversity we show that randomized decision tree complexity of f lifts to randomized semi-structured communication complexity of f∘g. In particular, this gives tight lifting results for Indexing gadget Ind_m, Inner Product gadget IP_m for all m ≥ 2, and for Majority gadget MAJ_m for all m ≥ 4. We prove the same results for deterministic case. From our result it immediately follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [Arkadev Chattopadhyay et al., 2023] for Inner Product gadget. To obtain our results we introduce a new secret sets approach to simulation of semi-structured communication protocols by decision trees. It allows us to simulate (restricted classes of) communication protocols on truly uniform distribution of inputs.
Cite as

Vladimir Podolskii and Alexander Shekhovtsov. Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 78:1-78:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{podolskii_et_al:LIPIcs.ITCS.2025.78,
  author =	{Podolskii, Vladimir and Shekhovtsov, Alexander},
  title =	{{Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{78:1--78:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.78},
  URN =		{urn:nbn:de:0030-drops-227061},
  doi =		{10.4230/LIPIcs.ITCS.2025.78},
  annote =	{Keywords: communication complexity, decision trees, lifting}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.75
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

Authors: Xinyu Mao, Guangxu Yang, and Jiapeng Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We prove an Ω(n / k + k) communication lower bound on (k - 1)-round distributional complexity of the k-step pointer chasing problem under uniform input distribution, improving the Ω(n/k - klog n) lower bound due to Yehudayoff (Combinatorics Probability and Computing, 2020). Our lower bound almost matches the upper bound of Õ(n/k + k) communication by Nisan and Wigderson (STOC 91). As part of our approach, we put forth gadgetless lifting, a new framework that lifts lower bounds for a family of restricted protocols into lower bounds for general protocols. A key step in gadgetless lifting is choosing the appropriate definition of restricted protocols. In this paper, our definition of restricted protocols is inspired by the structure-vs-pseudorandomness decomposition by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24). Previously, round-communication trade-offs were mainly obtained by round elimination and information complexity. Both methods have some barriers in some situations, and we believe gadgetless lifting could potentially address these barriers.
Cite as

Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mao_et_al:LIPIcs.ITCS.2025.75,
  author =	{Mao, Xinyu and Yang, Guangxu and Zhang, Jiapeng},
  title =	{{Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{75:1--75:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.75},
  URN =		{urn:nbn:de:0030-drops-227038},
  doi =		{10.4230/LIPIcs.ITCS.2025.75},
  annote =	{Keywords: communication complexity, lifting theorems, pointer chasing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.48
Proving Unsatisfiability with Hitting Formulas

Authors: Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals

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

Abstract
A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. Hitting formulas have been studied in many different contexts at least since [Iwama, 1989] and, based on experimental evidence, Peitl and Szeider [Tomás Peitl and Stefan Szeider, 2022] conjectured that unsatisfiable hitting formulas are among the hardest for resolution. Using the fact that hitting formulas are easy to check for satisfiability we make them the foundation of a new static proof system {{rmHitting}}: a refutation of a CNF in {{rmHitting}} is an unsatisfiable hitting formula such that each of its clauses is a weakening of a clause of the refuted CNF. Comparing this system to resolution and other proof systems is equivalent to studying the hardness of hitting formulas. Our first result is that {{rmHitting}} is quasi-polynomially simulated by tree-like resolution, which means that hitting formulas cannot be exponentially hard for resolution and partially refutes the conjecture of Peitl and Szeider. We show that tree-like resolution and {{rmHitting}} are quasi-polynomially separated, while for resolution, this question remains open. For a system that is only quasi-polynomially stronger than tree-like resolution, {{rmHitting}} is surprisingly difficult to polynomially simulate in another proof system. Using the ideas of Raz-Shpilka’s polynomial identity testing for noncommutative circuits [Raz and Shpilka, 2005] we show that {{rmHitting}} is p-simulated by {{rmExtended {{rmFrege}}}}, but we conjecture that much more efficient simulations exist. As a byproduct, we show that a number of static (semi)algebraic systems are verifiable in deterministic polynomial time. We consider multiple extensions of {{rmHitting}}, and in particular a proof system {{{rmHitting}}(⊕)} related to the {{{rmRes}}(⊕)} proof system for which no superpolynomial-size lower bounds are known. {{{rmHitting}}(⊕)} p-simulates the tree-like version of {{{rmRes}}(⊕)} and is at least quasi-polynomially stronger. We show that formulas expressing the non-existence of perfect matchings in the graphs K_{n,n+2} are exponentially hard for {{{rmHitting}}(⊕)} via a reduction to the partition bound for communication complexity. See the full version of the paper for the proofs. They are omitted in this Extended Abstract.
Cite as

Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.ITCS.2024.48,
  author =	{Filmus, Yuval and Hirsch, Edward A. and Riazanov, Artur and Smal, Alexander and Vinyals, Marc},
  title =	{{Proving Unsatisfiability with Hitting Formulas}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{48:1--48:20},
  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.48},
  URN =		{urn:nbn:de:0030-drops-195762},
  doi =		{10.4230/LIPIcs.ITCS.2024.48},
  annote =	{Keywords: hitting formulas, polynomial identity testing, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.14
On Disperser/Lifting Properties of the Index and Inner-Product Functions

Authors: Paul Beame and Sajin Koroth

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated "lifted" function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. A number of important complexity questions could be resolved if we could make substantial improvements in the input size required for lifting with the Index function, which is a universal gadget for lifting, from its current near-linear size down to polylogarithmic in the number of inputs N of the original function or, ideally, constant. The near-linear size bound was recently shown by Lovett, Meka, Mertz, Pitassi and Zhang [Shachar Lovett et al., 2022] using a recent breakthrough improvement on the Sunflower Lemma to show that a certain graph associated with an Index function of that size is a disperser. They also stated a conjecture about the Index function that is essential for further improvements in the size required for lifting with Index using current techniques. In this paper we prove the following; - The conjecture of Lovett et al. is false when the size of the Index gadget is less than logarithmic in N. - The same limitation applies to the Inner-Product function. More precisely, the Inner-Product function, which is known to satisfy the disperser property at size O(log N), also does not have this property when its size is less than log N. - Notwithstanding the above, we prove a lifting theorem that applies to Index gadgets of any size at least 4 and yields lower bounds for a restricted class of communication protocols in which one of the players is limited to sending parities of its inputs. - Using a modification of the same idea with improved lifting parameters we derive a strong lifting theorem from decision tree size to parity decision tree size. We use this, in turn, to derive a general lifting theorem in proof complexity from tree-resolution size to tree-like Res(⊕) refutation size, which yields many new exponential lower bounds on such proofs.
Cite as

Paul Beame and Sajin Koroth. On Disperser/Lifting Properties of the Index and Inner-Product Functions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{beame_et_al:LIPIcs.ITCS.2023.14,
  author =	{Beame, Paul and Koroth, Sajin},
  title =	{{On Disperser/Lifting Properties of the Index and Inner-Product Functions}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.14},
  URN =		{urn:nbn:de:0030-drops-175172},
  doi =		{10.4230/LIPIcs.ITCS.2023.14},
  annote =	{Keywords: Decision trees, communication complexity, lifting theorems, proof complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.15
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates

Authors: Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
The class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class 𝒢. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n^{1.99}]∘𝒢, for classes 𝒢 of functions with low communication complexity. Let R^(k)(𝒢) be the maximum k-party number-on-forehead randomized communication complexity of a function in 𝒢. Among other results, we show that: - The Generalized Inner Product function 𝖦𝖨𝖯^k_n cannot be computed in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 on more than 1/2+ε fraction of inputs for s = o(n²/{(k⋅4^k⋅R^(k)(𝒢)⋅log (n/ε)⋅log(1/ε))²}). This significantly extends the lower bounds against bipartite formulas obtained by [Avishay Tal, 2017]. As a corollary, we get an average-case lower bound for 𝖦𝖨𝖯^k_n against 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^{1.99}]∘𝖯𝖳𝖥^{k-1}, i.e., sub-quadratic-size de Morgan formulas with degree-(k-1) PTF (polynomial threshold function) gates at the bottom. - There is a PRG of seed length n/2 + O(√s⋅R^(2)(𝒢)⋅log(s/ε)⋅log(1/ε)) that ε-fools FORMULA[s]∘𝒢. For the special case of FORMULA[s]∘𝖫𝖳𝖥, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length O(n^{1/2}⋅s^{1/4}⋅log(n)⋅log(n/ε)). In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε ≤ 1/n, complementing a recent result of [Ryan O'Donnell et al., 2019]. - There exists a randomized 2^{n-t}-time #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢, where t = Ω(n/{√s⋅log²(s)⋅R^(2)(𝒢)})^{1/2}. In particular, this implies a nontrivial #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖫𝖳𝖥. - The Minimum Circuit Size Problem is not in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱; thereby making progress on hardness magnification, in connection with results from [Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019]. On the algorithmic side, we show that the concept class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱 can be PAC-learned in time 2^O(n/log n).
Cite as

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira. Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 15:1-15:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kabanets_et_al:LIPIcs.CCC.2020.15,
  author =	{Kabanets, Valentine and Koroth, Sajin and Lu, Zhenjian and Myrisiotis, Dimitrios and Oliveira, Igor C.},
  title =	{{Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{15:1--15:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.15},
  URN =		{urn:nbn:de:0030-drops-125673},
  doi =		{10.4230/LIPIcs.CCC.2020.15},
  annote =	{Keywords: de Morgan formulas, circuit lower bounds, satisfiability (SAT), pseudorandom generators (PRGs), learning, communication complexity, polynomial threshold functions (PTFs), parities}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.17
Limits of Preprocessing

Authors: Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
It is a classical result that the inner product function cannot be computed by an AC⁰ circuit [Merrick L. Furst et al., 1981; Miklós Ajtai, 1983; Johan Håstad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{ω(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning AC⁰ under simple input distributions.
Cite as

Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler. Limits of Preprocessing. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.CCC.2020.17,
  author =	{Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Kindler, Guy},
  title =	{{Limits of Preprocessing}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.17},
  URN =		{urn:nbn:de:0030-drops-125697},
  doi =		{10.4230/LIPIcs.CCC.2020.17},
  annote =	{Keywords: circuit, communication complexity, IPPP, preprocessing, PRF, simultaneous messages}
}
  • Refine by Type
  • 20 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 10 2025
  • 1 2024
  • 1 2023
  • 3 2020
  • Show More...

  • Refine by Author
  • 5 Koroth, Sajin
  • 3 Filmus, Yuval
  • 2 Chattopadhyay, Arkadev
  • 2 Itsykson, Dmitry
  • 2 Mao, Xinyu
  • Show More...

  • Refine by Series/Journal
  • 20 LIPIcs

  • Refine by Classification
  • 11 Theory of computation → Communication complexity
  • 6 Theory of computation → Circuit complexity
  • 6 Theory of computation → Proof complexity
  • 5 Theory of computation → Oracles and decision trees
  • 2 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 10 communication complexity
  • 5 lifting theorems
  • 3 lifting
  • 3 lower bounds
  • 2 composition
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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