13 Search Results for "Vardi, Shai"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.53
Average Sensitivity of Geometric Algorithms

Authors: Matthijs Ebbens and Yuichi Yoshida

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

Abstract
In modern applications of geometric algorithms, it is often unrealistic to assume that the input representation fully captures all relevant aspects of the problem, because the input data is often large and dynamic. To address this challenge, we consider the notion of average sensitivity, which is defined as the average earth mover’s distance between the output distributions of the algorithm when run on an input and the same input with one point removed, where the average is over removed points and the distance between two outputs is measured using the symmetric difference size. We start by showing that a number of classical problems from computational geometry, in particular the convex hull, Delaunay triangulation, and Voronoi diagram problems, are "simple" from the viewpoint of average sensitivity by proving tight bounds for the average sensitivity of any algorithm for these problems. Then, we continue by constructing an algorithm with low average sensitivity that computes, for any ε > 0, a set of (1/3+ε)n guards for the art gallery problem. This is the main technical contribution of this work, which combines algorithms from computational geometry with results from the theory of local computation algorithms (LCAs) and property testing.
Cite as

Matthijs Ebbens and Yuichi Yoshida. Average Sensitivity of Geometric Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.ITCS.2026.53,
  author =	{Ebbens, Matthijs and Yoshida, Yuichi},
  title =	{{Average Sensitivity of Geometric Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{53:1--53:16},
  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.53},
  URN =		{urn:nbn:de:0030-drops-253409},
  doi =		{10.4230/LIPIcs.ITCS.2026.53},
  annote =	{Keywords: Average Sensitivity, Convex Hull, Delaunay Triangulation, Voronoi Diagram, Art Gallery}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.89
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Authors: Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang

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

Abstract
We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system 𝐌x = b in sublinear time, with the goal of estimating t^{⊤}x^{∗} for a given vector t ∈ ℝⁿ and a specific solution x^{∗}. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [Andoni-Krauthgamer-Pogrow, ITCS 2019] to the asymmetric case, which has remained underexplored despite extensive work on nearly-linear-time solvers for RDD/CDD systems. Our first contributions are characterizations of the problem’s mathematical structure. We express a solution x^{∗} via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of 𝐌, termed the maximum p-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of 𝐌 governs the problem’s computational difficulty. For systems with bounded maximum p-norm gap, we develop a collection of algorithmic results for locally approximating t^{⊤}x^{∗} under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum p-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.
Cite as

Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang. On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 89:1-89:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.ITCS.2026.89,
  author =	{Kwok, Tsz Chiu and Wei, Zhewei and Yang, Mingji},
  title =	{{On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{89:1--89:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.89},
  URN =		{urn:nbn:de:0030-drops-253768},
  doi =		{10.4230/LIPIcs.ITCS.2026.89},
  annote =	{Keywords: Spectral Graph Theory, Linear Systems, Sublinear Algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.45
Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them

Authors: Clément L. Canonne, Yun Li, and Seeun William Umboh

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

Abstract
Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a given computational task, are required to provide fast query access to a consistent output solution, without maintaining a state between queries. This paradigm of computation in particular allows for hugely distributed algorithms, where independent instances of a given LCA provide consistent access to a common output solution. The past decade has seen a significant amount of work on LCAs, by and large focusing on graph problems. In this paper, we initiate the study of Local Computation Algorithms for perhaps the archetypal combinatorial optimization problem, Knapsack. We first establish strong impossibility results, ruling out the existence of any non-trivial LCA for Knapsack as several of its relaxations. We then show how equipping the LCA with additional access to the Knapsack instance, namely, weighted item sampling, allows one to circumvent these impossibility results, and obtain sublinear-time and query LCAs. Our positive result draws on a connection to the recent notion of reproducibility for learning algorithms (Impagliazzo, Lei, Pitassi, and Sorrell, 2022), a connection we believe to be of independent interest for the design of LCAs.
Cite as

Clément L. Canonne, Yun Li, and Seeun William Umboh. Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2025.45,
  author =	{Canonne, Cl\'{e}ment L. and Li, Yun and Umboh, Seeun William},
  title =	{{Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-244111},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.45},
  annote =	{Keywords: Local computation algorithms, Knapsack, algorithms, lower bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.61
A Fast Coloring Oracle for Average Case Hypergraphs

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber

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

Abstract
Hypergraph 2-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen 2-colorable 3-uniform hypergraph. Lee, Molla, and Nagle recently extended this to k-uniform hypergraphs for all k ≥ 3. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic 2-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only O(n). Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a 2-coloring of an average 2-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex v, assigns color red/blue to v while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal 2-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time O(1).
Cite as

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. A Fast Coloring Oracle for Average Case Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marcussen_et_al:LIPIcs.APPROX/RANDOM.2025.61,
  author =	{Marcussen, Cassandra and Pyne, Edward and Rubinfeld, Ronitt and Shapira, Asaf and Tauber, Shlomo},
  title =	{{A Fast Coloring Oracle for Average Case Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{61:1--61:13},
  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.61},
  URN =		{urn:nbn:de:0030-drops-244272},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.61},
  annote =	{Keywords: average-case algorithms, local computation algorithms, graph coloring}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.60
Sink-Free Orientations: A Local Sampler with Applications

Authors: Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, and Jiaheng Wang

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

Abstract
For sink-free orientations in graphs of minimum degree at least 3, we show that there is a deterministic approximate counting algorithm that runs in time O((n^33/ε^32)log(n/ε)), a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time O((n/ε)²log(n/ε)), where n denotes the number of vertices of the input graph and 0 < ε < 1 is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019).
Cite as

Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, and Jiaheng Wang. Sink-Free Orientations: A Local Sampler with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 60:1-60:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.APPROX/RANDOM.2025.60,
  author =	{Anand, Konrad and Freifeld, Graham and Guo, Heng and Wang, Chunyang and Wang, Jiaheng},
  title =	{{Sink-Free Orientations: A Local Sampler with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{60:1--60:19},
  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.60},
  URN =		{urn:nbn:de:0030-drops-244267},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.60},
  annote =	{Keywords: Sink-free orientations, local sampling, deterministic counting}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.13
Random Local Access for Sampling k-SAT Solutions

Authors: Dingding Dong and Nitya Mani

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
We present a sublinear time algorithm that gives random local access to the uniform distribution over satisfying assignments to an arbitrary k-SAT formula Φ, at exponential clause density. Our algorithm provides memory-less query access to variable assignments, such that the output variable assignments consistently emulate a single global satisfying assignment whose law is close to the uniform distribution over satisfying assignments to Φ. Random local access and related models have been studied for a wide variety of natural Gibbs distributions and random graphical processes. Here, we establish feasibility of random local access models for one of the most canonical such sample spaces, the set of satisfying assignments to a k-SAT formula. Our algorithm proceeds by leveraging the local uniformity of the uniform distribution over satisfying assignments to Φ. We randomly partition the variables into two subsets, so that each clause has sufficiently many variables from each set to preserve local uniformity. We then sample some variables by simulating a systematic scan Glauber dynamics backward in time, greedily constructing the necessary intermediate steps. We sample the other variables by first conducting a search for a polylogarithmic-sized local component, which we iteratively grow to identify a small subformula from which we can efficiently sample using the appropriate marginal distribution. This two-pronged approach enables us to sample individual variable assignments without constructing a full solution.
Cite as

Dingding Dong and Nitya Mani. Random Local Access for Sampling k-SAT Solutions. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dong_et_al:LIPIcs.SAT.2025.13,
  author =	{Dong, Dingding and Mani, Nitya},
  title =	{{Random Local Access for Sampling k-SAT Solutions}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{13:1--13:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.13},
  URN =		{urn:nbn:de:0030-drops-237474},
  doi =		{10.4230/LIPIcs.SAT.2025.13},
  annote =	{Keywords: sublinear time algorithms, random generation, k-SAT, local computation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.116
A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time

Authors: Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski

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

Abstract
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a 0.5109-approximation algorithm with a running time of Õ(n√n). All previous algorithms either provide only a marginal improvement (e.g., 2^{-280}) over the 0.5-approximation that arises from estimating a maximal matching, or have a running time that is nearly n². Our approach is also arguably much simpler than other algorithms beating 0.5-approximation.
Cite as

Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski. A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ICALP.2025.116,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub},
  title =	{{A 0.51-Approximation of Maximum Matching in Sublinear n^\{1.5\} Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{116:1--116: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.116},
  URN =		{urn:nbn:de:0030-drops-234932},
  doi =		{10.4230/LIPIcs.ICALP.2025.116},
  annote =	{Keywords: Sublinear Algorithms, Maximum Matching, Maximal Matching, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.25
Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation

Authors: Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, and Yanheng Wang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Union volume estimation is a classical algorithmic problem. Given a family of objects O₁,…,O_n ⊂ ℝ^d, we want to approximate the volume of their union. In the special case where all objects are boxes (also called hyperrectangles) this is known as Klee’s measure problem. The state-of-the-art (1+ε)-approximation algorithm [Karp, Luby, Madras '89] for union volume estimation as well as Klee’s measure problem in constant dimension d uses a total of O(n/ε²) queries of three types: (i) determine the volume of O_i; (ii) sample a point uniformly at random from O_i; and (iii) ask whether a given point is contained in O_i. First, we show that if an algorithm learns about the objects only through these types of queries, then Ω(n/ε²) queries are necessary. In this sense, the complexity of [Karp, Luby, Madras '89] is optimal. Our lower bound holds even if the objects are equiponderous axis-aligned polygons in ℝ², if the containment query allows arbitrary (not necessarily sampled) points, and if the algorithm can spend arbitrary time and space examining the query responses. Second, we provide a more efficient approximation algorithm for Klee’s measure problem, which improves the running time from O(n/ε²) to O((n+1/ε²) ⋅ log^{O(d)} (n)). We circumvent our lower bound by exploiting the geometry of boxes in various ways: (1) We sort the boxes into classes of similar shapes after inspecting their corner coordinates. (2) With orthogonal range searching, we show how to sample points from the union of boxes in each class, and how to merge samples from different classes. (3) We bound the amount of wasted work by arguing that most pairs of classes have a small intersection.
Cite as

Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, and Yanheng Wang. Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.SoCG.2025.25,
  author =	{Bringmann, Karl and Larsen, Kasper Green and Nusser, Andr\'{e} and Rotenberg, Eva and Wang, Yanheng},
  title =	{{Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.25},
  URN =		{urn:nbn:de:0030-drops-231778},
  doi =		{10.4230/LIPIcs.SoCG.2025.25},
  annote =	{Keywords: approximation, volume of union, union of objects, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.20
A Formal Language Perspective on Factorized Representations

Authors: Benny Kimelfeld, Wim Martens, and Matthias Niewerth

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Factorized representations (FRs) are a well-known tool to succinctly represent results of join queries and have been originally defined using the named database perspective. We define FRs in the unnamed database perspective and use them to establish several new connections. First, unnamed FRs can be exponentially more succinct than named FRs, but this difference can be alleviated by imposing a disjointness condition on columns. Conversely, named FRs can also be exponentially more succinct than unnamed FRs. Second, unnamed FRs are the same as (i.e., isomorphic to) context-free grammars for languages in which each word has the same length. This tight connection allows us to transfer a wide range of results on context-free grammars to database factorization; of which we offer a selection in the paper. Third, when we generalize unnamed FRs to arbitrary sets of tuples, they become a generalization of path multiset representations, a formalism that was recently introduced to succinctly represent sets of paths in the context of graph database query evaluation.
Cite as

Benny Kimelfeld, Wim Martens, and Matthias Niewerth. A Formal Language Perspective on Factorized Representations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kimelfeld_et_al:LIPIcs.ICDT.2025.20,
  author =	{Kimelfeld, Benny and Martens, Wim and Niewerth, Matthias},
  title =	{{A Formal Language Perspective on Factorized Representations}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.20},
  URN =		{urn:nbn:de:0030-drops-229614},
  doi =		{10.4230/LIPIcs.ICDT.2025.20},
  annote =	{Keywords: Databases, relational databases, graph databases, factorized databases, regular path queries, compact representations}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.30
Fast, Fair and Truthful Distributed Stable Matching for Common Preferences

Authors: Juho Hirvonen and Sara Ranjbaran

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Stable matching is a fundamental problem studied both in economics and computer science. The task is to find a matching between two sides of agents that have preferences over who they want to be matched with. A matching is stable if no pair of agents prefer each other over their current matches. The deferred acceptance algorithm of Gale and Shapley solves this problem in polynomial time. Further, it is a mechanism: the proposing side in the algorithm is always incentivised to report their preferences truthfully. The deferred acceptance algorithm has a natural interpretation as a distributed algorithm (and thus a distributed mechanism). However, the algorithm is slow in the worst case and it is known that the stable matching problem cannot be solved efficiently in the distributed setting. In this work we study a natural special case of the stable matching problem where all agents on one of the two sides share common preferences. We show that in this case the deferred acceptance algorithm does yield a fast and truthful distributed mechanism for finding a stable matching. We show how algorithms for sampling random colorings can be used to break ties fairly and extend the results to fractional stable matching.
Cite as

Juho Hirvonen and Sara Ranjbaran. Fast, Fair and Truthful Distributed Stable Matching for Common Preferences. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirvonen_et_al:LIPIcs.OPODIS.2024.30,
  author =	{Hirvonen, Juho and Ranjbaran, Sara},
  title =	{{Fast, Fair and Truthful Distributed Stable Matching for Common Preferences}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.30},
  URN =		{urn:nbn:de:0030-drops-225666},
  doi =		{10.4230/LIPIcs.OPODIS.2024.30},
  annote =	{Keywords: stable matching, deferred acceptance, local algorithm, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.57
Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

Authors: Shai Vardi

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

Abstract
We consider the problem of sampling a proper k-coloring of a graph of maximal degree Delta uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k >=(1+epsilon)Delta, for any epsilon>0, using a hybrid paths argument.
Cite as

Shai Vardi. Randomly Coloring Graphs of Logarithmically Bounded Pathwidth. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vardi:LIPIcs.APPROX-RANDOM.2018.57,
  author =	{Vardi, Shai},
  title =	{{Randomly Coloring Graphs of Logarithmically Bounded Pathwidth}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.57},
  URN =		{urn:nbn:de:0030-drops-94618},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.57},
  annote =	{Keywords: Random coloring, Glauber dynamics, Markov-chain Monte Carlo}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.50
On the Probe Complexity of Local Computation Algorithms

Authors: Uriel Feige, Boaz Patt-Shamir, and Shai Vardi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching. Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.
Cite as

Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.ICALP.2018.50,
  author =	{Feige, Uriel and Patt-Shamir, Boaz and Vardi, Shai},
  title =	{{On the Probe Complexity of Local Computation Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.50},
  URN =		{urn:nbn:de:0030-drops-90543},
  doi =		{10.4230/LIPIcs.ICALP.2018.50},
  annote =	{Keywords: Local computation algorithms, sublinear algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.716
The Returning Secretary

Authors: Shai Vardi

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In the online random-arrival model, an algorithm receives a sequence of $n$ requests that arrive in a random order. The algorithm is expected to make an irrevocable decision with regard to each request based only on the observed history. We consider the following natural extension of this model: each request arrives k times, and the arrival order is a random permutation of the kn arrivals; the algorithm is expected to make a decision regarding each request only upon its last arrival. We focus primarily on the case when k=2, which can also be interpreted as each request arriving at, and departing from the system, at a random time. We examine the secretary problem: the problem of selecting the best secretary when the secretaries are presented online according to a random permutation. We show that when each secretary arrives twice, we can achieve a competitive ratio of 0.767974... (compared to 1/e in the classical secretary problem), and that it is optimal. We also show that without any knowledge about the number of secretaries or their arrival times, we can still hire the best secretary with probability at least 2/3, in contrast to the impossibility of achieving a constant success probability in the classical setting. We extend our results to the matroid secretary problem, introduced by Babaioff et al. [3], and show a simple algorithm that achieves a 2-approximation to the maximal weighted basis in the new model (for k=2). We show that this approximation factor can be improved in special cases of the matroid secretary problem; in particular, we give a 16/9-competitive algorithm for the returning edge-weighted bipartite matching problem.
Cite as

Shai Vardi. The Returning Secretary. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 716-729, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{vardi:LIPIcs.STACS.2015.716,
  author =	{Vardi, Shai},
  title =	{{The Returning Secretary}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{716--729},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.716},
  URN =		{urn:nbn:de:0030-drops-49539},
  doi =		{10.4230/LIPIcs.STACS.2015.716},
  annote =	{Keywords: online algorithms, secretary problem, matroid secretary}
}
  • Refine by Type
  • 13 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 8 2025
  • 2 2018
  • 1 2015

  • Refine by Author
  • 3 Vardi, Shai
  • 1 Anand, Konrad
  • 1 Bringmann, Karl
  • 1 Canonne, Clément L.
  • 1 Dong, Dingding
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Random walks and Markov chains
  • Show More...

  • Refine by Keyword
  • 2 Local computation algorithms
  • 2 Sublinear Algorithms
  • 1 Approximation Algorithm
  • 1 Art Gallery
  • 1 Average Sensitivity
  • 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