9 Search Results for "Gordon, Spencer"

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.52
Upper and Lower Bounds for the Linear Ordering Principle

Authors: Edward A. Hirsch and Ilya Volkovich

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

Abstract
Korten and Pitassi (FOCS, 2024) defined a new complexity class L₂^P as the polynomial-time Turing closure of the Linear Ordering Principle (a total function extending finding the minimum of an order [M. Chiari and J. Krajíček, 1998] to the case where the order is not linear). They put it between MA (Merlin-Arthur protocols) and S₂^P (the second symmetric level of the polynomial hierarchy). In this paper we sandwich L₂^P between P^prMA and P^prSBP. (The oracles here are promise problems, and SBP is the only known class between MA and AM.) The containment in P^prSBP is proved via an iterative process that uses a prSBP oracle to estimate the average order rank of a subset and find the minimum of a linear order. Another containment result of this paper is P^prO₂^P ⊆ O₂^P (where O₂^P is the input-oblivious version of S₂^P). These containment results altogether have several byproducts: - We give an affirmative answer to an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) whether P^prMA ⊆ S₂^P, thereby settling the relative standing of the existing (non-oblivious) Karp–Lipton–style collapse results of [V. T. Chakaravarthy and S. Roy, 2011] and [J.-Y. Cai, 2007], - We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for L₂^P, - We show that the Karp-Lipton-style collapse to P^prOMA is actually better than both known collapses to P^prMA due to Chakaravarthy and Roy (Computational Complexity, 2011) and to O₂^P also due to Chakaravarthy and Roy (STACS, 2006). Thus we resolve the controversy between previously incomparable Karp-Lipton collapses stemming from these two lines of research.
Cite as

Edward A. Hirsch and Ilya Volkovich. Upper and Lower Bounds for the Linear Ordering Principle. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hirsch_et_al:LIPIcs.STACS.2026.52,
  author =	{Hirsch, Edward A. and Volkovich, Ilya},
  title =	{{Upper and Lower Bounds for the Linear Ordering Principle}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{52:1--52: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.52},
  URN =		{urn:nbn:de:0030-drops-255410},
  doi =		{10.4230/LIPIcs.STACS.2026.52},
  annote =	{Keywords: Complexity Classes, Structural Complexity Theory, Linear Ordering Principle, Symmetric Alternation, Merlin-Arthur Protocols, Karp-Lipton Collapse}
}
Document
Research
DOI: 10.4230/TGDK.3.3.4
Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web

Authors: Florian Ruosch, Cristina Sarasua, and Abraham Bernstein

Published in: TGDK, Volume 3, Issue 3 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 3

Abstract
In Argument Mining, predicting argumentative relations between texts (or spans) remains one of the most challenging aspects, even more so in the cross-document setting. This paper makes three key contributions to advance research in this domain. We first extend an existing dataset, the Sci-Arg corpus, by annotating it with explicit inter-document argumentative relations, thereby allowing arguments to be distributed over several documents forming an Argument Web; these new annotations are published using Semantic Web technologies (RDF, OWL). Second, we explore and evaluate three automated approaches for predicting these inter-document argumentative relations, establishing critical baselines on the new dataset. We find that a simple classifier based on discourse indicators with access to context outperforms neural methods. Third, we conduct a comparative analysis of these approaches for both intra- and inter-document settings, identifying statistically significant differences in results that indicate the necessity of distinguishing between these two scenarios. Our findings highlight significant challenges in this complex domain and open crucial avenues for future research on the Argument Web of Science, particularly for those interested in leveraging Semantic Web technologies and knowledge graphs to understand scholarly discourse. With this, we provide the first stepping stones in the form of a benchmark dataset, three baseline methods, and an initial analysis for a systematic exploration of this field relevant to the Web of Data and Science.
Cite as

Florian Ruosch, Cristina Sarasua, and Abraham Bernstein. Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{ruosch_et_al:TGDK.3.3.4,
  author =	{Ruosch, Florian and Sarasua, Cristina and Bernstein, Abraham},
  title =	{{Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:33},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{3},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.3.4},
  URN =		{urn:nbn:de:0030-drops-252159},
  doi =		{10.4230/TGDK.3.3.4},
  annote =	{Keywords: Argument Mining, Large Language Models, Knowledge Graphs, Link Prediction}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.41
Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

Authors: Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one-dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents’ preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent’s allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.
Cite as

Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui. Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.FSTTCS.2025.41,
  author =	{Kawase, Yasushi and Roy, Bodhayan and Sanpui, Mohammad Azharuddin},
  title =	{{Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-251210},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.41},
  annote =	{Keywords: Fair allocation, Envy-free up to one good, Multi-dimensional criteria, Linear programming, NP-hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.95
ARRIVAL: Recursive Framework & 𝓁₁-Contraction

Authors: Sebastian Haslebacher

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

Abstract
ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, according to so-called switching rules. It is known to lie in NP ∩ CoNP, but not known to lie in 𝖯. The state-of-the-art algorithm due to Gärtner et al. (ICALP `21) runs in time 2^{𝒪(√n log n)} on an n-vertex graph. We prove that ARRIVAL can be solved in time 2^{𝒪(k log² n)} on n-vertex graphs of treewidth k. Our algorithm is derived by adapting a simple recursive algorithm for a generalization of ARRIVAL called G-ARRIVAL. This simple recursive algorithm acts as a framework from which we can also rederive the subexponential upper bound of Gärtner et al. Our second result is a reduction from G-ARRIVAL to the problem of finding an approximate fixed point of an 𝓁₁-contracting function f : [0, 1]ⁿ → [0, 1]ⁿ. Finding such fixed points is a well-studied problem in the case of the 𝓁₂-metric and the 𝓁_∞-metric, but little is known about the 𝓁₁-case. Both of our results highlight parallels between ARRIVAL and the Simple Stochastic Games (SSG) problem. Concretely, Chatterjee et al. (SODA `23) gave an algorithm for SSG parameterized by treewidth that achieves a similar bound as we do for ARRIVAL, and SSG is known to reduce to 𝓁_∞-contraction.
Cite as

Sebastian Haslebacher. ARRIVAL: Recursive Framework & 𝓁₁-Contraction. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haslebacher:LIPIcs.ICALP.2025.95,
  author =	{Haslebacher, Sebastian},
  title =	{{ARRIVAL: Recursive Framework \& 𝓁₁-Contraction}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{95:1--95:17},
  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.95},
  URN =		{urn:nbn:de:0030-drops-234723},
  doi =		{10.4230/LIPIcs.ICALP.2025.95},
  annote =	{Keywords: ARRIVAL, G-ARRIVAL, Deterministic Random Walk, Rotor-Routing, 𝓁₁-Contraction, Banach Fixed Point}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.145
Reducing Stochastic Games to Semidefinite Programming

Authors: Manuel Bodirsky, Georg Loho, and Mateusz Skomra

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

Abstract
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon’s simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity games can all be reduced to semidefinite programming.
Cite as

Manuel Bodirsky, Georg Loho, and Mateusz Skomra. Reducing Stochastic Games to Semidefinite Programming. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 145:1-145:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2025.145,
  author =	{Bodirsky, Manuel and Loho, Georg and Skomra, Mateusz},
  title =	{{Reducing Stochastic Games to Semidefinite Programming}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{145:1--145:15},
  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.145},
  URN =		{urn:nbn:de:0030-drops-235224},
  doi =		{10.4230/LIPIcs.ICALP.2025.145},
  annote =	{Keywords: Mean-payoff games, stochastic games, semidefinite programming, max-average constraints, max-atom problem}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.32
Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents

Authors: Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, and Simon Weber

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sink orientation (USO), and a variant of the α-Ham Sandwich problem. For all three settings, we show that "two choices are enough", meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our α-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs.
Cite as

Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, and Simon Weber. Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{borzechowski_et_al:LIPIcs.ICALP.2024.32,
  author =	{Borzechowski, Michaela and Fearnley, John and Gordon, Spencer and Savani, Rahul and Schnider, Patrick and Weber, Simon},
  title =	{{Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.32},
  URN =		{urn:nbn:de:0030-drops-201751},
  doi =		{10.4230/LIPIcs.ICALP.2024.32},
  annote =	{Keywords: P-LCP, Unique Sink Orientation, \alpha-Ham Sandwich, search complexity, TFNP, UEOPL}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.56
Unique End of Potential Line

Authors: John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The complexity class CLS was proposed by Daskalakis and Papadimitriou in 2011 to understand the complexity of important NP search problems that admit both path following and potential optimizing algorithms. Here we identify a subclass of CLS - called UniqueEOPL - that applies a more specific combinatorial principle that guarantees unique solutions. We show that UniqueEOPL contains several important problems such as the P-matrix Linear Complementarity Problem, finding Fixed Point of Contraction Maps, and solving Unique Sink Orientations (USOs). UniqueEOPL seems to a proper subclass of CLS and looks more likely to be the right class for the problems of interest. We identify a problem - closely related to solving contraction maps and USOs - that is complete for UniqueEOPL. Our results also give the fastest randomised algorithm for P-matrix LCP.
Cite as

John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique End of Potential Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fearnley_et_al:LIPIcs.ICALP.2019.56,
  author =	{Fearnley, John and Gordon, Spencer and Mehta, Ruta and Savani, Rahul},
  title =	{{Unique End of Potential Line}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.56},
  URN =		{urn:nbn:de:0030-drops-106327},
  doi =		{10.4230/LIPIcs.ICALP.2019.56},
  annote =	{Keywords: P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search}
}
  • Refine by Type
  • 9 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 5 2025
  • 1 2024
  • 1 2019

  • Refine by Author
  • 2 Fearnley, John
  • 2 Gordon, Spencer
  • 2 Savani, Rahul
  • 2 Schnider, Patrick
  • 2 Weber, Simon
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 5 Theory of computation → Problems, reductions and completeness
  • 2 Mathematics of computing → Combinatoric problems
  • 2 Theory of computation → Algorithmic game theory
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Information extraction
  • Show More...

  • Refine by Keyword
  • 2 TFNP
  • 1 ARRIVAL
  • 1 Argument Mining
  • 1 Banach Fixed Point
  • 1 Complexity Classes
  • 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