9 Search Results for "Feldman, Vitaly"

Document
DOI: 10.4230/LIPIcs.ESA.2024.3
From Donkeys to Kings in Tournaments

Authors: Amir Abboud, Tomer Grossman, Moni Naor, and Tomer Solomon

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a king. We study the complexity of finding k kings in a tournament graph. We show that the randomized query complexity of finding k ≤ 3 kings is O(n), and for the deterministic case it takes the same amount of queries (up to a constant) as finding a single king (the best known deterministic algorithm makes O(n^{3/2}) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n²) queries, even in the randomized case. We consider the RAM model for k ≥ 4. We show an algorithm that finds k kings in time O(kn²), which is optimal for constant values of k. Alternatively, one can also find k ≥ 4 kings in time n^{ω} (the time for matrix multiplication). We provide evidence that this is optimal for large k by suggesting a fine-grained reduction from a variant of the triangle detection problem.
Cite as

Amir Abboud, Tomer Grossman, Moni Naor, and Tomer Solomon. From Donkeys to Kings in Tournaments. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ESA.2024.3,
  author =	{Abboud, Amir and Grossman, Tomer and Naor, Moni and Solomon, Tomer},
  title =	{{From Donkeys to Kings in Tournaments}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.3},
  URN =		{urn:nbn:de:0030-drops-210740},
  doi =		{10.4230/LIPIcs.ESA.2024.3},
  annote =	{Keywords: Tournament Graphs, Kings, Query Complexity, Fine Grained Complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.38
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Authors: Nader H. Bshouty and George Haddad

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

Abstract
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:ℝ^+ → ℝ^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ^{-1}(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n) ≤ n relevant variables), where k(n) = ω_n(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Γ(n))T(Γ(n)²)-time algorithm that properly learns parities, where Γ(x) = γ(γ(x)). If T(Γ(n)²) = exp({o(n/log n)}), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).
Cite as

Nader H. Bshouty and George Haddad. Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.APPROX/RANDOM.2024.38,
  author =	{Bshouty, Nader H. and Haddad, George},
  title =	{{Approximating the Number of Relevant Variables in a Parity Implies Proper Learning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  URN =		{urn:nbn:de:0030-drops-210316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  annote =	{Keywords: PAC Learning, Random Classification Noise, Uniform Distribution, Parity, Sparcity Approximation}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.61
When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Authors: Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen

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

Abstract
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph G together with a linear inner code C₀. Expander codes are Tanner codes whose defining bipartite graph G has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ and d₀ must satisfy, so that every bipartite expander G with vertex expansion ratio δ and every linear inner code C₀ with minimum distance d₀ together define an expander code that corrects Ω(n) errors in O(n) time? For C₀ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ > 3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ > 2/3-Ω(1) and he also showed that δ > 1/2 is necessary. For general linear code C₀, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d₀ = Ω(cδ^{-2}) is sufficient, where c is the left-degree of G. In this paper, we give a near-optimal solution to the above question for general C₀ by showing that δ d₀ > 3 is sufficient and δ d₀ > 1 is necessary, thereby also significantly improving Dowling-Gao’s result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.
Cite as

Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen. When Can an Expander Code Correct Ω(n) Errors in O(n) Time?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.61,
  author =	{Cheng, Kuan and Ouyang, Minghui and Shangguan, Chong and Shen, Yuanting},
  title =	{{When Can an Expander Code Correct \Omega(n) Errors in O(n) Time?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{61:1--61:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.61},
  URN =		{urn:nbn:de:0030-drops-210543},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.61},
  annote =	{Keywords: expander codes, expander graphs, linear-time decoding}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.64
On the Communication Complexity of Finding a King in a Tournament

Authors: Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

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

Abstract
A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: - We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS'91, Göös, Pitassi, Watson, SICOMP'18] imply a bound of Θ̃(log² n) for finding a source (if it exists, or outputting that there is no source) in a tournament. - The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ̃(√n). - The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ̃(n) and Θ̃(√n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP'03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.
Cite as

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Communication Complexity of Finding a King in a Tournament. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 64:1-64:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.APPROX/RANDOM.2024.64,
  author =	{Mande, Nikhil S. and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Communication Complexity of Finding a King in a Tournament}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{64:1--64:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  URN =		{urn:nbn:de:0030-drops-210571},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  annote =	{Keywords: Communication complexity, tournaments, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.4
Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient

Authors: Badih Ghazi, Ravi Kumar, and Pasin Manurangsi

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We obtain a new protocol for binary counting in the ε-DP_shuffle model with error O(1/ε) and expected communication Õ((log n)/ε) messages per user. Previous protocols incur either an error of O(1/ε^1.5) with O_ε(log n) messages per user (Ghazi et al., ITC 2020) or an error of O(1/ε) with O_ε(n²) messages per user (Cheu and Yan, TPDP 2022). Using the new protocol, we obtained improved ε-DP_shuffle protocols for real summation and histograms.
Cite as

Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ITC.2024.4,
  author =	{Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin},
  title =	{{Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.4},
  URN =		{urn:nbn:de:0030-drops-205127},
  doi =		{10.4230/LIPIcs.ITC.2024.4},
  annote =	{Keywords: Differential Privacy, Shuffle Model, Aggregation, Pure Differential Privacy}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.6
Information-Theoretic Single-Server PIR in the Shuffle Model

Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every γ > 0, the protocol has O(n^{γ}) communication and computation costs per (stateless) client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.
Cite as

Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma. Information-Theoretic Single-Server PIR in the Shuffle Model. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.ITC.2024.6,
  author =	{Ishai, Yuval and Kelkar, Mahimna and Lee, Daniel and Ma, Yiping},
  title =	{{Information-Theoretic Single-Server PIR in the Shuffle Model}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.6},
  URN =		{urn:nbn:de:0030-drops-205142},
  doi =		{10.4230/LIPIcs.ITC.2024.6},
  annote =	{Keywords: Private information retrieval, Shuffle model}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.97
Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Authors: Yotam Kenneth and Robert Krauthgamer

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

Abstract
In cut sparsification, all cuts of a hypergraph H = (V,E,w) are approximated within 1±ε factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge e is provided by a splitting function g_e: 2^e → ℝ_+. This generalization is called a submodular hypergraph when the functions {g_e}_{e ∈ E} are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work studied the setting where H' is a reweighted sub-hypergraph of H, and measured the size of H' by the number of hyperedges in it. In this setting, we present two results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n = |V| and ε^{-1}; (ii) we propose a new parameter, called spread, and use it to obtain smaller sparsifiers in some cases. We also show that for a natural family of splitting functions, relaxing the requirement that H' be a reweighted sub-hypergraph of H yields a substantially smaller encoding of the cuts of H (almost a factor n in the number of bits). This is in contrast to graphs, where the most succinct representation is attained by reweighted subgraphs. A new tool in our construction of succinct representation is the notion of deformation, where a splitting function g_e is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions.
Cite as

Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kenneth_et_al:LIPIcs.ICALP.2024.97,
  author =	{Kenneth, Yotam and Krauthgamer, Robert},
  title =	{{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{97:1--97:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.97},
  URN =		{urn:nbn:de:0030-drops-202406},
  doi =		{10.4230/LIPIcs.ICALP.2024.97},
  annote =	{Keywords: Cut Sparsification, Submodular Hypergraphs, Succinct Representation}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.15
Pure Differentially Private Summation from Anonymous Messages

Authors: Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically: - For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-differentially private protocol for estimating the number of ones held by the users up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log n) one-bit messages. This is the first pure protocol in the shuffled model with error o(√n) for constant values of ε. Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers in [0, 1] up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log³ n) messages each consisting of O(log log n) bits. - In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n^{0.5-Ω(1)}, the per user communication has to be at least Ω_{ε}(√{log n}) bits. This implies (i) the first separation between the (bounded-communication) multi-message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model. Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question that might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X⁰ and X^1 supported on {0, … , m} such that (i) the total variation distance between X⁰ and X^1 is at least 1 - γ, and (ii) the moment generating functions of X⁰ and X^1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(√{log(1/γ)}).
Cite as

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Pure Differentially Private Summation from Anonymous Messages. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ghazi_et_al:LIPIcs.ITC.2020.15,
  author =	{Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin and Pagh, Rasmus and Velingker, Ameya},
  title =	{{Pure Differentially Private Summation from Anonymous Messages}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.15},
  URN =		{urn:nbn:de:0030-drops-121208},
  doi =		{10.4230/LIPIcs.ITC.2020.15},
  annote =	{Keywords: Pure differential privacy, Shuffled model, Anonymous messages, Summation, Communication bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.41
On the Power of Learning from k-Wise Queries

Authors: Vitaly Feldman and Badih Ghazi

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication algorithms rely on queries that provide information about a function of a single sample. (For example, a statistical query (SQ) gives an estimate of Ex_{x ~ D}[q(x)] for any choice of the query function q mapping X to the reals, where D is an unknown data distribution over X.) Yet some data analysis algorithms rely on properties of functions that depend on multiple samples. Such algorithms would be naturally implemented using k-wise queries each of which is specified by a function q mapping X^k to the reals. Hence it is natural to ask whether algorithms using k-wise queries can solve learning problems more efficiently and by how much. Blum, Kalai and Wasserman (2003) showed that for any weak PAC learning problem over a fixed distribution, the complexity of learning with k-wise SQs is smaller than the (unary) SQ complexity by a factor of at most 2^k. We show that for more general problems over distributions the picture is substantially richer. For every k, the complexity of distribution-independent PAC learning with k-wise queries can be exponentially larger than learning with (k+1)-wise queries. We then give two approaches for simulating a k-wise query using unary queries. The first approach exploits the structure of the problem that needs to be solved. It generalizes and strengthens (exponentially) the results of Blum et al.. It allows us to derive strong lower bounds for learning DNF formulas and stochastic constraint satisfaction problems that hold against algorithms using k-wise queries. The second approach exploits the k-party communication complexity of the k-wise query function.
Cite as

Vitaly Feldman and Badih Ghazi. On the Power of Learning from k-Wise Queries. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 41:1-41:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ITCS.2017.41,
  author =	{Feldman, Vitaly and Ghazi, Badih},
  title =	{{On the Power of Learning from k-Wise Queries}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{41:1--41:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.41},
  URN =		{urn:nbn:de:0030-drops-81801},
  doi =		{10.4230/LIPIcs.ITCS.2017.41},
  annote =	{Keywords: Statistical Queries, PAC Learning, Differential Privacy, Lower bounds, Communication Complexity}
}
  • Refine by Author
  • 3 Ghazi, Badih
  • 2 Kumar, Ravi
  • 2 Manurangsi, Pasin
  • 1 Abboud, Amir
  • 1 Bshouty, Nader H.
  • Show More...

  • Refine by Classification
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation
  • 2 Theory of computation → Communication complexity
  • 1 Mathematics of computing → Coding theory
  • 1 Mathematics of computing → Combinatoric problems
  • Show More...

  • Refine by Keyword
  • 2 Differential Privacy
  • 2 PAC Learning
  • 1 Aggregation
  • 1 Anonymous messages
  • 1 Communication Complexity
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 7 2024
  • 1 2017
  • 1 2020

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact