55 Search Results for "Micali, Silvio"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.97
One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

Authors: Yanyi Liu and Rafael Pass

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

Abstract
We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, MINK^{poly} - that is, determining whether a string is "structured" (i.e., K^t(x) < n-1) or "random" (i.e., K^{poly(t)} ≥ n-1) - suffices to imply the existence of one-way functions (OWF). Liu-Pass (CRYPTO'25) recently showed that worst-case hardness of a boundary version of MINK^{poly} - where, roughly speaking, the goal is to decide whether given an instance x, (a) x is K^poly-random (i.e., K^{poly(t)}(x) ≥ n-1), or just close to K^poly-random (i.e., K^{t}(x) < n-1 but K^{poly(t)} > n - log n) - characterizes OWF, but with either of the following caveats (1) considering a non-standard notion of probabilistic K^t, as opposed to the standard notion of K^t, or (2) assuming somewhat strong, and non-standard, derandomization assumptions. In this paper, we present an alternative method for establishing their result which enables significantly weakening the caveats. First, we show that boundary hardness of the more standard randomized K^t problem suffices (where randomized K^t(x) is defined just like K^t(x) except that the program generating the string x may be randomized). As a consequence of this result, we can provide a characterization also in terms of just "plain" K^t under the most standard derandomization assumption (used to derandomize just BPP into P) - namely E ̸ ⊆ ioSIZE[2^{o(n)}]. Our proof relies on language compression schemes of Goldberg-Sipser (STOC'85); using the same technique, we also present the the first worst-case to average-case reduction for the exact MINK^{poly} problem (under the same standard derandomization assumption), improving upon Hirahara’s celebrated results (STOC'18, STOC'21) that only applied to a gap version of the MINK^{poly} problem, referred to as GapMINK^{poly}, where the goal is to decide whether K^t(x) ≤ n-O(log n)) or K^{poly(t)}(x) ≥ n-1 and under the same derandomization assumption.
Cite as

Yanyi Liu and Rafael Pass. One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 97:1-97:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2026.97,
  author =	{Liu, Yanyi and Pass, Rafael},
  title =	{{One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{97:1--97:19},
  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.97},
  URN =		{urn:nbn:de:0030-drops-253849},
  doi =		{10.4230/LIPIcs.ITCS.2026.97},
  annote =	{Keywords: One-way functions, Time-Bounded Kolmogorov Complexity, Worst-case to Average-case Reductions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.6
Model-Generic Incrementally Verifiable Computation from Updatable BARGs

Authors: Eden Aldema Tshuva and Rotem Oshman

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

Abstract
Incrementally verifiable computation (IVC) is a computationally sound proof system that allows a prover to certify the correctness of a long or ongoing computation in an incremental manner, by repeatedly updating a proof certifying the computation so far. Updating the proof does not require access to the entire trace of the computation, which makes the IVC-prover memory efficient. Recently, such schemes were constructed for deterministic Turing machines from standard cryptographic assumptions (Paneth and Pass, FOCS 2022, and Devadas et al., FOCS 2022). In this work we generalize and extend IVC to support incremental certification and verifiability of a large set of computation models, focusing on distributed and online computation. This allows distributed algorithms to efficiently certify their own execution using low memory and communication overhead. We construct IVC for a variety of computation models by proving one generic lifting theorem from a classical (non-incremental) delegation scheme (also known as SNARG) into full-fledged IVC, while preserving the delegation scheme’s succinctness properties (up to an additive factor which is polynomial in the security parameter and independent of the size of the computation). Using this lifting theorem, we obtain IVC for the following computation models: - RAM and exclusive-read exclusive-write (EREW) PRAM algorithms, using existing delegation schemes for these models. - Streaming algorithms, using the natural memory-efficiency properties of the model. - Massively parallel computation (MPC). Notably, in this model, memory efficiency is a critical bottleneck: the machines participating in an MPC algorithm usually cannot store the entire trace of their computation. Thus, certifying MPC algorithms naturally benefits from IVC. Moreover, since prior to our work, no delegation scheme for this model was known, we also construct a delegation scheme for one-round massively parallel computations, and then apply our lifting theorem to it. - Distributed graph algorithms, using existing distributed delegation schemes (also known as locally verifiable distributed SNARGs). Here, in order to use our lifting theorem we have to first make some observations about the verification procedure of these existing schemes. At the heart of this work is a new abstraction, updatable batch arguments for NP (UpBARGs), which we define and construct. Standard BARGs allow one to prove a batch of k NP-statements using a proof whose length barely grows with k; however, the statements and their witnesses must all be known in advance. In contrast, UpBARGs support adding statements and witnesses on the fly, making them a flexible tool for constructing IVC across different computational models.
Cite as

Eden Aldema Tshuva and Rotem Oshman. Model-Generic Incrementally Verifiable Computation from Updatable BARGs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.ITCS.2026.6,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{Model-Generic Incrementally Verifiable Computation from Updatable BARGs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{6:1--6:22},
  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.6},
  URN =		{urn:nbn:de:0030-drops-252931},
  doi =		{10.4230/LIPIcs.ITCS.2026.6},
  annote =	{Keywords: incrementally verifiable computation, massively parallel computation, streaming, parallel RAM, batch arguments, SNARG}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.52
Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

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

Abstract
In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52: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.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.60
Total Search Problems in ZPP

Authors: Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan

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

Abstract
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code: - We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. - We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007). - Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.
Cite as

Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan. Total Search Problems in ZPP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 60:1-60:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.ITCS.2026.60,
  author =	{Fleming, Noah and Grosser, Stefan and Jain, Siddhartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang},
  title =	{{Total Search Problems in ZPP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{60:1--60:26},
  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.60},
  URN =		{urn:nbn:de:0030-drops-253473},
  doi =		{10.4230/LIPIcs.ITCS.2026.60},
  annote =	{Keywords: TFNP, lossy code, randomized proof systems, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.24
Unitary Complexity and the Uhlmann Transformation Problem

Authors: John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen

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

Abstract
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann’s theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
Cite as

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.ITCS.2026.24,
  author =	{Bostanci, John and Efron, Yuval and Metger, Tony and Poremba, Alexander and Qian, Luowen and Yuen, Henry},
  title =	{{Unitary Complexity and the Uhlmann Transformation Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{24:1--24:17},
  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.24},
  URN =		{urn:nbn:de:0030-drops-253111},
  doi =		{10.4230/LIPIcs.ITCS.2026.24},
  annote =	{Keywords: Uhlmann’s theorem, unitary complexity theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.20
Samplability Makes Learning Easier

Authors: Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan

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

Abstract
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions - even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show that its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.
Cite as

Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan. Samplability Makes Learning Easier. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.ITCS.2026.20,
  author =	{Blanc, Guy and Koch, Caleb and Lange, Jane and Strassle, Carmen and Tan, Li-Yang},
  title =	{{Samplability Makes Learning Easier}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{20:1--20:12},
  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.20},
  URN =		{urn:nbn:de:0030-drops-253071},
  doi =		{10.4230/LIPIcs.ITCS.2026.20},
  annote =	{Keywords: PAC learning, Samplable distributions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.72
Forrelation Is Extremally Hard

Authors: Uma Girish and Rocco Servedio

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

Abstract
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to n-bit Boolean functions f and g, the goal is to estimate the Forrelation function forr(f,g), which measures the correlation between g and the Fourier transform of f. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely (f,g) with forr(f,g) = 1 and forr(f,g) = -1. We show that this problem can be solved with one quantum query and success probability one, yet requires Ω̃(2^{n/4}) classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs f,g are computable by small classical circuits and show classical hardness under cryptographic assumptions.
Cite as

Uma Girish and Rocco Servedio. Forrelation Is Extremally Hard. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.ITCS.2026.72,
  author =	{Girish, Uma and Servedio, Rocco},
  title =	{{Forrelation Is Extremally Hard}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{72:1--72:22},
  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.72},
  URN =		{urn:nbn:de:0030-drops-253594},
  doi =		{10.4230/LIPIcs.ITCS.2026.72},
  annote =	{Keywords: Forrelation, exact quantum, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.111
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

Authors: Hanlin Ren, Yichuan Wang, and Yan Zhong

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

Abstract
Given a circuit G: {0, 1}ⁿ → {0, 1}^m with m > n, the range avoidance problem (Avoid) asks to output a string y ∈ {0, 1}^m that is not in the range of G. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of proof complexity generators - circuits G: {0, 1}ⁿ → {0, 1}^m where m > n but for every y ∈ {0, 1}^m, it is infeasible to prove the statement "y ̸ ∈ Range(G)" in a given propositional proof system. This paper connects these two problems with the existence of demi-bits generators, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM '97). - We show that the existence of demi-bits generators implies Avoid is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC '24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich’s PRG, we prove the hardness of Avoid even when the instances are constant-degree polynomials over 𝔽₂. - We show that the dual weak pigeonhole principle is unprovable in Cook’s theory PV₁ under the existence of demi-bits generators secure against AM/_{O(1)}, thereby separating Jeřábek’s theory APC₁ from PV₁. Previously, Ilango, Li, and Williams (STOC '23) obtained the same separation under different (and arguably stronger) cryptographic assumptions. - We transform demi-bits generators to proof complexity generators that are pseudo-surjective in certain parameter regime. Pseudo-surjectivity is the strongest form of hardness considered in the literature for proof complexity generators. Our constructions are inspired by the recent breakthroughs on the hardness of Avoid by Ilango, Li, and Williams (STOC '23) and Chen and Li (STOC '24). We use randomness extractors to significantly simplify the construction and the proof.
Cite as

Hanlin Ren, Yichuan Wang, and Yan Zhong. Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 111:1-111:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.ITCS.2026.111,
  author =	{Ren, Hanlin and Wang, Yichuan and Zhong, Yan},
  title =	{{Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{111:1--111:25},
  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.111},
  URN =		{urn:nbn:de:0030-drops-253982},
  doi =		{10.4230/LIPIcs.ITCS.2026.111},
  annote =	{Keywords: Range Avoidance, Proof Complexity Generators}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.18
Interactive Proofs for Distribution Testing with Conditional Oracles

Authors: Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar

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

Abstract
We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompanied by notable progress (e.g., Herman and Rothblum, STOC 2022, FOCS 2023; Herman, RANDOM 2024). In this model, a data-poor verifier determines whether a probability distribution has a property of interest by interacting with an all-powerful, data-rich but untrusted prover bent on convincing them that it has the property. While prior work gave sample-, time-, and communication-efficient protocols for testing and estimating a range of distribution properties, they all suffer from an inherent issue: for most interesting properties of distributions over a domain of size N, the verifier must draw at least Ω(√N) samples of its own. While sublinear in N, this is still prohibitive for large domains encountered in practice. In this work, we circumvent this limitation by augmenting the verifier with the ability to perform an exponentially smaller number of more powerful (but reasonable) pairwise conditional queries, effectively enabling them to perform "local comparison checks" of the prover’s claims. We systematically investigate the landscape of interactive proofs in this new setting, giving poly-logarithmic query and sample protocols for (tolerantly) testing all label-invariant properties, thus demonstrating exponential savings without compromising on communication, for this large and fundamental class of testing tasks.
Cite as

Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar. Interactive Proofs for Distribution Testing with Conditional Oracles. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.ITCS.2026.18,
  author =	{Biswas, Ari and Bun, Mark and Canonne, Cl\'{e}ment L. and Sivakumar, Satchit},
  title =	{{Interactive Proofs for Distribution Testing with Conditional Oracles}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{18:1--18:13},
  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.18},
  URN =		{urn:nbn:de:0030-drops-253059},
  doi =		{10.4230/LIPIcs.ITCS.2026.18},
  annote =	{Keywords: Distribution Testing, Interactive Proofs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.7
Mobile Byzantine Agreement in a Trusted World

Authors: Bo Pan and Maria Potop-Butucaru

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on two representative models: Garay’s and Buhrman’s models. In Garay’s model, when a process has been left by the Byzantine agent, it enters a cured state, is aware of its condition, and can remain silent for a round to prevent the dissemination of incorrect information. In Buhrman’s model, a Byzantine agent moves together with the message. It has been shown that solving Byzantine Agreement requires at least 4t + 1 processes in Garay’s model, and at least 3t + 1 in Buhrman’s model. In this paper, we aim to increase the tolerance to mobile Byzantine agents by integrating a trusted counter abstraction into both models. This abstraction prevents nodes from equivocating. In the new models, we prove that at least 3t+1, respectively 2t+1 processors are needed to tolerate t mobile Byzantine agents. Furthermore, we propose novel Mobile Byzantine Agreement algorithms that match these new lower bounds for both Garay’s and Buhrman’s models, achieving agreement in 𝒪(n) synchronous rounds.
Cite as

Bo Pan and Maria Potop-Butucaru. Mobile Byzantine Agreement in a Trusted World. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pan_et_al:LIPIcs.OPODIS.2025.7,
  author =	{Pan, Bo and Potop-Butucaru, Maria},
  title =	{{Mobile Byzantine Agreement in a Trusted World}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.7},
  URN =		{urn:nbn:de:0030-drops-251809},
  doi =		{10.4230/LIPIcs.OPODIS.2025.7},
  annote =	{Keywords: Byzantine Agreement, Mobile Faults, Trusted Abstractions}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.8
Weaker Assumptions for Asymmetric Trust

Authors: Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In distributed systems with asymmetric trust, each participant is free to make its own trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric quorum systems and threshold models, where trust assumptions are uniformly shared among participants. Fundamental problems like reliable broadcast and consensus are unsolvable in the asymmetric model if quorum systems satisfy only the classical properties of consistency and availability. Existing approaches overcome this by introducing stronger assumptions. We show that some of these assumptions are overly restrictive, so much so that they effectively eliminate the benefits of asymmetric trust. To address this, we propose a new approach to characterize asymmetric problems and, building upon it, present algorithms for reliable broadcast and consensus that require weaker assumptions than previous solutions. Our methods are general and can be extended to other core problems in systems with asymmetric trust.
Cite as

Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis. Weaker Assumptions for Asymmetric Trust. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2025.8,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Kamp, Simon Holmgaard and Villacis, Juan},
  title =	{{Weaker Assumptions for Asymmetric Trust}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.8},
  URN =		{urn:nbn:de:0030-drops-251812},
  doi =		{10.4230/LIPIcs.OPODIS.2025.8},
  annote =	{Keywords: Asymmetric Trust, Quorum Systems, Reliable Broadcast, Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.9
Contention-Aware Cooperation

Authors: Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is crucial in fault-tolerant distributed computing. Considering n-process asynchronous message-passing systems where some processes may be Byzantine, this paper introduces a novel cooperation abstraction, Contention-Aware Cooperation (CAC). While Reliable Broadcast is a one-to-n cooperation abstraction and Consensus is an n-to-n cooperation abstraction, CAC is a d-to-n cooperation abstraction where d (1 ≤ d ≤ n) varies with each run and remains unknown to the processes. Correct processes accept the same set of 𝓁 pairs ⟨ v,i ⟩ (v is the value proposed by p_i) from the d proposer processes, where 1 ≤ 𝓁 ≤ d and (as d) 𝓁 remains unknown to the processes (except in specific cases). Those 𝓁 values are accepted one at a time, potentially in different orders at each process. In addition, CAC provides each process with an imperfect oracle that provides insights into the values that they may accept in the future. Interestingly, the CAC abstraction is particularly efficient in favorable circumstances, when the oracle becomes accurate, which processes can detect. To illustrate its practical utility, the paper details two applications leveraging CAC: a fast consensus implementation optimized for low contention (named Cascading Consensus), and a novel naming problem that can be solved under full asynchrony. All algorithms presented require signatures.
Cite as

Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani. Contention-Aware Cooperation. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2025.9,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gestin, Mathieu and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Contention-Aware Cooperation}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.9},
  URN =		{urn:nbn:de:0030-drops-251823},
  doi =		{10.4230/LIPIcs.OPODIS.2025.9},
  annote =	{Keywords: Agreement, Asynchronous message-passing system, Byzantine processes, Conflict detection, Consensus, Cooperation abstraction, Distributed computing, Fault tolerance, Optimistically terminating consensus, Short-naming}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.16
Asynchronous Approximate Agreement with Quadratic Communication

Authors: Mose Mizrahi Erbes and Roger Wattenhofer

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
We study approximate agreement in an asynchronous network of n parties, up to t of which are byzantine. This an agreement task where the parties obtain approximately equal inputs in the convex hull of their inputs. In an asynchronous network, it can be solved with the optimal resilience t < n/3 by forcing the parties to reliably broadcast their messages and thus preventing inconsistent byzantine behavior. This costs Θ(n²) messages per reliable broadcast, or Θ(n³) messages per protocol iteration. In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against t < n/3 faults with quadratic communication. In a tree with the maximum degree Δ and the centroid decomposition height h, we achieve edge agreement (agreement on two adjacent vertices) in at most 6h + 1 rounds with 𝒪(n²) messages of size 𝒪(log Δ + log h) per round. We do this by designing a 6-round multivalued 2-graded consensus protocol and using it to construct a recursive edge agreement protocol. Then, we achieve edge agreement in the infinite path ℤ, again by using 2-graded consensus. Finally, we show that our edge agreement protocol enables approximate agreement in ℝ (with outputs that are at most some small parameter ε > 0 apart) in 6log₂M/(ε) + 𝒪(log log M/(ε)) rounds with 𝒪(n²) messages of size 𝒪(log log M/(ε)) per round, where M is the maximum non-byzantine input magnitude.
Cite as

Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous Approximate Agreement with Quadratic Communication. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mizrahierbes_et_al:LIPIcs.OPODIS.2025.16,
  author =	{Mizrahi Erbes, Mose and Wattenhofer, Roger},
  title =	{{Asynchronous Approximate Agreement with Quadratic Communication}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{16:1--16:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.16},
  URN =		{urn:nbn:de:0030-drops-251890},
  doi =		{10.4230/LIPIcs.OPODIS.2025.16},
  annote =	{Keywords: Approximate agreement, byzantine fault tolerance, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.24
On Time-Optimal, Fault-Tolerant Algorithms for Connected Consensus Beyond Grade Two

Authors: Alan Ernesto Arteaga Vázquez

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
A common question in the asynchronous model is whether some given notion of agreement between processes is achievable. Usually, we formalise such agreement notions in the form of agreement problems. Some of these problems also receive the name of coordination primitives. Several fault-tolerant algorithms in asynchronous systems rely upon the use of different primitives as building blocks, such as adopt-commit, crusader agreement, or graded broadcast. Recently, the connected consensus problem - a form of agreement over a specific family of graphs parametrised by a positive integer R- was introduced. This problem unifies the three mentioned primitives while extending them for multi-valued inputs. Moreover, the problem is equipped with a security condition called binding, which limits the effect of malicious processes over the decision of correct parties. While fault-tolerant connected consensus algorithms for R = 1 and R = 2 are known, the existence of algorithmic solutions for any positive integer parameter remained an open question. In this work, we introduce a pair of fault-tolerant algorithms for connected consensus when the R parameter is any positive integer. We introduce a crash-resilient algorithm, which is optimal with respect to the maximum number of possible faulty processes. Our second algorithm is resilient to Byzantine failures; whose failure-resilience is optimal for a specific class of algorithms. Both algorithms satisfy the binding property and match the best known time complexities achieved for the R = 1 and R = 2 cases, further achieving time optimality for the general case in the crash-failure setting, and asymptotic time optimality in the Byzantine scenario.
Cite as

Alan Ernesto Arteaga Vázquez. On Time-Optimal, Fault-Tolerant Algorithms for Connected Consensus Beyond Grade Two. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 24:1-24:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arteagavazquez:LIPIcs.OPODIS.2025.24,
  author =	{Arteaga V\'{a}zquez, Alan Ernesto},
  title =	{{On Time-Optimal, Fault-Tolerant Algorithms for Connected Consensus Beyond Grade Two}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{24:1--24:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.24},
  URN =		{urn:nbn:de:0030-drops-251973},
  doi =		{10.4230/LIPIcs.OPODIS.2025.24},
  annote =	{Keywords: Approximate Agreement, Binding, Connected Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.26
Recognizing Hereditary Properties in the Presence of Byzantine Nodes

Authors: David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set B of Byzantine nodes, where |B| is less than a third of the total number of nodes. These nodes have complete knowledge of the network and the state of other nodes, and they conspire to alter the output of the system. The authors addressed the connectivity problem, showing that it is solvable under the promise that either the subgraph induced by the honest nodes is connected, or the graph has 2|B|+1 connected components. In the current work, we continue the study of the Byzantine congested clique model by considering the recognition of other graph properties, specifically hereditary properties. A graph property is hereditary if it is closed under taking induced subgraphs. Examples of hereditary properties include acyclicity, bipartiteness, planarity, and bounded (chromatic, independence) number, etc. For each class of graphs 𝒢 satisfying a hereditary property (a hereditary graph-class), we propose a randomized algorithm which, with high probability, (1) accepts if the input graph G belongs to 𝒢, and (2) rejects if G contains at least |B| + 1 disjoint subgraphs not belonging to 𝒢. The round complexity of our algorithm is 𝒪(((log (|𝒢_n|))/n) +|B|) ⋅polylog(n)) , where 𝒢_n is the set of n-node graphs in 𝒢. Finally, we obtain an impossibility result that proves that our result is tight. Indeed, we consider the hereditary class of acyclic graphs, and we prove that there is no algorithm that can distinguish between a graph being acyclic and a graph having |B| disjoint cycles.
Cite as

David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport. Recognizing Hereditary Properties in the Presence of Byzantine Nodes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cifuentesnunez_et_al:LIPIcs.OPODIS.2025.26,
  author =	{Cifuentes-N\'{u}\~{n}ez, David and Montealegre, Pedro and Rapaport, Ivan},
  title =	{{Recognizing Hereditary Properties in the Presence of Byzantine Nodes}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.26},
  URN =		{urn:nbn:de:0030-drops-251990},
  doi =		{10.4230/LIPIcs.OPODIS.2025.26},
  annote =	{Keywords: Byzantine protocols, congested clique, hereditary properties}
}
  • Refine by Type
  • 55 Document/PDF
  • 53 Document/HTML

  • Refine by Publication Year
  • 16 2026
  • 37 2025
  • 1 2024
  • 1 2017

  • Refine by Author
  • 2 Bostanci, John
  • 2 Efron, Yuval
  • 2 Kuznetsov, Petr
  • 2 Lewis-Pye, Andrew
  • 2 Metger, Tony
  • Show More...

  • Refine by Series/Journal
  • 54 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 14 Theory of computation → Distributed algorithms
  • 6 Security and privacy → Cryptography
  • 6 Security and privacy → Distributed systems security
  • 6 Theory of computation → Cryptographic primitives
  • 3 Security and privacy → Information-theoretic techniques
  • Show More...

  • Refine by Keyword
  • 4 Blockchain
  • 4 Consensus
  • 3 Byzantine Agreement
  • 2 Broadcast
  • 2 Distributed computing
  • 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