101 Search Results for "Ravi, R."


Document
APPROX
Approximating Submodular k-Partition via Principal Partition Sequence

Authors: Karthekeyan Chandrasekaran and Weihang Wang

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


Abstract
In submodular k-partition, the input is a submodular function f:2^V → ℝ_{≥ 0} (given by an evaluation oracle) along with a positive integer k and the goal is to find a partition of the ground set V into k non-empty parts V_1, V_2, …, V_k in order to minimize ∑_{i=1}^k f(V_i). Narayanan, Roy, and Patkar [Narayanan et al., 1996] designed an algorithm for submodular k-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [R. Ravi and A. Sinha, 2008]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions - namely monotone, symmetric, and posimodular and show the following results: 1) The approximation factor of their algorithm for monotone submodular k-partition is 4/3. This result improves on the 2-factor that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [Santiago, 2021]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. 2) The approximation factor of their algorithm for symmetric submodular k-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. 3) The approximation factor of their algorithm for posimodular submodular k-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k).

Cite as

Karthekeyan Chandrasekaran and Weihang Wang. Approximating Submodular k-Partition via Principal Partition Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2023.3,
  author =	{Chandrasekaran, Karthekeyan and Wang, Weihang},
  title =	{{Approximating Submodular k-Partition via Principal Partition Sequence}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  URN =		{urn:nbn:de:0030-drops-188284},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  annote =	{Keywords: Approximation algorithms}
}
Document
MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Authors: Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants. Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).

Cite as

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.ITC.2023.11,
  author =	{Keller, Hannah and Orlandi, Claudio and Paskin-Cherniavsky, Anat and Ravi, Divya},
  title =	{{MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183391},
  doi =		{10.4230/LIPIcs.ITC.2023.11},
  annote =	{Keywords: Secure Multiparty Computation, Bottleneck Complexity, Information-theoretic}
}
Document
Secure Communication in Dynamic Incomplete Networks

Authors: Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
In this paper, we explore the feasibility of reliable and private communication in dynamic networks, where in each round the adversary can choose which direct peer-to-peer links are available in the network graph, under the sole condition that the graph is k-connected at each round (for some k). We show that reliable communication is possible in such a dynamic network if and only if k > 2t. We also show that if k = cn > 2 t for a constant c, we can achieve reliable communication with polynomial round and communication complexity. For unconditionally private communication, we show that for a passive adversary, k > t is sufficient (and clearly necessary). For an active adversary, we show that k > 2t is sufficient for statistical security (and clearly necessary), while k > 3t is sufficient for perfect security. We conjecture that, in contrast to the static case, k > 2t is not enough for perfect security, and we give evidence that the conjecture is true. Once we have reliable and private communication between each pair of parties, we can emulate a complete network with secure channels, and we can use known protocols to do secure computation.

Cite as

Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov. Secure Communication in Dynamic Incomplete Networks. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.13,
  author =	{Damg\r{a}rd, Ivan and Ravi, Divya and Tschudi, Daniel and Yakoubov, Sophia},
  title =	{{Secure Communication in Dynamic Incomplete Networks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.13},
  URN =		{urn:nbn:de:0030-drops-183419},
  doi =		{10.4230/LIPIcs.ITC.2023.13},
  annote =	{Keywords: Secure Communication, Dynamic Incomplete Network, Information-theoretic}
}
Document
Differentially Private Aggregation via Imperfect Shuffling

Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, and Samson Zhou

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
In this paper, we introduce the imperfect shuffle differential privacy model, where messages sent from users are shuffled in an almost uniform manner before being observed by a curator for private aggregation. We then consider the private summation problem. We show that the standard split-and-mix protocol by Ishai et. al. [FOCS 2006] can be adapted to achieve near-optimal utility bounds in the imperfect shuffle model. Specifically, we show that surprisingly, there is no additional error overhead necessary in the imperfect shuffle model.

Cite as

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, and Samson Zhou. Differentially Private Aggregation via Imperfect Shuffling. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ITC.2023.17,
  author =	{Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Nelson, Jelani and Zhou, Samson},
  title =	{{Differentially Private Aggregation via Imperfect Shuffling}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{17:1--17:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.17},
  URN =		{urn:nbn:de:0030-drops-183453},
  doi =		{10.4230/LIPIcs.ITC.2023.17},
  annote =	{Keywords: Differential privacy, private summation, shuffle model}
}
Document
Track A: Algorithms, Complexity and Games
On Differentially Private Counting on Trees

Authors: Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a new error measure for this problem by considering a combination of multiplicative and additive approximation to the query results. We examine known mechanisms in differential privacy (DP) and prove their optimality, under this measure, in the pure-DP setting. In the approximate-DP setting, we design new algorithms achieving significant improvements over known ones.

Cite as

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On Differentially Private Counting on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ICALP.2023.66,
  author =	{Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Wu, Kewen},
  title =	{{On Differentially Private Counting on Trees}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{66:1--66:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.66},
  URN =		{urn:nbn:de:0030-drops-181186},
  doi =		{10.4230/LIPIcs.ICALP.2023.66},
  annote =	{Keywords: Differential Privacy, Algorithms, Trees, Hierarchies}
}
Document
Online Paging with Heterogeneous Cache Slots

Authors: Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, and Neal E. Young

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
It is natural to generalize the online k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To initiate a systematic study of this generalization, we focus on uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family 𝒮 ⊆ 2^[k] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family 𝒮. If all request sets are allowed (𝒮 = 2^[k]), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging (𝒮 = {[k]}). As a function of |𝒮| and k, the optimal deterministic ratio is polynomial: at most O(k²|𝒮|) and at least Ω(√{|𝒮|}). For any laminar family {𝒮} of height h, the optimal ratios are O(hk) (deterministic) and O(h²log k) (randomized). The special case that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. For All-or-One Paging the optimal competitive ratios are Θ(k) (deterministic) and Θ(log k) (randomized), while the offline problem is NP-hard. We extend the deterministic upper bound to the weighted variant of All-or-One Paging (a generalization of standard Weighted Paging), showing that it is also Θ(k). Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set P of pages, and is satisfied by fetching any page from P into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and hH_k (randomized).

Cite as

Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, and Neal E. Young. Online Paging with Heterogeneous Cache Slots. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chrobak_et_al:LIPIcs.STACS.2023.23,
  author =	{Chrobak, Marek and Haney, Samuel and Liaee, Mehraneh and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi and Young, Neal E.},
  title =	{{Online Paging with Heterogeneous Cache Slots}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.23},
  URN =		{urn:nbn:de:0030-drops-176759},
  doi =		{10.4230/LIPIcs.STACS.2023.23},
  annote =	{Keywords: Caching and paging algorithms, k-server, weighted paging, laminar family}
}
Document
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees

Authors: Marc Dufay, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the "virtual machine packing" problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of "reduced length".

Cite as

Marc Dufay, Claire Mathieu, and Hang Zhou. An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.STACS.2023.27,
  author =	{Dufay, Marc and Mathieu, Claire and Zhou, Hang},
  title =	{{An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.27},
  URN =		{urn:nbn:de:0030-drops-176794},
  doi =		{10.4230/LIPIcs.STACS.2023.27},
  annote =	{Keywords: vehicle routing, distance constraint, approximation algorithms, trees}
}
Document
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

Authors: Papri Dey, Ravi Kannan, Nick Ryder, and Nikhil Srivastava

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


Abstract
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an ε-approximation to the Jordan Normal form of an integer matrix with a-bit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for ε-approximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational a-bit coefficients having a-bit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.

Cite as

Papri Dey, Ravi Kannan, Nick Ryder, and Nikhil Srivastava. Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2023.42,
  author =	{Dey, Papri and Kannan, Ravi and Ryder, Nick and Srivastava, Nikhil},
  title =	{{Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.42},
  URN =		{urn:nbn:de:0030-drops-175450},
  doi =		{10.4230/LIPIcs.ITCS.2023.42},
  annote =	{Keywords: Symbolic algorithms, numerical algorithms, linear algebra}
}
Document
Algorithms with More Granular Differential Privacy Guarantees

Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Thomas Steinke

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


Abstract
Differential privacy is often applied with a privacy parameter that is larger than the theory suggests is ideal; various informal justifications for tolerating large privacy parameters have been proposed. In this work, we consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. We study several basic data analysis and learning tasks in this framework, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person (i.e., all the attributes).

Cite as

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Thomas Steinke. Algorithms with More Granular Differential Privacy Guarantees. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 54:1-54:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ITCS.2023.54,
  author =	{Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Steinke, Thomas},
  title =	{{Algorithms with More Granular Differential Privacy Guarantees}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{54:1--54:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.54},
  URN =		{urn:nbn:de:0030-drops-175574},
  doi =		{10.4230/LIPIcs.ITCS.2023.54},
  annote =	{Keywords: Differential Privacy, Algorithms, Per-Attribute Privacy}
}
Document
Private Counting of Distinct and k-Occurring Items in Time Windows

Authors: Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi

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


Abstract
In this work, we study the task of estimating the numbers of distinct and k-occurring items in a time window under the constraint of differential privacy (DP). We consider several variants depending on whether the queries are on general time windows (between times t₁ and t₂), or are restricted to being cumulative (between times 1 and t₂), and depending on whether the DP neighboring relation is event-level or the more stringent item-level. We obtain nearly tight upper and lower bounds on the errors of DP algorithms for these problems. En route, we obtain an event-level DP algorithm for estimating, at each time step, the number of distinct items seen over the last W updates with error polylogarithmic in W; this answers an open question of Bolot et al. (ICDT 2013).

Cite as

Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. Private Counting of Distinct and k-Occurring Items in Time Windows. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 55:1-55:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ITCS.2023.55,
  author =	{Ghazi, Badih and Kumar, Ravi and Nelson, Jelani and Manurangsi, Pasin},
  title =	{{Private Counting of Distinct and k-Occurring Items in Time Windows}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{55:1--55:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.55},
  URN =		{urn:nbn:de:0030-drops-175580},
  doi =		{10.4230/LIPIcs.ITCS.2023.55},
  annote =	{Keywords: Differential Privacy, Algorithms, Distinct Elements, Time Windows}
}
Document
Online Metric Allocation and Time-Varying Regularization

Authors: Nikhil Bansal and Christian Coester

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an n-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional k-server. Because of an inherent scale-freeness property of the problem, existing techniques for MTS and k-server fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)-competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is time-varying. Using this perspective, we further refine the guarantees of our algorithm. We also consider the case of non-convex cost functions. Using a simple 𝓁₂²-regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics.

Cite as

Nikhil Bansal and Christian Coester. Online Metric Allocation and Time-Varying Regularization. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.ESA.2022.13,
  author =	{Bansal, Nikhil and Coester, Christian},
  title =	{{Online Metric Allocation and Time-Varying Regularization}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.13},
  URN =		{urn:nbn:de:0030-drops-169515},
  doi =		{10.4230/LIPIcs.ESA.2022.13},
  annote =	{Keywords: Online algorithms, competitive analysis, k-server, metrical task systems, mirror descent, regularization}
}
Document
Stochastic Route Planning for Electric Vehicles

Authors: Payas Rajan and Chinya V. Ravishankar

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
Electric Vehicle routing is often modeled as a generalization of the energy-constrained shortest path problem, taking travel times and energy consumptions on road network edges to be deterministic. In practice, however, energy consumption and travel times are stochastic distributions, typically estimated from real-world data. Consequently, real-world routing algorithms can make only probabilistic feasibility guarantees. Current stochastic route planning methods either fail to ensure that routes are energy-feasible, or if they do, have not been shown to scale well to large graphs. Our work bridges this gap by finding routes to maximize on-time arrival probability and the set of non-dominated routes under two criteria for stochastic route feasibility: 𝔼-feasibility and p-feasibility. Our 𝔼-feasibility criterion ensures energy-feasibility in expectation, using expected energy values along network edges. Our p-feasibility criterion accounts for the actual distribution along edges, and keeps the stranding probability along the route below a user-specified threshold p. We generalize the charging function propagation algorithm to accept stochastic edge weights to find routes that maximize the probability of on-time arrival, while maintaining 𝔼- or p-feasibility. We also extend multi-criteria Contraction Hierarchies to accept stochastic edge weights and offer heuristics to speed up queries. Our experiments on a real-world road network instance of the Los Angeles area show that our methods answer stochastic queries in reasonable time, that the two criteria produce similar routes for longer deadlines, but that 𝔼-feasibility queries can be much faster than p-feasibility queries.

Cite as

Payas Rajan and Chinya V. Ravishankar. Stochastic Route Planning for Electric Vehicles. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{rajan_et_al:LIPIcs.SEA.2022.15,
  author =	{Rajan, Payas and Ravishankar, Chinya V.},
  title =	{{Stochastic Route Planning for Electric Vehicles}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.15},
  URN =		{urn:nbn:de:0030-drops-165497},
  doi =		{10.4230/LIPIcs.SEA.2022.15},
  annote =	{Keywords: Stochastic Routing, Electric Vehicles, Route Planning Algorithms}
}
Document
Maniposynth: Bimodal Tangible Functional Programming

Authors: Brian Hempel and Ravi Chugh

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)


Abstract
Traditionally, writing code is a non-graphical, abstract, and linear process. Not everyone is comfortable with this way of thinking at all times. Can programming be transformed into a graphical, concrete, non-linear activity? While nodes-and-wires [Sutherland, 1966] and blocks-based [Begel, 1996] programming environments do leverage graphical direct manipulation, users perform their manipulations on abstract syntax tree elements, which are still abstract. Is it possible to be more concrete - could users instead directly manipulate live program values to create their program? We present a system, Maniposynth, that reimagines functional programming as a non-linear workflow where program expressions are spread on a 2D canvas. The live results of those expressions are continuously displayed and available for direct manipulation. The non-linear canvas liberates users to work out-of-order, and the live values can be interacted with via drag-and-drop. Incomplete programs are gracefully handled via hole expressions, which allow Maniposynth to offer program synthesis. Throughout the workflow, the program is valid OCaml code which the user may inspect and edit in their preferred text editor at any time. With Maniposynth’s direct manipulation features, we created 38 programs drawn from a functional data structures course. We additionally hired two professional OCaml developers to implement a subset of these programs. We report on these experiences and discuss to what degree Maniposynth meets its goals of providing a non-linear, concrete, graphical programming workflow.

Cite as

Brian Hempel and Ravi Chugh. Maniposynth: Bimodal Tangible Functional Programming. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hempel_et_al:LIPIcs.ECOOP.2022.16,
  author =	{Hempel, Brian and Chugh, Ravi},
  title =	{{Maniposynth: Bimodal Tangible Functional Programming}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.16},
  URN =		{urn:nbn:de:0030-drops-162445},
  doi =		{10.4230/LIPIcs.ECOOP.2022.16},
  annote =	{Keywords: direct manipulation, tangible programming, programming user interfaces}
}
Document
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Authors: Noah Shutty and Mary Wootters

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions F:F^k → F of some data 𝐱 ∈ F^k, given access to an encoding 𝐜 ∈ Fⁿ of 𝐱 under an error correcting code. In our model - relevant in distributed storage, distributed computation and secret sharing - each symbol of 𝐜 is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute F(𝐱). Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let ε > 0 and let 𝒞: F^k → Fⁿ be a full-length Reed-Solomon code of rate 1 - ε over a field F with constant characteristic. For any γ ∈ [0, ε), our scheme can compute any linear function F(𝐱) given access to any (1 - γ)-fraction of the symbols of 𝒞(𝐱), with download bandwidth O(n/(ε - γ)) bits. In contrast, the naive scheme that involves reconstructing the data 𝐱 and then computing F(𝐱) uses Θ(n log n) bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.

Cite as

Noah Shutty and Mary Wootters. Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{shutty_et_al:LIPIcs.ITCS.2022.117,
  author =	{Shutty, Noah and Wootters, Mary},
  title =	{{Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.117},
  URN =		{urn:nbn:de:0030-drops-157130},
  doi =		{10.4230/LIPIcs.ITCS.2022.117},
  annote =	{Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation}
}
Document
Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH

Authors: Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)


Abstract
In this article we study a well-known problem, called Bipartite Token Jumping and not-so-well known problem(s), which we call, Half (Induced-) Subgraph, and show that under Gap-ETH, these problems do not admit FPT algorithms. The problem Bipartite Token Jumping takes as input a bipartite graph G and two independent sets S,T in G, where |S| = |T| = k, and the objective is to test if there is a sequence of exactly k-sized independent sets ⟨ I₀, I₁,⋯, I_𝓁 ⟩ in G, such that: i) I₀ = S and I_𝓁 = T, and ii) for every j ∈ [𝓁], I_{j} is obtained from I_{j-1} by replacing a vertex in I_{j-1} by a vertex in V(G) ⧵ I_{j-1}. We show that, assuming Gap-ETH, Bipartite Token Jumping does not admit an FPT algorithm. We note that this result resolves one of the (two) open problems posed by Bartier et al. (ISAAC 2020), under Gap-ETH. Most of the known reductions related to Token Jumping exploit the property given by triangles (i.e., C₃s), to obtain the correctness, and our results refutes FPT algorithm for Bipartite Token Jumping, where the input graph cannot have any triangles. For an integer k ∈ ℕ, the half graph S_{k,k} is the graph with vertex set V(S_{k,k}) = A_k ∪ B_k, where A_k = {a₁,a₂,⋯, a_k} and B_k = {b₁,b₂,⋯, b_k}, and for i,j ∈ [k], {a_i,b_j} ∈ E(T_{k,k}) if and only if j ≥ i. We also study the Half (Induced-)Subgraph problem where we are given a graph G and an integer k, and the goal is to check if G contains S_{k,k} as an (induced-)subgraph. Again under Gap-ETH, we show that Half (Induced-)Subgraph does not admit an FPT algorithm, even when the input is a bipartite graph. We believe that the above problem (and its negative) result maybe of independent interest and could be useful obtaining new fixed parameter intractability results. There are very few reductions known in the literature which refute FPT algorithms for a parameterized problem based on assumptions like Gap-ETH. Thus our technique (and simple reductions) exhibits the potential of such conjectures in obtaining new (and possibly easier) proofs for refuting FPT algorithms for parameterized problems.

Cite as

Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula. Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2021.2,
  author =	{Agrawal, Akanksha and Allumalla, Ravi Kiran and Dhanekula, Varun Teja},
  title =	{{Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.2},
  URN =		{urn:nbn:de:0030-drops-153851},
  doi =		{10.4230/LIPIcs.IPEC.2021.2},
  annote =	{Keywords: Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, Gap-Exponential Time Hypothesis}
}
  • Refine by Author
  • 14 Ravi, R.
  • 9 Kumar, Ravi
  • 6 Ghazi, Badih
  • 6 Manurangsi, Pasin
  • 5 Rajaraman, Rajmohan
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Online algorithms
  • 4 Theory of computation → Routing and network design problems
  • 3 Theory of computation → Approximation algorithms analysis
  • 3 Theory of computation → Theory of database privacy and security
  • 2 Human-centered computing → Human computer interaction (HCI)
  • Show More...

  • Refine by Keyword
  • 5 Approximation Algorithms
  • 5 Approximation algorithms
  • 4 Algorithms
  • 4 Differential Privacy
  • 3 Online algorithms
  • Show More...

  • Refine by Type
  • 101 document

  • Refine by Publication Year
  • 40 2009
  • 10 2019
  • 10 2023
  • 8 2017
  • 7 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail