73 Search Results for "Moshkovitz, Dana"

Volume

LIPIcs, Volume 383

41st Computational Complexity Conference (CCC 2026)

CCC 2026, Lisbon, Portugal, August 3-6, 2026

Editors: Dana Moshkovitz

Document
Complete Volume
DOI: 10.4230/LIPIcs.CCC.2026
LIPIcs, Volume 383, CCC 2026, Complete Volume

Authors: Dana Moshkovitz

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
LIPIcs, Volume 383, CCC 2026, Complete Volume
Cite as

41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 1-1054, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Proceedings{moshkovitz:LIPIcs.CCC.2026,
  title =	{{LIPIcs, Volume 383, CCC 2026, Complete Volume}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{1--1054},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026},
  URN =		{urn:nbn:de:0030-drops-273215},
  doi =		{10.4230/LIPIcs.CCC.2026},
  annote =	{Keywords: LIPIcs, Volume 383, CCC 2026, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CCC.2026.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dana Moshkovitz

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

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

41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{moshkovitz:LIPIcs.CCC.2026.0,
  author =	{Moshkovitz, Dana},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.0},
  URN =		{urn:nbn:de:0030-drops-273205},
  doi =		{10.4230/LIPIcs.CCC.2026.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.1
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH

Authors: Rishav Gupta, Bingkai Lin, and Xin Zheng

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (ETH), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem (MLD) and the parameterized Nearest Codeword Problem (NCP) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of (c, s)-Gap MAXLIN established in [Nir Bitansky et al., 2024]. We transform a (c, s)-Gap MAXLIN instance into an instance of γ-Gap k-MLD via a novel combinatorial object that we call a cover family. We provide both a randomized construction of the required cover families and a subsequent derandomization. Prior to our work, n^{Ω(k)} hardness for constant-factor approximation was only shown under the randomized Gap Exponential Time Hypothesis Gap-ETH [Pasin Manurangsi, 2020], which is a much stronger assumption than ETH. Under ETH, the strongest known lower bound was n^{Ω(k/poly log k)} due to [Mitali Bafna et al., 2025]. Unlike previous approaches that rely on reductions from the hardness of approximating 2-CSP, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.
Cite as

Rishav Gupta, Bingkai Lin, and Xin Zheng. Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.CCC.2026.1,
  author =	{Gupta, Rishav and Lin, Bingkai and Zheng, Xin},
  title =	{{Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.1},
  URN =		{urn:nbn:de:0030-drops-270439},
  doi =		{10.4230/LIPIcs.CCC.2026.1},
  annote =	{Keywords: Maximum Likelihood Decoding, Parameterized Complexity, Hardness of Approximation, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.2
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties

Authors: Aaron Putterman, Salil Vadhan, and Vadim Zaripov

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound over exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1) O(log(m))-wise independence suffices for preserving connectivity when sampling at rate 1/2 in a graph with minimum cut ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 2) O(log(m))-wise (1/poly(m))-almost independence suffices for ensuring cycle-freeness when sampling at rate 1/2 in a graph with minimum cycle length ≥ κ log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant κ). 3) If we relax to arbitrary distributions, we show there is an explicit distribution with marginals ≤ 1/2 generated using O(log(m)log log(m)) random bits such that in a graph with minimum cut ≥ κ log(m) (for a sufficiently large constant κ), a sample from the distribution has is still connected with probability 1- 1/poly(m). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.
Cite as

Aaron Putterman, Salil Vadhan, and Vadim Zaripov. Bounded-Independence Sampling of Edges for Combinatorial Graph Properties. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{putterman_et_al:LIPIcs.CCC.2026.2,
  author =	{Putterman, Aaron and Vadhan, Salil and Zaripov, Vadim},
  title =	{{Bounded-Independence Sampling of Edges for Combinatorial Graph Properties}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.2},
  URN =		{urn:nbn:de:0030-drops-270444},
  doi =		{10.4230/LIPIcs.CCC.2026.2},
  annote =	{Keywords: Graphs, random sampling}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.3
Improved Bounds on the Space Complexity of Circuit Evaluation

Authors: Yakov Shalunov

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Williams (STOC 2025) recently proved that time-t multitape Turing machines can be simulated using O(√{t log t}) space using the Cook-Mertz (STOC 2024) tree evaluation procedure. As Williams notes, applying this result to fast algorithms for the circuit value problem implies an O(√s ⋅ polylog s) space algorithm for evaluating circuits with s gates. In this work, we provide a direct reduction from circuit value to tree evaluation without passing through Turing machines, simultaneously improving the bound to O(√{s log s}) space and providing a proof with fewer layers of abstraction. This result can be thought of as a "sibling" result to Williams' for circuit complexity instead of time; in particular, using the fact that time-t Turing machines have size O(t log t) circuits, we can recover a slightly weakened version of Williams' result, simulating time-t machines in space O(√t log t).
Cite as

Yakov Shalunov. Improved Bounds on the Space Complexity of Circuit Evaluation. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shalunov:LIPIcs.CCC.2026.3,
  author =	{Shalunov, Yakov},
  title =	{{Improved Bounds on the Space Complexity of Circuit Evaluation}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.3},
  URN =		{urn:nbn:de:0030-drops-270451},
  doi =		{10.4230/LIPIcs.CCC.2026.3},
  annote =	{Keywords: circuit value problem CVP, space complexity, tree evaluation problem}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.4
Probabilistically Checking Quantum Proofs, with Interaction

Authors: Baocheng Sun and Thomas Vidick

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protoocls. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 1 and soundness bounded away from 1 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Previous works in the information-theoretic setting either considered two isolated but entangled quantum provers or quantum verifiers whose effort in a single round is small but remains polynomial when aggregated across all rounds of the protocol. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.
Cite as

Baocheng Sun and Thomas Vidick. Probabilistically Checking Quantum Proofs, with Interaction. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 4:1-4:49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.CCC.2026.4,
  author =	{Sun, Baocheng and Vidick, Thomas},
  title =	{{Probabilistically Checking Quantum Proofs, with Interaction}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{4:1--4:49},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.4},
  URN =		{urn:nbn:de:0030-drops-270463},
  doi =		{10.4230/LIPIcs.CCC.2026.4},
  annote =	{Keywords: quantum complexity theory, quantum probabilistically checkable proofs, interactive oracle proofs, quantum locally testable codes, QMA}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.5
Condensing and Extracting Against Online Adversaries

Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
We investigate the tasks of deterministically condensing and extracting randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective random sources for which it is known that extraction is impossible in many parameter regimes [AORSV, EUROCRYPT'20]. A (g,𝓁)-oNOSF source is a sequence of 𝓁 blocks 𝐗 = (𝐗₁, … , 𝐗_{𝓁})∼ ({0, 1}ⁿ)^{𝓁}, where at least g of the blocks are good (are independent and have some min-entropy), and the remaining bad blocks are controlled by an online adversary where each bad block can be arbitrarily correlated with any block that appears before it. The existence of condensers (in regimes where extraction is impossible) was recently studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of g and 𝓁, and they showed the existence of condensers matching the impossibility results in the special case when n is exponential in 𝓁 (i.e., the setting of few blocks of large length). In this work, not only do we construct the first explicit condensers matching the existential results of [CGR, FOCS'24], but we make a doubly exponential improvement by handling the case when n is only polylogarithmic in 𝓁. We also obtain a much improved explicit construction for transforming low-entropy oNOSF sources (where the good blocks only have min-entropy, as opposed to being uniform) into uniform oNOSF sources. As our next result, we essentially resolve the question of the existence of condensers for oNOSF sources by showing the existence of condensers in almost all parameter regimes, even when n is a large enough constant and 𝓁 is growing. We find interesting connections and applications of our results on condensers to collective coin flipping and collective sampling, problems that are well-studied in fault-tolerant distributed computing. We use our condensers to provide very simple protocols for these problems. Next, we turn to understanding the possibility of extraction from oNOSF sources. For proving lower bounds, we introduce and initiate a systematic study of a new, natural notion of the influence of functions, which we call online influence, and establish tight bounds on the total online influence of functions, which imply extraction lower bounds. Lastly, we give explicit extractor constructions for oNOSF sources using novel connections to leader election protocols, and we further construct the required leader election protocols. These extractor constructions achieve parameters that go beyond the standard resilient functions of [AL, Combinatorica'93].
Cite as

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio. Condensing and Extracting Against Online Adversaries. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2026.5,
  author =	{Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam and Servedio, Rocco A.},
  title =	{{Condensing and Extracting Against Online Adversaries}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.5},
  URN =		{urn:nbn:de:0030-drops-270477},
  doi =		{10.4230/LIPIcs.CCC.2026.5},
  annote =	{Keywords: collective coin flipping, leader election, Boolean function analysis, fault tolerant distributed computing, full information model, resilient function, pseudorandomness, condensers, adversarial sources, non-oblivious symbol fixing sources, Chor-Goldreich sources}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.6
Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Authors: Yang P. Liu, Shachar Lovett, and Kunal Mittal

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
We prove that for any 3-player game G, whose query distribution has the same support as the GHZ game (i.e., all x,y,z ∈ {0,1} satisfying x+y+z = 0 (mod 2)), the value of the n-fold parallel repetition of G decays exponentially fast: val(G^{⊗ n}) ≤ exp(-n^c) for all sufficiently large n, where c > 0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε > 0, the probability that the players win at least a (3/4+ε) fraction of the n coordinates is at most exp(-n^c), where c = c(ε) > 0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n^{-Ω(1)}. Our key technical tool is the notion of algebraic spreadness adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.
Cite as

Yang P. Liu, Shachar Lovett, and Kunal Mittal. Improved Parallel Repetition for GHZ-Supported Games via Spreadness. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.CCC.2026.6,
  author =	{Liu, Yang P. and Lovett, Shachar and Mittal, Kunal},
  title =	{{Improved Parallel Repetition for GHZ-Supported Games via Spreadness}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.6},
  URN =		{urn:nbn:de:0030-drops-270486},
  doi =		{10.4230/LIPIcs.CCC.2026.6},
  annote =	{Keywords: Parallel Repetition, GHZ Game, Algebraic Spreadness}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.7
The Log-Rank Conjecture: New Equivalent Formulations

Authors: Lianna Hambardzumyan, Shachar Lovett, and Morgan Shirley

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the rank and partitioning number of a Boolean matrix are quasi-polynomially related. We propose a relaxed but still equivalent version of the conjecture based on a new matrix parameter, signed rectangle rank: the minimum number of all-1 rectangles needed to express the Boolean matrix as a ± 1-sum. Signed rectangle rank lies between rank and partition number, and our main result shows that it is in fact equivalent to rank up to a logarithmic factor. Additionally, we extend the main result to tensors. This reframes the log-rank conjecture as: can every signed decomposition of a Boolean matrix be made positive with only quasi-polynomial blowup? As an application, we prove an equivalence between the log-rank conjecture and a conjecture of Lovett and Singer–Sudan on cross-intersecting set systems.
Cite as

Lianna Hambardzumyan, Shachar Lovett, and Morgan Shirley. The Log-Rank Conjecture: New Equivalent Formulations. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 7:1-7:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hambardzumyan_et_al:LIPIcs.CCC.2026.7,
  author =	{Hambardzumyan, Lianna and Lovett, Shachar and Shirley, Morgan},
  title =	{{The Log-Rank Conjecture: New Equivalent Formulations}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{7:1--7:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.7},
  URN =		{urn:nbn:de:0030-drops-270495},
  doi =		{10.4230/LIPIcs.CCC.2026.7},
  annote =	{Keywords: cross-intersecting set systems, Log-rank conjecture, monochromatic rectangle, partition number}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.8
Efficient Adversaries

Authors: Erfan Khaniki, Ján Pich, and Dmitry Sokolov

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
The size of Frege proofs can be characterized in terms of prover-adversary games of Pudlák and Buss. We consider a generalization of prover-adversary games to many standard proof systems and show that some of the major proof complexity lower bounds such as the constant-depth Frege lower bound for the pigeonhole principle based on the method of k-evaluations, the Resolution lower bound for the weak pigeonhole principle based on the method of pseudo-width and Razborov’s Res(k) lower bound for Nisan-Wigderson generators based on expansion and a width lower bound (which is used to derive the Res(k)-hardness of formulas expressing circuit lower bounds) are constructive in the sense that they yield efficient algorithms computing winning strategies of adversaries in the generalized games. This is in contrast with our second result saying that if (a) such a constructive lower bound exists for Extended Frege system EF for formulas expressing succinct circuit lower bounds for SAT and (b) EF is strong enough to prove efficiently the correctness of anticheckers for SAT, then it is easy to separate the canonical pair of EF.
Cite as

Erfan Khaniki, Ján Pich, and Dmitry Sokolov. Efficient Adversaries. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 8:1-8:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khaniki_et_al:LIPIcs.CCC.2026.8,
  author =	{Khaniki, Erfan and Pich, J\'{a}n and Sokolov, Dmitry},
  title =	{{Efficient Adversaries}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{8:1--8:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.8},
  URN =		{urn:nbn:de:0030-drops-270508},
  doi =		{10.4230/LIPIcs.CCC.2026.8},
  annote =	{Keywords: proof complexity, circuit complexity, lower bounds, barriers, truth-table formula, pigeonhole principle}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.9
Hardness of Computing Nondeterministic Kolmogorov Complexity

Authors: Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of NP is a central research direction. A longstanding open problem in this area is to establish the NP-hardness of MINKT (Ker-I Ko, 1991 [Ker{-}I Ko, 1991]), the problem of estimating time-bounded Kolmogorov complexity. We contribute to this research direction by studying nK^t, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [Buhrman et al., 2001]. Let MINnKT denote the task of estimating nK^t(x) of a given input string x. We prove that MINnKT ∈ BPP if and only if NP ⊆ BPP. This can be interpreted as a solution to Ko’s question in the setting of nondeterministic time-bounded Kolmogorov complexity. Crucial to the proof of this result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called pnK^t. This measure can be seen as an extension of pK^t complexity [Halley Goldberg et al., 2022] obtained by replacing 𝖪^t with nK^t. We establish unconditionally that pnK^t has nearly all key properties of (time-unbounded) Kolmogorov complexity, such as language compression, conditional coding, and a form of symmetry of information. Finally, we show that the corresponding meta-computational problem MINpnKT also captures the hardness of NP, and that extending this result to the closely related problem Gap-MINpnKT would imply the exclusion of PH-Heuristica.
Cite as

Jinqiao Hu, Zhenjian Lu, and Igor C. Oliveira. Hardness of Computing Nondeterministic Kolmogorov Complexity. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 9:1-9:50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.CCC.2026.9,
  author =	{Hu, Jinqiao and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Hardness of Computing Nondeterministic Kolmogorov Complexity}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{9:1--9:50},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.9},
  URN =		{urn:nbn:de:0030-drops-270516},
  doi =		{10.4230/LIPIcs.CCC.2026.9},
  annote =	{Keywords: meta-complexity, average-case complexity, Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.10
The Rate-Immediacy Barrier in Explicit Tree Code Constructions

Authors: Gil Cohen, Leonard J. Schulman, and Piyush Srivastava

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of asymptotically good tree codes has remained a notorious challenge. A work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, Cohen, and Yankovitz (STOC 2022) have achieved codes with rate Ω(1/log log n), exponentially improving upon the original rate Ω(1/log n) construction of Evans, Klugerman and Schulman from 1994. All of these constructions rely, at least in part, on increasingly sophisticated methods of combining (block) error-correcting codes. In this work, we identify a fundamental barrier to constructing tree codes using known techniques. We introduce a key property which we call immediacy, that, while not required by the original definition of tree codes, is shared by all known constructions and inherently arises in recursive combinations of error-correcting codes. Our main technical contribution is the proof of a rate–immediacy trade-off, which, in particular, implies that any tree code with constant distance and non-trivial immediacy must necessarily have vanishing rate. By applying our rate-immediacy trade-off to existing constructions, we establish that their known rate analyses are essentially optimal given their actual error-correction properties. More broadly, our work highlights the need for fundamentally new ideas - beyond the recursive use of error-correcting codes - to achieve substantial progress in explicitly constructing asymptotically good tree codes.
Cite as

Gil Cohen, Leonard J. Schulman, and Piyush Srivastava. The Rate-Immediacy Barrier in Explicit Tree Code Constructions. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2026.10,
  author =	{Cohen, Gil and Schulman, Leonard J. and Srivastava, Piyush},
  title =	{{The Rate-Immediacy Barrier in Explicit Tree Code Constructions}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.10},
  URN =		{urn:nbn:de:0030-drops-270522},
  doi =		{10.4230/LIPIcs.CCC.2026.10},
  annote =	{Keywords: Tree codes, Information Theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.11
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?

Authors: Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
The complexity of bilinear maps (equivalently, of 3-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for 3-mode tensors, this correspondence breaks down for d ≥ 4 modes. As a result, the complexity of d-mode tensors for larger fixed d remains poorly understood, despite its relevance, e.g., in fine-grained complexity. Our paper explores this intermediate regime. First, we give a "graph-theoretic" proof of Strassen’s 2ω/3 bound on the asymptotic rank exponent of 3-mode tensors. Our proof directly generalizes to an upper bound of (d-1)ω/3 for d-mode tensors. Using refined techniques available only for d ≥ 4 modes, we improve this bound beyond the current state of the art for ω. We also obtain a bound of d/2+1 on the asymptotic exponent of circuit complexity of generic d-mode tensors and optimized bounds for d ∈ {4,5}. To the best of our knowledge, asymptotic circuit complexity (rather than rank) of tensors has not been studied before. To obtain a robust theory, we first ask whether low complexity of T and U imply low complexity of their Kronecker product T ⊗ U. While this crucially holds for rank (and thus for circuit complexity in 3 modes), we show that assumptions from fine-grained complexity rule out such a submultiplicativity for the circuit complexity of tensors with many modes. In particular, assuming the Hyperclique Conjecture, this failure occurs already for d = 8 modes. Nevertheless, we can salvage a restricted notion of submultiplicativity. From a technical perspective, our proofs heavily make use of the graph tensors T_H, as employed by Christandl and Zuiddam (Comput. Complexity 28 (2019) 27-56) and Christandl, Vrana and Zuiddam (Comput. Complexity 28 (2019) 57-111), whose modes correspond to the vertices of undirected graphs H. We make the simple but conceptually crucial observation that Kronecker products T_G ⊗ T_H are isomorphic to T_{G+H}, and that G and H may also be fractional graphs. By asymptotically converting generic tensors to specific graph tensors, we can use nontrivial results from algorithmic graph theory to study the rank and complexity of d-mode tensors for fixed d.
Cite as

Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang. Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.CCC.2026.11,
  author =	{Brand, Cornelius and Curticapean, Radu and Kaski, Petteri and Li, Baitian and Orzel, Ian and Seppelt, Tim and Wang, Jiaheng},
  title =	{{Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.11},
  URN =		{urn:nbn:de:0030-drops-270530},
  doi =		{10.4230/LIPIcs.CCC.2026.11},
  annote =	{Keywords: arithmetic circuits, tensor rank, bilinear complexity, graph tensors}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.12
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions

Authors: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, and Yu-Ching Shen

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
The local Hamiltonian (LH) problem is the canonical QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on n qubits cannot be solved classically in time O(2^{(1-ε)n}) for any ε > 0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2^{(1-ε)n/2}) for any ε > 0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(√{2ⁿ}) time for an arbitrary 1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a T-time quantum circuit acting on N qubits into a (d+1)-local Hamiltonian acting on N+O(T^{1/d}) qubits. This improves the standard construction based on the unary clock, which uses N+O(T) qubits.
Cite as

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, and Yu-Ching Shen. Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 12:1-12:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.CCC.2026.12,
  author =	{Chia, Nai-Hui and Hasegawa, Atsuya and Le Gall, Fran\c{c}ois and Shen, Yu-Ching},
  title =	{{Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{12:1--12:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.12},
  URN =		{urn:nbn:de:0030-drops-270543},
  doi =		{10.4230/LIPIcs.CCC.2026.12},
  annote =	{Keywords: Fine-grain complexity, SETH, QSETH, Local Hamiltonian problem, Quantum partition problem}
}
  • Refine by Type
  • 72 Document/PDF
  • 15 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 46 2026
  • 14 2025
  • 1 2024
  • 3 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 13 Moshkovitz, Dana
  • 6 Cook, Joshua
  • 3 Lovett, Shachar
  • 3 Shpilka, Amir
  • 3 Zuckerman, David
  • Show More...

  • Refine by Series/Journal
  • 72 LIPIcs

  • Refine by Classification
  • 12 Theory of computation → Pseudorandomness and derandomization
  • 11 Theory of computation → Algebraic complexity theory
  • 9 Theory of computation → Error-correcting codes
  • 6 Theory of computation → Circuit complexity
  • 6 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 Derandomization
  • 3 Pseudorandomness
  • 3 TFNP
  • 2 Approximation Algorithms
  • 2 Boolean function analysis
  • 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