9 Search Results for "Ronen, Eyal"

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

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean

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

Abstract
Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data x and Bob holds m inputs y_1, …, y_m. They want to compute m instances of a bipartite relation R(⋅,⋅) on every pair (x, y_1), …, (x, y_m). We call this the asymmetric direct sum question for one-way communication. We give examples where the quantum communication complexity of such problems scales polynomially with m, while the classical communication complexity depends at most logarithmically on m. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications.
Cite as

Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean. Consumable Data via Quantum Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.APPROX/RANDOM.2025.39,
  author =	{Gilboa, Dar and Jain, Siddhartha and McClean, Jarrod R.},
  title =	{{Consumable Data via Quantum Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-244059},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.39},
  annote =	{Keywords: quantum communication, one-time programs, data markets}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.33
Bit-Fixing Extractors for Almost-Logarithmic Entropy

Authors: Dean Doron and Ori Fridman

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

Abstract
An oblivious bit-fixing source is a distribution over {0,1}ⁿ, where k bits are uniform and independent and the rest n-k are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity theory. We construct explicit extractors for oblivious bit-fixing source that support k = Õ(log n), outputting almost all the entropy with low error. The previous state-of-the-art construction that outputs many bits is due to Rao [Rao, CCC '09], and requires entropy k ≥ log^{c} n for some large constant c. The two key components in our constructions are new low-error affine condensers for poly-logarithmic entropies (that we achieve using techniques from the nonmalleable extractors literature), and a dual use of linear condensers for OBF sources.
Cite as

Dean Doron and Ori Fridman. Bit-Fixing Extractors for Almost-Logarithmic Entropy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.33,
  author =	{Doron, Dean and Fridman, Ori},
  title =	{{Bit-Fixing Extractors for Almost-Logarithmic Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-243994},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.33},
  annote =	{Keywords: Seedless extractors, oblivious bit-fixing sources}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.67
On Sums of INW Pseudorandom Generators

Authors: William M. Hoza and Zelin Lv

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

Abstract
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let X be the n-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter λ. We prove that the bitwise XOR of t independent copies of X fools width-w programs with error n^{log(w + 1)} ⋅ (λ⋅log n)^t. Notably, this error bound is meaningful even for relatively large values of λ such as λ = 1/O(log n). Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs - it just gives a new way of re-proving the well-known O(log² n) bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our "XOR of INW" approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-3 programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably Ω(log² n). Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on t correlated seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
Cite as

William M. Hoza and Zelin Lv. On Sums of INW Pseudorandom Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.67,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{On Sums of INW Pseudorandom Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{67:1--67:24},
  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.67},
  URN =		{urn:nbn:de:0030-drops-244330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.67},
  annote =	{Keywords: INW generator, pseudorandomness, space-bounded computation, XOR Lemmas}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.16
Direct Sums for Parity Decision Trees

Authors: Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(k) times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.
Cite as

Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, and Weiqiang Yuan. Direct Sums for Parity Decision Trees. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 16:1-16:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{besselman_et_al:LIPIcs.CCC.2025.16,
  author =	{Besselman, Tyler and G\"{o}\"{o}s, Mika and Guo, Siyao and Maystre, Gilbert and Yuan, Weiqiang},
  title =	{{Direct Sums for Parity Decision Trees}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{16:1--16:38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.16},
  URN =		{urn:nbn:de:0030-drops-237105},
  doi =		{10.4230/LIPIcs.CCC.2025.16},
  annote =	{Keywords: direct sum, parity decision trees, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.82
Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes

Authors: Nicolas Resch, Chen Yuan, and Yihan Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code 𝒞 ⊆ [q]ⁿ is (p,𝓁,L)-list-recoverable if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = 𝓁, the number of codewords c ∈ 𝒞 such that c_i ∉ Y_i for at most pn choices of i ∈ [n] is less than L; list-decoding is the special case of 𝓁 = 1. In recent work by Resch, Yuan and Zhang (ICALP 2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes p_*: = p_*(q,𝓁,L) with the property that for all ε > 0 (a) there exist positive-rate (p_*-ε,𝓁,L)-list-recoverable codes, and (b) any (p_*+ε,𝓁,L)-list-recoverable code has rate 0. In fact, in the latter case the code has constant size, independent on n. However, the constant size in their work is quite large in 1/ε, at least |𝒞| ≥ (1/(ε))^O(q^L). Our contribution in this work is to show that for all choices of q,𝓁 and L with q ≥ 3, any (p_*+ε,𝓁,L)-list-recoverable code must have size O_{q,𝓁,L}(1/ε), and furthermore this upper bound is complemented by a matching lower bound Ω_{q,𝓁,L}(1/ε). This greatly generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf. Theory 2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for q = 2 and even L, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work. Our main technical contribution is to (a) properly define a linear programming relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate that a certain function defined on a q-ary probability simplex is maximized by the uniform distribution. This represents the core challenge in generalizing to larger q (as a binary simplex can be naturally identified with a one-dimensional interval). We can subsequently re-utilize certain Schur convexity and convexity properties established for a related function by Resch, Yuan and Zhang along with ideas of Alon, Bukh and Polyanskiy.
Cite as

Nicolas Resch, Chen Yuan, and Yihan Zhang. Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 82:1-82:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{resch_et_al:LIPIcs.ITCS.2025.82,
  author =	{Resch, Nicolas and Yuan, Chen and Zhang, Yihan},
  title =	{{Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{82:1--82:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.82},
  URN =		{urn:nbn:de:0030-drops-227103},
  doi =		{10.4230/LIPIcs.ITCS.2025.82},
  annote =	{Keywords: List Decoding, List Recovery, Zero Rate}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.42
Nearest Neighbor Complexity and Boolean Circuits

Authors: Mason DiCicco, Vladimir Podolskii, and Daniel Reichman

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A nearest neighbor representation of a Boolean function f is a set of vectors (anchors) labeled by 0 or 1 such that f(x) = 1 if and only if the closest anchor to x is labeled by 1. This model was introduced by Hajnal, Liu and Turán [2022], who studied bounds on the minimum number of anchors required to represent Boolean functions under different choices of anchors (real vs. Boolean vectors) as well as the analogous model of k-nearest neighbors representations. We initiate a systematic study of the representational power of nearest and k-nearest neighbors through Boolean circuit complexity. To this end, we establish a close connection between Boolean functions with polynomial nearest neighbor complexity and those that can be efficiently represented by classes based on linear inequalities - min-plus polynomial threshold functions - previously studied in relation to threshold circuits. This extends an observation of Hajnal et al. [2022]. Next, we further extend the connection between nearest neighbor representations and circuits to the k-nearest neighbors case. As an outcome of these connections we obtain exponential lower bounds on the k-nearest neighbors complexity of explicit n-variate functions, assuming k ≤ n^{1-ε}. Previously, no superlinear lower bound was known for any k > 1. At the same time, we show that proving superpolynomial lower bounds for the k-nearest neighbors complexity of an explicit function for arbitrary k would require a breakthrough in circuit complexity. In addition, we prove an exponential separation between the nearest neighbor and k-nearest neighbors complexity (for unrestricted k) of an explicit function. These results address questions raised by [Hajnal et al., 2022] of proving strong lower bounds for k-nearest neighbors and understanding the role of the parameter k. Finally, we devise new bounds on the nearest neighbor complexity for several families of Boolean functions.
Cite as

Mason DiCicco, Vladimir Podolskii, and Daniel Reichman. Nearest Neighbor Complexity and Boolean Circuits. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dicicco_et_al:LIPIcs.ITCS.2025.42,
  author =	{DiCicco, Mason and Podolskii, Vladimir and Reichman, Daniel},
  title =	{{Nearest Neighbor Complexity and Boolean Circuits}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.42},
  URN =		{urn:nbn:de:0030-drops-226704},
  doi =		{10.4230/LIPIcs.ITCS.2025.42},
  annote =	{Keywords: Complexity, Nearest Neighbors, Circuits}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.4
Error Resilient Space Partitioning (Invited Talk)

Authors: Orr Dunkelman, Zeev Geyzel, Chaya Keller, Nathan Keller, Eyal Ronen, Adi Shamir, and Ran J. Tessler

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In this paper we consider a new type of space partitioning which bridges the gap between continuous and discrete spaces in an error resilient way. It is motivated by the problem of rounding noisy measurements from some continuous space such as ℝ^d to a discrete subset of representative values, in which each tile in the partition is defined as the preimage of one of the output points. Standard rounding schemes seem to be inherently discontinuous across tile boundaries, but in this paper we show how to make it perfectly consistent (with error resilience ε) by guaranteeing that any pair of consecutive measurements X₁ and X₂ whose L₂ distance is bounded by ε will be rounded to the same nearby representative point in the discrete output space. We achieve this resilience by allowing a few bits of information about the first measurement X₁ to be unidirectionally communicated to and used by the rounding process of the second measurement X₂. Minimizing this revealed information can be particularly important in privacy-sensitive applications such as COVID-19 contact tracing, in which we want to find out all the cases in which two persons were at roughly the same place at roughly the same time, by comparing cryptographically hashed versions of their itineraries in an error resilient way. The main problem we study in this paper is characterizing the achievable tradeoffs between the amount of information provided and the error resilience for various dimensions. We analyze the problem by considering the possible colored tilings of the space with k available colors, and use the color of the tile in which X₁ resides as the side information. We obtain our upper and lower bounds with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Sperner’s lemma, and Čech cohomology. In particular, we show that when X_i ∈ ℝ^d, communicating log₂(d+1) bits of information is both sufficient and necessary (in the worst case) to achieve positive resilience, and when d=3 we obtain a tight upper and lower asymptotic bound of (0.561 …)k^{1/3} on the achievable error resilience when we provide log₂(k) bits of information about X₁’s color.
Cite as

Orr Dunkelman, Zeev Geyzel, Chaya Keller, Nathan Keller, Eyal Ronen, Adi Shamir, and Ran J. Tessler. Error Resilient Space Partitioning (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dunkelman_et_al:LIPIcs.ICALP.2021.4,
  author =	{Dunkelman, Orr and Geyzel, Zeev and Keller, Chaya and Keller, Nathan and Ronen, Eyal and Shamir, Adi and Tessler, Ran J.},
  title =	{{Error Resilient Space Partitioning}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.4},
  URN =		{urn:nbn:de:0030-drops-140731},
  doi =		{10.4230/LIPIcs.ICALP.2021.4},
  annote =	{Keywords: space partition, high-dimensional rounding, error resilience, sphere packing, Sperner’s lemma, Brunn-Minkowski theorem, \v{C}ech cohomology}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.13
Tight Bounds on Online Checkpointing Algorithms

Authors: Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir

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

Abstract
The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.
Cite as

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir. Tight Bounds on Online Checkpointing Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baron_et_al:LIPIcs.ICALP.2018.13,
  author =	{Bar-On, Achiya and Dinur, Itai and Dunkelman, Orr and Hod, Rani and Keller, Nathan and Ronen, Eyal and Shamir, Adi},
  title =	{{Tight Bounds on Online Checkpointing Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{13:1--13:13},
  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.13},
  URN =		{urn:nbn:de:0030-drops-90179},
  doi =		{10.4230/LIPIcs.ICALP.2018.13},
  annote =	{Keywords: checkpoint, checkpointing algorithm, online algorithm, uniform distribution, discrepancy}
}
  • Refine by Type
  • 9 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 6 2025
  • 1 2021
  • 1 2018

  • Refine by Author
  • 2 Dunkelman, Orr
  • 2 Keller, Nathan
  • 2 Ronen, Eyal
  • 2 Shamir, Adi
  • 1 Bar-On, Achiya
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Communication complexity
  • 2 Theory of computation → Computational pricing and auctions
  • 1 Mathematics of computing → Coding theory
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Algorithmic mechanism design
  • Show More...

  • Refine by Keyword
  • 1 Auctions
  • 1 Brunn-Minkowski theorem
  • 1 Circuits
  • 1 Communication Complexity
  • 1 Complexity
  • 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