DROPS

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.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.58

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Authors: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger

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

Abstract

We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal’s utility), reward, and welfare. Our first result is a strong impossibility: For submodular reward functions, no randomized poly-time algorithm can approximate the optimal budget-feasible value within any finite factor, even with demand-oracle access. This result rules out extending known constant-factor guarantees from either (i) unbudgeted settings with combinatorial actions or (ii) budgeted settings with binary actions, to their combination. The hardness is tight: It holds even when all but one agent have binary actions and the remaining agent has just one additional action. On the positive side, we show that gross substitutes rewards (a well-studied strict subclass of submodular functions) admit a deterministic poly-time O(1)-approximation, using only value queries. Our results thus draw the first sharp separation between budgeted and unbudgeted settings in combinatorial contracts, and identifies gross substitutes as a tractable frontier for budgeted combinatorial contracts. Finally, we present an FPTAS for additive rewards, demonstrating that arbitrary approximation is tractable under any budget. This constitutes the first FPTAS for the multi-agent combinatorial-actions setting, even in the absence of budget constraints.

Cite as

Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 58:1-58:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ITCS.2026.58,
  author =	{Feldman, Michal and Gal-Tzur, Yoav and Ponitka, Tomasz and Schlesinger, Maya},
  title =	{{One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-253459},
  doi =		{10.4230/LIPIcs.ITCS.2026.58},
  annote =	{Keywords: Combinatorial Contracts, Algorithmic Contract Design, Budget-Feasible Contracts}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.7

Mechanism Design for Automated Market Makers

Authors: T-H. Hubert Chan, Ke Wu, and Elaine Shi

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

Blockchains have popularized automated market makers (AMMs), applications that run on a blockchain, maintain a pool of crypto-assets, and execute trades with users governed by some pricing function. AMMs have also introduced a significant challenge known as the Miner Extractable Value (MEV). Specifically, miners who control the contents and sequencing of transactions in a block can extract value by front-running and back-running users' transactions, creating arbitrage opportunities that guarantee them risk-free returns. MEV not only harms ordinary users, but more critically, encourages miners to auction off favorable transaction placements to users and arbitragers. This has fostered a more centralized off-chain eco-system, departing from the decentralized equilibrium originally envisioned for the blockchain infrastructure layer. In this paper, we consider how to design AMM mechanisms that eliminate MEV opportunities. Specifically, we propose a new AMM mechanism that processes all transactions contained within a block according to some pre-defined rules, ensuring that some constant potential function is maintained after processing the batch. We show that our new mechanism satisfies two tiers of guarantees. First, for legacy blockchains where each block is proposed by a single (possibly rotating) miner, we prove that our mechanism satisfies arbitrage resilience, i.e., a miner cannot gain risk-free profit. Second, for blockchains where the block proposal process is decentralized and offers sequencing-fairness, we prove a strictly stronger notion called strategy proofness - roughly speaking, we guarantee that any individual user’s best response is to follow the honest strategy. Our results complement prior works on MEV resilience in the following senses. First, prior works have shown impossibilities to address MEV entirely at the consensus level. Our work demonstrates a new paradigm of mechanism design at the application (i.e., smart contract) layer to ensure provable guarantees of strategy proofness. Second, many works have attempted to augment the underlying consensus protocol with extra properties such as sequencing fairness. While most previous works heuristically argued why these extra properties help to mitigate MEV, our work demonstrates in a mathematically formal manner how to leverage such consensus-level properties to aid the design of strategy-proof mechanisms.

Cite as

T-H. Hubert Chan, Ke Wu, and Elaine Shi. Mechanism Design for Automated Market Makers. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.AFT.2025.7,
  author =	{Chan, T-H. Hubert and Wu, Ke and Shi, Elaine},
  title =	{{Mechanism Design for Automated Market Makers}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.7},
  URN =		{urn:nbn:de:0030-drops-247265},
  doi =		{10.4230/LIPIcs.AFT.2025.7},
  annote =	{Keywords: Mechanism design, game theory, strategy proof, blockchain}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.13

Composable Byzantine Agreements with Reorder Attacks

Authors: Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

Byzantine agreement (BA) is a foundational building block in distributed systems that has been extensively studied for decades. With the growing demand for protocol composition in practice, the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol’s security guarantees, without the participating parties being corrupted. In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when n ≤ 3t or n ≤ 2c + 2t + 1, where t and c denote the number of corrupted parties and communication channels, respectively. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when n > 3t and n > 2c+2t+1. More specifically, we provide a general black-box compiler that transforms any single-instance secure BA protocol into one that is secure under parallel executions, and we provide a non-black-box construction for concurrent compositions.

Cite as

Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou. Composable Byzantine Agreements with Reorder Attacks. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.AFT.2025.13,
  author =	{Chen, Jing and Dong, Jin and Li, Jichen and Xia, Xuanzhi and Zhou, Wentao},
  title =	{{Composable Byzantine Agreements with Reorder Attacks}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.13},
  URN =		{urn:nbn:de:0030-drops-247321},
  doi =		{10.4230/LIPIcs.AFT.2025.13},
  annote =	{Keywords: Byzantine agreement, protocol composition, channel reorder attack, security threshold}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.21

Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing

Authors: Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

We study a game-theoretic model for pool formation in Proof of Stake blockchain protocols. In such systems, stakeholders can form pools as a means of obtaining regular rewards from participation in ledger maintenance, with the power of each pool being dependent on its collective stake. The question we are interested in is the design of mechanisms, i.e., "reward sharing schemes," that suitably split rewards among pool members and achieve favorable properties in the resulting pool configuration. With this in mind, we initiate a non-cooperative game-theoretic analysis of the well known Shapley value scheme from cooperative game theory into the context of blockchains. In particular, we focus on the oceanic model of games, proposed by Milnor and Shapley (1978), which is suitable for populations where a small set of large players coexists with a big mass of rather small, negligible players. This provides an appropriate level of abstraction for pool formation processes that occur among the stakeholders of a blockchain. We provide comparisons between the Shapley mechanism and the more standard proportional scheme, in terms of attained decentralization, via a Price of Stability analysis and in terms of susceptibility to Sybil attacks, i.e., the strategic splitting of a players' stake with the intention of participating in multiple pools for increased profit. Interestingly, while the widely deployed proportional scheme appears to have certain advantages, the Shapley value scheme, which rewards higher the most pivotal players, emerges as a competitive alternative, by being able to bypass some of the downsides of proportional sharing in terms of Sybil attack susceptibility, while also not being far from optimal guarantees w.r.t. decentralization. Finally, we also complement our study with some variations of proportional sharing, where the profit is split in proportion to a superadditive or a subadditive function of the stake, showing that our results for the Shapley value scheme are maintained in comparison to these functions as well.

Cite as

Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos. Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kiayias_et_al:LIPIcs.AFT.2025.21,
  author =	{Kiayias, Aggelos and Koutsoupias, Elias and Markakis, Evangelos and Tsamopoulos, Panagiotis},
  title =	{{Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.21},
  URN =		{urn:nbn:de:0030-drops-247409},
  doi =		{10.4230/LIPIcs.AFT.2025.21},
  annote =	{Keywords: Shapley value, Nash equilibria, Price of Stability, Reward sharing schemes, Proof of Stake blockchains}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.23

Transaction Fee Market Design for Parallel Execution

Authors: Bahar Acilan, Andrei Constantinescu, Lioba Heimbach, and Roger Wattenhofer

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

Given the low throughput of blockchains like Bitcoin and Ethereum, scalability - the ability to process an increasing number of transactions - has become a central focus of blockchain research. One promising approach is the parallelization of transaction execution across multiple threads. However, achieving efficient parallelization requires a redesign of the incentive structure within the fee market. Currently, the fee market does not differentiate between transactions that access multiple high-demand storage keys (i.e., unique identifiers for individual data entries) versus a single low-demand one, as long as they require the same computational effort. Addressing this discrepancy is crucial for enabling more effective parallel execution. In this work, we aim to bridge the gap between the current fee market and the need for parallel execution by exploring alternative fee market designs. To this end, we propose a framework consisting of two key components: a Gas Computation Mechanism (GCM), which quantifies the load a transaction places on the network in terms of parallelization and computation, measured in units of gas, and a Transaction Fee Mechanism (TFM), which assigns a price to each unit of gas. We additionally introduce a set of desirable properties for a GCM, propose several candidate mechanisms, and evaluate them against these criteria. Our analysis highlights two strong candidates: the weighted area GCM, which integrates smoothly with existing TFMs such as EIP‑1559 and satisfies a broad subset of the outlined properties, and the time-proportional makespan GCM, which assigns gas costs based on the context of the entire block’s schedule and, through this dependence on the overall execution outcome, captures the dynamics of parallel execution more accurately.

Cite as

Bahar Acilan, Andrei Constantinescu, Lioba Heimbach, and Roger Wattenhofer. Transaction Fee Market Design for Parallel Execution. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{acilan_et_al:LIPIcs.AFT.2025.23,
  author =	{Acilan, Bahar and Constantinescu, Andrei and Heimbach, Lioba and Wattenhofer, Roger},
  title =	{{Transaction Fee Market Design for Parallel Execution}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.23},
  URN =		{urn:nbn:de:0030-drops-247426},
  doi =		{10.4230/LIPIcs.AFT.2025.23},
  annote =	{Keywords: blockchain, transaction fee mechanism, parallel execution}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.111

Hardness of Median and Center in the Ulam Metric

Authors: Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. - Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. - Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive Õ(n² L)-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.

Cite as

Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.. Hardness of Median and Center in the Ulam Metric. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 111:1-111:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.111,
  author =	{Fischer, Nick and Goldenberg, Elazar and Habib, Mursalin and Karthik C. S.},
  title =	{{Hardness of Median and Center in the Ulam Metric}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{111:1--111:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.111},
  URN =		{urn:nbn:de:0030-drops-245809},
  doi =		{10.4230/LIPIcs.ESA.2025.111},
  annote =	{Keywords: Ulam distance, median, center, rank aggregation, fine-grained complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.68

Graph Exploration: The Impact of a Distance Constraint

Authors: Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel

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

Abstract

A mobile agent, starting from a node s of a simple undirected connected graph G = (V,E), has to explore all nodes and edges of G using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on G as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most D to go back to node s. The upper bound D is fixed as being equal to (1+α)r, where r is the eccentricity of node s (i.e., the maximum distance from s to any other node) and α is any positive real constant. This task has been introduced by Duncan et al. [Christian A. Duncan et al., 2006] and is known as distance-constrained exploration. The penalty of an exploration algorithm running in G is the number of edge traversals made by the agent in excess of |E|. In [Petrisor Panaite and Andrzej Pelc, 1999], Panaite and Pelc gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph G with a (small) penalty in 𝒪(|V|). Hence, a natural question is whether we can obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph G with a linear penalty in |V| cannot be obtained for the task of fuel-constrained exploration, another variant studied in the literature. This solves an open problem posed by Duncan et al. in [Christian A. Duncan et al., 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.

Cite as

Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel. Graph Exploration: The Impact of a Distance Constraint. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.ICALP.2025.68,
  author =	{Devismes, St\'{e}phane and Dieudonn\'{e}, Yoann and Labourel, Arnaud},
  title =	{{Graph Exploration: The Impact of a Distance Constraint}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.68},
  URN =		{urn:nbn:de:0030-drops-234452},
  doi =		{10.4230/LIPIcs.ICALP.2025.68},
  annote =	{Keywords: exploration, graph, mobile agent}
}

Document

DOI: 10.4230/LIPIcs.STACS.2025.71

Unfairly Splitting Separable Necklaces

Authors: Patrick Schnider, Linus Stalder, and Simon Weber

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the α-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for α-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of α-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for α-Ham Sandwich.

Cite as

Patrick Schnider, Linus Stalder, and Simon Weber. Unfairly Splitting Separable Necklaces. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schnider_et_al:LIPIcs.STACS.2025.71,
  author =	{Schnider, Patrick and Stalder, Linus and Weber, Simon},
  title =	{{Unfairly Splitting Separable Necklaces}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{71:1--71:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.71},
  URN =		{urn:nbn:de:0030-drops-228963},
  doi =		{10.4230/LIPIcs.STACS.2025.71},
  annote =	{Keywords: Necklace splitting, n-separability, well-separation, Ham Sandwich, alpha-Ham Sandwich, unfair splitting, fair division}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.57

Consensus Division in an Arbitrary Ratio

Authors: Paul Goldberg and Jiawei Li

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

Abstract

We consider the problem of partitioning a line segment into two subsets, so that n finite measures all have the same ratio of values for the subsets. Letting α ∈ [0,1] denote the desired ratio, this generalises the PPA-complete consensus-halving problem, in which α = 1/2. Stromquist and Woodall [Stromquist and Woodall, 1985] showed that for any α, there exists a solution using 2n cuts of the segment. They also showed that if α is irrational, that upper bound is almost optimal. In this work, we elaborate the bounds for rational values α. For α = 𝓁/k, we show a lower bound of (k-1)/k ⋅ 2n - O(1) cuts; we also obtain almost matching upper bounds for a large subset of rational α. On the computational side, we explore its dependence on the number of cuts available. More specifically, 1) when using the minimal number of cuts for each instance is required, the problem is NP-hard for any α; 2) for a large subset of rational α = 𝓁/k, when (k-1)/k ⋅ 2n cuts are available, the problem is in PPA-k under Turing reduction; 3) when 2n cuts are allowed, the problem belongs to PPA for any α; more generally, the problem belong to PPA-p for any prime p if 2(p-1)⋅⌈p/2⌉/⌊p/2⌋ ⋅ n cuts are available.

Cite as

Paul Goldberg and Jiawei Li. Consensus Division in an Arbitrary Ratio. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.ITCS.2023.57,
  author =	{Goldberg, Paul and Li, Jiawei},
  title =	{{Consensus Division in an Arbitrary Ratio}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.57},
  URN =		{urn:nbn:de:0030-drops-175606},
  doi =		{10.4230/LIPIcs.ITCS.2023.57},
  annote =	{Keywords: Consensus Halving, TFNP, PPA-k, Necklace Splitting}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2017.16

Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis

Authors: Xiaotie Deng, Yansong Gao, and Jie Zhang

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

The approximation ratio has become one of the dominant measures in mechanism design problems. In light of analysis of algorithms, we define the smoothed approximation ratio to compare the performance of the optimal mechanism and a truthful mechanism when the inputs are subject to random perturbations of the worst-case inputs, and define the average-case approximation ratio to compare the performance of these two mechanisms when the inputs follow a distribution. For the one-sided matching problem, Filos-Ratsikas et al. [2014] show that, amongst all truthful mechanisms, random priority achieves the tight approximation ratio bound of Theta(sqrt{n}). We prove that, despite of this worst-case bound, random priority has a constant smoothed approximation ratio. This is, to our limited knowledge, the first work that asymptotically differentiates the smoothed approximation ratio from the worst-case approximation ratio for mechanism design problems. For the average-case, we show that our approximation ratio can be improved to 1+e. These results partially explain why random priority has been successfully used in practice, although in the worst case the optimal social welfare is Theta(sqrt{n}) times of what random priority achieves. These results also pave the way for further studies of smoothed and average-case analysis for approximate mechanism design problems, beyond the worst-case analysis.

Cite as

Xiaotie Deng, Yansong Gao, and Jie Zhang. Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.MFCS.2017.16,
  author =	{Deng, Xiaotie and Gao, Yansong and Zhang, Jie},
  title =	{{Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.16},
  URN =		{urn:nbn:de:0030-drops-80936},
  doi =		{10.4230/LIPIcs.MFCS.2017.16},
  annote =	{Keywords: mechanism design, approximation ratio, smoothed analysis, average-case analysis}
}

Document

DOI: 10.4230/LIPIcs.CCC.2016.23

Understanding PPA-Completeness

Authors: Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract

We consider the problem of finding a fully colored base triangle on the 2-dimensional Möbius band under the standard boundary condition, proving it to be PPA-complete. The proof is based on a construction for the DPZP problem, that of finding a zero point under a discrete version of continuity condition. It further derives PPA-completeness for versions on the Möbius band of other related discrete fixed point type problems, and a special version of the Tucker problem, finding an edge such that if the value of one end vertex is x, the other is -x, given a special anti-symmetry boundary condition. More generally, this applies to other non-orientable spaces, including the projective plane and the Klein bottle. However, since those models have a closed boundary, we rely on a version of the PPA that states it as to find another fixed point giving a fixed point. This model also makes it presentationally simple for an extension to a high dimensional discrete fixed point problem on a non-orientable (nearly) hyper-grid with a constant side length.

Cite as

Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu. Understanding PPA-Completeness. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.CCC.2016.23,
  author =	{Deng, Xiaotie and Edmonds, Jack R. and Feng, Zhe and Liu, Zhengyang and Qi, Qi and Xu, Zeying},
  title =	{{Understanding PPA-Completeness}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.23},
  URN =		{urn:nbn:de:0030-drops-58310},
  doi =		{10.4230/LIPIcs.CCC.2016.23},
  annote =	{Keywords: Fixed Point Computation, PPA-Completeness}
}

13 Search Results for "Deng, Xiaotie"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message