216 Search Results for "Censor-Hillel, Keren"

Volume

LIPIcs, Volume 334

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

ICALP 2025, July 8-11, 2025, Aarhus, Denmark

Editors: Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Document
DOI: 10.4230/LIPIcs.DISC.2025.20
Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique

Authors: Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We design a deterministic compiler that makes any computation in the Congested Clique model robust to a constant fraction α < 1 of adversarial crash faults. In particular, we show how a network of n nodes can compute any circuit of depth d, width ω, and gate total fan Δ, in d ⋅ ⌈ω/n² + Δ/n⌉ ⋅ 2^{O(√{log{n}}log log{n})} rounds in such a faulty model. As a corollary, any T-round Congested Clique algorithm can be compiled into an algorithm that completes in T² n^{o(1)} rounds in this model. Our compiler obtains resilience to node crashes by coding information across the network, and its main underlying observation is that we can leverage locally-decodable codes (LDCs) to maintain a low complexity overhead, as these allow recovering the information needed at each computational step by querying only small parts of the codeword, instead of retrieving the entire coded message, which is inherent when using block codes. The main technical contribution is that because erasures occur in known locations, which correspond to crashed nodes, we can derandomize classical LDC constructions by deterministically selecting query sets that avoid sufficiently many erasures. Moreover, when decoding multiple codewords in parallel, our derandomization load-balances the queries per-node, thereby preventing congestion and maintaining a low round complexity. Deterministic decoding of LDCs presents a new challenge: the adversary can target precisely the (few) nodes that are queried for decoding a certain codeword. We overcome this issue via an adaptive doubling strategy: if a decoding attempt for a codeword fails, the node doubles the number of its decoding attempts. We employ a similar doubling technique when the adversary crashes the decoding node itself, replacing it dynamically with two other non-crashed nodes. By carefully combining these two doubling processes, we overcome the challenges posed by the combination of a deterministic LDC with a worst case pattern of crashes.
Cite as

Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto. Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2025.20,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Gelles, Ran and Soto, Pedro},
  title =	{{Two for One, One for All: Deterministic LDC-Based Robust Computation in Congested Clique}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.20},
  URN =		{urn:nbn:de:0030-drops-248379},
  doi =		{10.4230/LIPIcs.DISC.2025.20},
  annote =	{Keywords: Congested Clique, Fault Tolerance, Error Correction Codes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.10
Connected Partitions via Connected Dominating Sets

Authors: Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif

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

Abstract
The classical theorem due to Győri and Lovász states that any k-connected graph G admits a partition into k connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of G. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for k = 5. We make progress towards an efficient constructive version of the Győri-Lovász theorem by considering a natural strengthening of the k-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if G contains k disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri-Lovász theorem: - On general graphs, a Győri-Lovász partition with k parts can be computed in polynomial time when the input graph has connectivity Ω(k ⋅ log² n); - On convex bipartite graphs, connectivity of 4k is sufficient; - On biconvex graphs and interval graphs, connectivity of k is sufficient, meaning that our algorithm gives a "true" constructive version of the theorem on these graph classes.
Cite as

Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif. Connected Partitions via Connected Dominating Sets. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{niklanovits_et_al:LIPIcs.ESA.2025.10,
  author =	{Niklanovits, Aikaterini and Simonov, Kirill and Verma, Shaily and Zeif, Ziena},
  title =	{{Connected Partitions via Connected Dominating Sets}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{10:1--10:14},
  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.10},
  URN =		{urn:nbn:de:0030-drops-244785},
  doi =		{10.4230/LIPIcs.ESA.2025.10},
  annote =	{Keywords: Gy\H{o}ri-Lov\'{a}sz theorem, connected dominating sets, graph classes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.39
Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

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

Abstract
Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.
Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39:19},
  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.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.34
Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) is invariant under simultaneous permutations of the coordinates of u and v.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost 𝒪(1)-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid 𝒮ⁿ to an Abelian group, correcting from a near-optimal (1/|𝒮|^d - ε) fraction of errors for every ε > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2025.34,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  URN =		{urn:nbn:de:0030-drops-244004},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  annote =	{Keywords: Markov Chains, Random Walk, Multislices, Representation Theory of Symmetric Group, Local Correction, Low-degree Polynomials, Polynomial Distance Lemma}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.64
Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication

Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We show that for a randomly sampled unsatisfiable O(log n)-CNF over n variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in n.
Cite as

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan. Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riazanov_et_al:LIPIcs.APPROX/RANDOM.2025.64,
  author =	{Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry and Yuan, Weiqiang},
  title =	{{Searching for Falsified Clause in Random (log\{n\})-CNFs Is Hard for Randomized Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.64},
  URN =		{urn:nbn:de:0030-drops-244306},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.64},
  annote =	{Keywords: communication complexity, proof complexity, random CNF}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.50
Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions

Authors: Adar Hadad and Moni Naor

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Shared randomness is a valuable resource in distributed computing, allowing some form of coordination between processors without explicit communication. But what happens when the shared random string can affect the inputs to the system? Consider the class of distributed graph problems where the correctness of solutions can be checked locally, known as Locally Checkable Labelings (LCL). LCL problems have been extensively studied in the LOCAL model, where nodes operate in synchronous rounds and have access only to local information. This has led to intriguing insights regarding the power of private randomness. E.g., for certain round complexity classes, derandomization does not incur an overhead (asymptotically). This work considers a setting where the randomness is public. Recently, an LCL problem for which shared randomness can reduce the round complexity was discovered by Balliu et al. (ICALP 2025). This result applies to inputs set obliviously of the shared randomness, which may not always be a plausible assumption. We define a model where the inputs can be adversarially chosen, even based on the shared randomness, which we now call preset public coins. We study LCL problems in the preset public coins model, under assumptions regarding the computational power of the adversary that selects the input. We show connections to hardness in the class TFNP. Our results are: 1) Assuming a hard-on-average problem in TFNP, we present an LCL problem that, in the preset public coins model, demonstrates a gap in the round complexity between polynomial-time and unbounded adversaries. 2) An LCL problem for which the error probability is significantly higher when facing unbounded adversaries implies a hard-on-average problem in TFNP/poly.
Cite as

Adar Hadad and Moni Naor. Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 50:1-50:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hadad_et_al:LIPIcs.APPROX/RANDOM.2025.50,
  author =	{Hadad, Adar and Naor, Moni},
  title =	{{Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{50:1--50:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.50},
  URN =		{urn:nbn:de:0030-drops-244161},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.50},
  annote =	{Keywords: Distributed Graph Algorithms, Common Random String, Cryptographic Hardness}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2025.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

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

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

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 0:i-0:xliv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2025.0,
  author =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{0:i--0:xliv},
  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.0},
  URN =		{urn:nbn:de:0030-drops-237675},
  doi =		{10.4230/LIPIcs.ICALP.2025.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.46
Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations

Authors: Karthekeyan Chandrasekaran, Siyue Liu, and R. Ravi

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

Abstract
Flows and colorings are disparate concepts in graph algorithms - the former is tractable while the latter is intractable. Tutte [Tutte, 1954; Tutte, 1966] introduced the concept of nowhere-zero flows to unify these two concepts. Jaeger [Jaeger, 1976] showed that nowhere-zero flows are equivalent to cut-balanced orientations. Motivated by connections between nowhere-zero flows, cut-balanced orientations, Nash-Williams' well-balanced orientations, and postman problems, we study optimization versions of nowhere-zero flows and cut-balanced orientations. Given a bidirected graph with asymmetric costs on two orientations of each edge, we study the min cost nowhere-zero k-flow problem and min cost k-cut-balanced orientation problem. We show that both problems are NP-hard to approximate within any finite factor. Given the strong inapproximability result, we design bicriteria approximations for both problems: we obtain a (6,6)-approximation to the min cost nowhere-zero k-flow and a (k,6)-approximation to the min cost k-cut-balanced orientation. For the case of symmetric costs (where the costs of both orientations are the same for every edge), we show that the nowhere-zero k-flow problem remains NP-hard and admits a 3-approximation.
Cite as

Karthekeyan Chandrasekaran, Siyue Liu, and R. Ravi. Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.ICALP.2025.46,
  author =	{Chandrasekaran, Karthekeyan and Liu, Siyue and Ravi, R.},
  title =	{{Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{46:1--46:21},
  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.46},
  URN =		{urn:nbn:de:0030-drops-234238},
  doi =		{10.4230/LIPIcs.ICALP.2025.46},
  annote =	{Keywords: Nowhere-zero Flows, Cut-balanced orientations, Bicriteria approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.73
Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes

Authors: Koppány István Encz, Monaldo Mastrolilli, and Eleonora Vercesi

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

Abstract
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits PTAS-like behaviour, yielding increasingly better solutions within polynomial time. Our findings are supported by computational experiments and comparisons with benchmark methods.
Cite as

Koppány István Encz, Monaldo Mastrolilli, and Eleonora Vercesi. Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{encz_et_al:LIPIcs.ICALP.2025.73,
  author =	{Encz, Kopp\'{a}ny Istv\'{a}n and Mastrolilli, Monaldo and Vercesi, Eleonora},
  title =	{{Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{73:1--73:19},
  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.73},
  URN =		{urn:nbn:de:0030-drops-234502},
  doi =		{10.4230/LIPIcs.ICALP.2025.73},
  annote =	{Keywords: Branch-and-bound algorithm, Polynomial-time approximation scheme, Parallel machine scheduling problem, Knapsack problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.97
An Optimal Error-Correcting Reduction for Matrix Multiplication

Authors: Shuichi Hirahara and Nobutaka Shimizu

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

Abstract
We present an optimal "worst-case exact to average-case approximate" reduction for matrix multiplication over a finite field of prime order p. Any efficient algorithm that correctly computes, in expectation, at least (1/p + ε)-fraction of entries of the multiplication A ⋅ B of a pair (A, B) of uniformly random matrices over the finite field of order p for a positive constant ε can be transformed into an efficient randomized algorithm that computes A ⋅ B for all the pairs (A, B) of matrices with high probability. Previously, such reductions were known only in a low-error regime (Gola, Shinkar and Singh; RANDOM 2024) or under non-uniform reductions (Hirahara and Shimizu; STOC 2025).
Cite as

Shuichi Hirahara and Nobutaka Shimizu. An Optimal Error-Correcting Reduction for Matrix Multiplication. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ICALP.2025.97,
  author =	{Hirahara, Shuichi and Shimizu, Nobutaka},
  title =	{{An Optimal Error-Correcting Reduction for Matrix Multiplication}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{97:1--97: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.97},
  URN =		{urn:nbn:de:0030-drops-234742},
  doi =		{10.4230/LIPIcs.ICALP.2025.97},
  annote =	{Keywords: Matrix Multiplication, Error-Correcting Reduction, Average-Case Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.121
Maximum Bipartite vs. Triangle-Free Subgraph

Authors: Tamio-Vesa Nakajima and Stanislav Živný

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

Abstract
Given a (multi)graph G which contains a bipartite subgraph with ρ edges, what is the largest triangle-free subgraph of G that can be found efficiently? We present an SDP-based algorithm that finds one with at least 0.8823 ρ edges, thus improving on the subgraph with 0.878 ρ edges obtained by the classic Max-Cut algorithm of Goemans and Williamson. On the other hand, by a reduction from Håstad’s 3-bit PCP we show that it is NP-hard to find a triangle-free subgraph with (25 / 26 + ε) ρ ≈ (0.961 + ε) ρ edges. As an application, we classify the Maximum Promise Constraint Satisfaction Problem, denoted byMaxPCSP(G, H), for all bipartite G: Given an input (multi)graph X which admits a G-colouring satisfying ρ edges, find an H-colouring of X that satisfies ρ edges. This problem is solvable in polynomial time, apart from trivial cases, if H contains a triangle, and is NP-hard otherwise.
Cite as

Tamio-Vesa Nakajima and Stanislav Živný. Maximum Bipartite vs. Triangle-Free Subgraph. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 121:1-121:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2025.121,
  author =	{Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Maximum Bipartite vs. Triangle-Free Subgraph}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{121:1--121:16},
  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.121},
  URN =		{urn:nbn:de:0030-drops-234987},
  doi =		{10.4230/LIPIcs.ICALP.2025.121},
  annote =	{Keywords: approximation, promise constraint satisfaction, triangle-free subgraphs}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2025
LIPIcs, Volume 334, ICALP 2025, Complete Volume

Authors: Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

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

Abstract
LIPIcs, Volume 334, ICALP 2025, Complete Volume
Cite as

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 1-3274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Proceedings{censorhillel_et_al:LIPIcs.ICALP.2025,
  title =	{{LIPIcs, Volume 334, ICALP 2025, Complete Volume}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{1--3274},
  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},
  URN =		{urn:nbn:de:0030-drops-237680},
  doi =		{10.4230/LIPIcs.ICALP.2025},
  annote =	{Keywords: LIPIcs, Volume 334, ICALP 2025, Complete Volume}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.14
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments

Authors: Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, and Adarsh Srinivasan

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

Abstract
Given a k-CNF formula and an integer s ≥ 2, we study algorithms that obtain s solutions to the formula that are as dispersed as possible. For s = 2, this problem of computing the diameter of a k-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for k = 2. The current best upper bound [Angelsmark and Thapper '04] goes to 4ⁿ as k → ∞. As our first result, we show that this quadratic blow up is not necessary by utilizing the Fast-Fourier transform (FFT) to give a O^*(2ⁿ) time exact algorithm for computing the diameter of any k-CNF formula. For s > 2, the problem was raised in the SAT community (Nadel '11) and several heuristics have been proposed for it, but no algorithms with theoretical guarantees are known. We give exact algorithms using FFT and clique-finding that run in O^*(2^{(s-1)n}) and O^*(s² |Ω_{𝐅}|^{ω ⌈ s/3 ⌉}) respectively, where |Ω_{𝐅}| is the size of the solutions space of the formula 𝐅 and ω is the matrix multiplication exponent. However, current SAT algorithms for finding one solution run in time O^*(2^{ε_{k}n}) for ε_{k} ≈ 1-Θ(1/k), which is much faster than all above run times. As our main result, we analyze two popular SAT algorithms - PPZ (Paturi, Pudlák, Zane '97) and Schöning’s ('02) algorithms, and show that in time poly(s)O^*(2^{ε_{k}n}), they can be used to approximate diameter as well as the dispersion (s > 2) problem. While we need to modify Schöning’s original algorithm for technical reasons, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe this geometric sampling property of PPZ may be of independent interest. Finally, we focus on diverse solutions to NP-complete optimization problems, and give bi-approximations running in time poly(s)O^*(2^{ε n}) with ε < 1 for several problems such as Maximum Independent Set, Minimum Vertex Cover, Minimum Hitting Set, Feedback Vertex Set, Multicut on Trees and Interval Vertex Deletion. For all of these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions s. Our methods show that by relaxing to bi-approximations, this dependence on s can be made polynomial.
Cite as

Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, and Adarsh Srinivasan. Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.ICALP.2025.14,
  author =	{Austrin, Per and Bercea, Ioana O. and Goswami, Mayank and Limaye, Nutan and Srinivasan, Adarsh},
  title =	{{Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-233916},
  doi =		{10.4230/LIPIcs.ICALP.2025.14},
  annote =	{Keywords: Exponential time algorithms, Satisfiability, k-SAT, PPZ, Sch\"{o}ning, Dispersion, Diversity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.87
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates

Authors: Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona

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

Abstract
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.
Cite as

Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona. IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 87:1-87:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{giambartolomei_et_al:LIPIcs.ICALP.2025.87,
  author =	{Giambartolomei, Giordano and Mallmann-Trenn, Frederik and Saona, Raimundo},
  title =	{{IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{87:1--87:21},
  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.87},
  URN =		{urn:nbn:de:0030-drops-234643},
  doi =		{10.4230/LIPIcs.ICALP.2025.87},
  annote =	{Keywords: Online algorithms, Prophet Inequality, Random Horizon, Secretary Problem}
}
  • Refine by Type
  • 215 Document/PDF
  • 183 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 192 2025
  • 2 2024
  • 3 2022
  • 7 2021
  • 2 2020
  • Show More...

  • Refine by Author
  • 26 Censor-Hillel, Keren
  • 4 Chandrasekaran, Karthekeyan
  • 4 Khanna, Sanjeev
  • 4 Leitersdorf, Dean
  • 4 Sudan, Madhu
  • Show More...

  • Refine by Series/Journal
  • 213 LIPIcs
  • 1 LITES
  • 1 DagRep

  • Refine by Classification
  • 25 Theory of computation → Distributed algorithms
  • 21 Theory of computation → Graph algorithms analysis
  • 20 Theory of computation → Problems, reductions and completeness
  • 15 Theory of computation → Design and analysis of algorithms
  • 14 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 9 Approximation Algorithms
  • 5 Congested Clique
  • 4 CONGEST
  • 4 approximation
  • 4 clustering
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact