185 Search Results for "Papadimitriou, Christos H."

Volume

LIPIcs, Volume 67

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

ITCS 2017, January 9-11, 2017, Berkeley, CA, USA

Editors: Christos H. Papadimitriou

Document
DOI: 10.4230/LIPIcs.STACS.2026.27
The Communication Complexity of Combinatorial Auctions in Graphs

Authors: George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.
Cite as

George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos. The Communication Complexity of Combinatorial Auctions in Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.STACS.2026.27,
  author =	{Christodoulou, George and Koutsoupias, Elias and Kov\'{a}cs, Annam\'{a}ria and Vlachos, Ioannis},
  title =	{{The Communication Complexity of Combinatorial Auctions in Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.27},
  URN =		{urn:nbn:de:0030-drops-255163},
  doi =		{10.4230/LIPIcs.STACS.2026.27},
  annote =	{Keywords: Auctions, Communication Complexity, Mechanism Design, Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.33
Higher Hardness Results for the Reconfiguration of Odd Matchings

Authors: Joseph Dorfer

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the reconfiguration of odd matchings of combinatorial graphs. Odd matchings are matchings that cover all but one vertex of a graph. A reconfiguration step, or flip, is an operation that matches the isolated vertex and, consequently, isolates another vertex. The flip graph of odd matchings is a graph that has all odd matchings of a graph as vertices and an edge between two vertices if their corresponding matchings can be transformed into one another via a single flip. We show that computing the diameter of the flip graph of odd matchings is Π₂^p-hard. This complements a recent result by Wulf [FOCS25] that it is Π₂^p-hard to compute the diameter of the flip graph of perfect matchings where a flip swaps matching edges along a single cycle of unbounded size. Further, we show that computing the radius of the flip graph of odd matchings is Σ₃^p-hard. The respective decision problems for the diameter and the radius are also complete in the respective level of the polynomial hierarchy. This shows that computing the radius of the flip graph of odd matchings is provably harder than computing its diameter, unless the polynomial hierarchy collapses. Finally, we reduce set cover to the problem of finding shortest flip sequences. As a consequence, we show APX-hardness and that the problem cannot be approximated by a sublogarithmic factor. By doing so, we answer a question asked by Aichholzer, Brenner, Dorfer, Hoang, Perz, Rieck, and Verciani [GD25].
Cite as

Joseph Dorfer. Higher Hardness Results for the Reconfiguration of Odd Matchings. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dorfer:LIPIcs.STACS.2026.33,
  author =	{Dorfer, Joseph},
  title =	{{Higher Hardness Results for the Reconfiguration of Odd Matchings}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.33},
  URN =		{urn:nbn:de:0030-drops-255222},
  doi =		{10.4230/LIPIcs.STACS.2026.33},
  annote =	{Keywords: Graph Reconfiguration Problems, Flip Graphs, Polynomial Hierarchy, APX-hardness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.67
Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata

Authors: Filip Mazowiecki, Antoni Puch, and Daniel Smertnig

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In this work we consider two rich subclasses of weighted automata over fields: polynomially ambiguous weighted automata and copyless cost register automata. Primarily we are interested in understanding their expressiveness power. Over the field of rationals and 1-letter alphabets, it is known that the two classes coincide; they are equivalent to linear recurrence sequences (LRS) whose exponential bases are roots of rationals. We develop a tool we call Pumping Sequence Families, which, by exploiting the simple single-letter behaviour of the models, yields two pumping-like results over arbitrary fields with unrestricted alphabets, one for each class. As a corollary of these results, we present examples proving that the two classes become incomparable over the field of rationals with unrestricted alphabets. We complement the results by analysing the zeroness and equivalence problems. For weighted automata (even unrestricted) these problems are well understood: there are polynomial time, and even NC² algorithms. For copyless cost register automata we show that the two problems are PSpace-complete, where the difficulty is to show the lower bound.
Cite as

Filip Mazowiecki, Antoni Puch, and Daniel Smertnig. Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mazowiecki_et_al:LIPIcs.STACS.2026.67,
  author =	{Mazowiecki, Filip and Puch, Antoni and Smertnig, Daniel},
  title =	{{Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{67:1--67:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.67},
  URN =		{urn:nbn:de:0030-drops-255568},
  doi =		{10.4230/LIPIcs.STACS.2026.67},
  annote =	{Keywords: weighted automata, cost register automata, ambiguity, linear recurrence sequences, equivalence problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.59
When Is Local Search Both Effective and Efficient?

Authors: Artem Kaznatcheev and Sofia Vazquez Alferez

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Combinatorial optimization problems implicitly define fitness landscapes that combine the numeric structure of the "fitness" function to be maximized with the combinatorial structure of which assignments are "adjacent". Local search starts at an assignment in this landscape and successively moves assignments until no further improvement is possible among the adjacent assignments. Classic analyses of local search algorithms have focused more on the question of effectiveness ("did we find a good solution?") and often implicitly assumed that there are no doubts about their efficiency ("did we find it quickly?"). But there are many reasons to doubt the efficiency of local search. Even if we focus on fitness landscapes on the hypercube that are single peaked on every subcube (known as semismooth fitness landscapes, completely unimodal pseudo-Boolean functions, or acyclic unique sink orientations) where effectiveness is obvious, many local search algorithms are known to be inefficient. Since fitness landscapes are unwieldy exponentially large objects, we focus on their polynomial-sized representations by instances of valued constraint satisfaction problems (VCSP). We define a "direction" for valued constraints such that directed VCSPs generate semismooth fitness landscapes. We call directed VCSPs oriented if they do not have any pair of variables with arcs in both directions. Since recognizing if a VCSP-instance is directed or oriented is coNP-complete, we generalized oriented VCSPs as conditionally-smooth fitness landscapes where the structural property of "conditionally-smooth" is recognizable in polynomial time for a VCSP-instance. We prove that many popular local search algorithms like random ascent, simulated annealing, history-based rules, jumping rules, and the Kernighan-Lin heuristic are very efficient on conditionally-smooth landscapes. But conditionally-smooth landscapes are still expressive enough so that other well-regarded local search algorithms like steepest ascent and random facet require a super-polynomial number of steps to find the fitness peak.
Cite as

Artem Kaznatcheev and Sofia Vazquez Alferez. When Is Local Search Both Effective and Efficient?. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kaznatcheev_et_al:LIPIcs.STACS.2026.59,
  author =	{Kaznatcheev, Artem and Vazquez Alferez, Sofia},
  title =	{{When Is Local Search Both Effective and Efficient?}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.59},
  URN =		{urn:nbn:de:0030-drops-255480},
  doi =		{10.4230/LIPIcs.STACS.2026.59},
  annote =	{Keywords: valued constraint satisfaction problem, local search, algorithm analysis, constraint graphs, pseudo-Boolean functions, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.50
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs

Authors: Thekla Hamm, Sukanya Pandey, and Krisztina Szilágyi

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given a planar graph, a subset of its vertices called terminals, and k ∈ ℕ, the Face Cover Number problem asks whether the terminals lie on the boundaries of at most k faces of some embedding of the input graph. When a plane graph is given in the input, the problem is known to have a polynomial kernel [Valentin Garnero et al., 2017]. In this paper, we present the first polynomial kernel for Face Cover Number when the input is a planar graph (without a fixed embedding). Our approach overcomes the challenge of not having a predefined set of face boundaries by building a kernel bottom-up on an SPR-tree while preserving the essential properties of the face cover along the way.
Cite as

Thekla Hamm, Sukanya Pandey, and Krisztina Szilágyi. A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hamm_et_al:LIPIcs.STACS.2026.50,
  author =	{Hamm, Thekla and Pandey, Sukanya and Szil\'{a}gyi, Krisztina},
  title =	{{A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.50},
  URN =		{urn:nbn:de:0030-drops-255392},
  doi =		{10.4230/LIPIcs.STACS.2026.50},
  annote =	{Keywords: Kernelization, Planar Graphs, SPQR-tree}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.27
Analysis of Logics with Arithmetic

Authors: Michael Benedikt, Chia-Hsuan Lu, and Tony Tan

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
We present new results on finite satisfiability of logics with counting and arithmetic. One result is a tight bound on the complexity of satisfiability of logics with so-called local Presburger quantifiers, which sum over neighbors of a node in a graph. A second contribution concerns computing a semilinear representation of the cardinalities associated with a formula in two variable logic extended with counting quantifiers. Such a representation allows you to get bounds not only on satisfiability for these logics, but for satisfiability in the presence of additional "global cardinality constraints": restrictions on cardinalities of unary formulas, expressed using arbitrary decidability logics over arithmetic. In the process, we provide simpler proofs of some key prior results on finite satisfiability and semi-linearity of the spectrum for these logics.
Cite as

Michael Benedikt, Chia-Hsuan Lu, and Tony Tan. Analysis of Logics with Arithmetic. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benedikt_et_al:LIPIcs.CSL.2026.27,
  author =	{Benedikt, Michael and Lu, Chia-Hsuan and Tan, Tony},
  title =	{{Analysis of Logics with Arithmetic}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.27},
  URN =		{urn:nbn:de:0030-drops-254510},
  doi =		{10.4230/LIPIcs.CSL.2026.27},
  annote =	{Keywords: Presburger quantifiers, Spectrum, Guarded logics}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.6
Hereditary First-Order Logic: the Tractable Quantifier Prefix Classes

Authors: Manuel Bodirsky and Santiago Guzmán-Pro

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Many computational problems can be modelled as the class of all finite structures A that satisfy a fixed first-order sentence ϕ hereditarily, i.e., we require that every (induced) substructure of A satisfies ϕ. We call the corresponding computational problem the hereditary model checking problem for ϕ, and denote it by Her(ϕ). We present a complete description of the quantifier prefixes for ϕ such that Her(ϕ) is in P; we show that for every other quantifier prefix there exists a formula ϕ with this prefix such that Her(ϕ) is coNP-complete. Specifically, we show that if Q is of the form ∀*∃∀* or of the form ∀*∃*, then Her(ϕ) can be solved in polynomial time whenever the quantifier prefix of ϕ is Q. Otherwise, Q contains ∃∃∀ or ∃∀∃ as a subword, and in this case, there is a first-order formula ϕ whose quantifier prefix is Q and Her(ϕ) is coNP-complete. Moreover, we show that there is no algorithm that decides for a given first-order formula ϕ whether Her(ϕ) is in P (unless P=NP).
Cite as

Manuel Bodirsky and Santiago Guzmán-Pro. Hereditary First-Order Logic: the Tractable Quantifier Prefix Classes. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.CSL.2026.6,
  author =	{Bodirsky, Manuel and Guzm\'{a}n-Pro, Santiago},
  title =	{{Hereditary First-Order Logic: the Tractable Quantifier Prefix Classes}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.6},
  URN =		{urn:nbn:de:0030-drops-254308},
  doi =		{10.4230/LIPIcs.CSL.2026.6},
  annote =	{Keywords: Quantifier prefix, first-order Logic, Computational Complexity, Polynomial-time algorithm, coNP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.45
Fairness in the k-Server Problem

Authors: Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco

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

Abstract
We initiate a formal study of fairness for the k-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of (α,β)-fairness, where, for parameters α ≥ 1 and β ≥ 0, no server incurs more than an α/k-fraction of the total cost plus an additive term β. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any ε > 0, transforms any optimal solution into an (α,β)-fair solution for α = 1 + ε and β = O(diam ⋅ log k / ε), while increasing the cost of the solution by just an additive O(diam ⋅ k log k / ε) term. Here diam is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when k = 2. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any "marking algorithm", including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness.
Cite as

Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco. Fairness in the k-Server Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{daneshvaramoli_et_al:LIPIcs.ITCS.2026.45,
  author =	{Daneshvaramoli, Mohammadreza and Hajiesmaili, Mohammad and Kamali, Shahin and Karisani, Helia and Musco, Cameron},
  title =	{{Fairness in the k-Server Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-253328},
  doi =		{10.4230/LIPIcs.ITCS.2026.45},
  annote =	{Keywords: k-server problem, online algorithms, fairness, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.7
An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem

Authors: Marco Aldi, Sevag Gharibian, and Dorian Rudolph

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

Abstract
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on Bézout’s theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA ⊆ MHS.
Cite as

Marco Aldi, Sevag Gharibian, and Dorian Rudolph. An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aldi_et_al:LIPIcs.ITCS.2026.7,
  author =	{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian},
  title =	{{An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{7:1--7:24},
  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.7},
  URN =		{urn:nbn:de:0030-drops-252946},
  doi =		{10.4230/LIPIcs.ITCS.2026.7},
  annote =	{Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), Quantum Satisfiability Problem (QSAT), total function NP (TFNP)}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.15
How to Use Nondeterminism in Cryptography

Authors: Marshall Ball and Peter Crawford-Kahrl

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

Abstract
Nondeterministic reductions have yielded powerful results in the theory of computational complexity, yet are effectively useless in a cryptographic context. The reason for this is simple, a nondeterministic polynomial time adversary can trivially break almost any cryptographic primitive by simply guessing the "key." In order to use this powerful nondeterministic tool kit in the cryptographic context, we initiate the study of cryptography against adversaries with limited nondeterminism: polynomial time nondeterministic algorithms that are restricted to just a few bits of nondeterminism. We demonstrate that limited nondeterministic security is sufficient to prove two foundational results that have eluded our grasp for decades: dream hardness amplification, and extracting ω(log n) hardcore bits.
Cite as

Marshall Ball and Peter Crawford-Kahrl. How to Use Nondeterminism in Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2026.15,
  author =	{Ball, Marshall and Crawford-Kahrl, Peter},
  title =	{{How to Use Nondeterminism in Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-253024},
  doi =		{10.4230/LIPIcs.ITCS.2026.15},
  annote =	{Keywords: limited nondeterminism, cryptography, computational complexity, hardness amplification, pseudorandom generators, hardcore bits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.82
Dimension Reduction for Clustering: The Curious Case of Discrete Centers

Authors: Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue

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

Abstract
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of n points into dimension O(log n) with low distortion of their distances. This dimension bound is tight in general, but one can bypass it for specific problems. Indeed, tremendous progress has been made for clustering problems, especially in the continuous setting where centers can be picked from the ambient space ℝ^d. Most notably, for k-median and k-means, the dimension bound was improved to O(log k) [Makarychev, Makarychev and Razenshteyn, STOC 2019]. We explore dimension reduction for clustering in the discrete setting, where centers can only be picked from the dataset, and present two results that are both parameterized by the doubling dimension of the dataset, denoted as ddim. The first result shows that dimension O_{ε}(ddim + log k + log log n) suffices, and is moreover tight, to guarantee that the cost is preserved within factor 1±ε for every set of centers. Our second result eliminates the log log n term in the dimension through a relaxation of the guarantee (namely, preserving the cost only for all approximately-optimal sets of centers), which maintains its usefulness for downstream applications. Overall, we achieve strong dimension reduction in the discrete setting, and find that it differs from the continuous setting not only in the dimension bound, which depends on the doubling dimension, but also in the guarantees beyond preserving the optimal value, such as which clusterings are preserved.
Cite as

Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue. Dimension Reduction for Clustering: The Curious Case of Discrete Centers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 82:1-82:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ITCS.2026.82,
  author =	{Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay and Silwal, Sandeep and Yue, Di},
  title =	{{Dimension Reduction for Clustering: The Curious Case of Discrete Centers}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{82:1--82:23},
  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.82},
  URN =		{urn:nbn:de:0030-drops-253698},
  doi =		{10.4230/LIPIcs.ITCS.2026.82},
  annote =	{Keywords: dimension reduction, clustering, k-median, k-means, doubling dimension}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.79
Range Avoidance and Remote Point: New Algorithms and Hardness

Authors: Shengtang Huang, Xin Li, and Yan Zhong

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

Abstract
The Range Avoidance (Avoid) problem C-Avoid[n,m(n)] asks that, given a circuit in a class C with input length n and output length m(n) > n, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous work by Korten (FOCS' 21) and by Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for Avoid are closely related to circuit lower bounds. In particular, Korten’s work reinterpreted an earlier result from bounded arithmetic, originally proved by Jeřábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of FP^NP algorithms for the general Avoid problem and 2^{Ω(n)} lower bounds against general Boolean circuits for the class 𝐄^NP. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following: - For any constant depth unbounded fan-in circuit class C ⊇ AC⁰, there is an FP^NP algorithm for C-Avoid[n,n^{1+ε}] (for any constant ε > 0) if and only if 𝐄^NP cannot be computed by C circuits of size 2^{o(n)}. This addresses an open problem by Korten (Bulletin of EATCS' 25). - If 𝐄^NP cannot be computed by o(2ⁿ/n) size formulas, then there is an FP^NP algorithm for NC⁰-Avoid[n,2n]. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an FP^NP algorithm for NC⁰₄-Avoid[n,n+n^δ] for any constant δ ∈ (0,1) implies 𝐄^NP cannot be computed by o(2ⁿ/n) size formulas. These results yield the first characterizations of FP^NP C-Avoid algorithms for low-complexity circuit classes such as AC⁰. We also consider the average-case analog of Avoid, the Remote Point (Remote-Point) problem, and establish: - For some suitable function c(n) and constant γ > 0, there is an FP^NP algorithm for Remote-Point[n,n^{6+γ},c(O_{γ}(log n))] if and only if 𝐄^NP cannot be (1/2-c(n))-approximated by circuits of size 2^{o(n)}. Finally, we also present two improved algorithms for NC⁰-Avoid: - A family of 2^{n^{1 - ε/(k-1) +o(1)}} time algorithms for NC⁰_k-Avoid[n,n^{1+ε}] for any ε > 0, exhibiting the first subexponential-time algorithm for any super-linear stretch. - Faster local algorithms for NC⁰_k-Avoid[n,n+1] running in time O(n2^{(k-2)/(k-1) n}), improving the naive 2ⁿ⋅ poly(n) bound.
Cite as

Shengtang Huang, Xin Li, and Yan Zhong. Range Avoidance and Remote Point: New Algorithms and Hardness. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 79:1-79:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ITCS.2026.79,
  author =	{Huang, Shengtang and Li, Xin and Zhong, Yan},
  title =	{{Range Avoidance and Remote Point: New Algorithms and Hardness}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{79:1--79: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.79},
  URN =		{urn:nbn:de:0030-drops-253662},
  doi =		{10.4230/LIPIcs.ITCS.2026.79},
  annote =	{Keywords: Circuit Lower Bounds, Range Avoidance Problem, Remote Point Problem}
}
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}
}
  • Refine by Type
  • 184 Document/PDF
  • 110 Document/HTML
  • 1 Volume

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

  • Refine by Author
  • 10 Papadimitriou, Christos H.
  • 3 Defrain, Oscar
  • 3 Ganian, Robert
  • 3 Koutsoupias, Elias
  • 3 Naor, Moni
  • Show More...

  • Refine by Series/Journal
  • 178 LIPIcs
  • 3 OASIcs
  • 2 TGDK
  • 1 DagSemRep

  • Refine by Classification
  • 13 Theory of computation → Parameterized complexity and exact algorithms
  • 10 Theory of computation → Graph algorithms analysis
  • 10 Theory of computation → Problems, reductions and completeness
  • 9 Mathematics of computing → Graph algorithms
  • 9 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 8 parameterized complexity
  • 5 Parameterized Complexity
  • 4 Communication Complexity
  • 4 TFNP
  • 4 local search
  • 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