Volume
LIPIcs, Volume 145
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Event
APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USAEditors
Publication Details
- published at: 2019-09-17
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-125-2
- DBLP: db/conf/approx/approx2019
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume
Abstract
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume
Cite as
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@Proceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019,
title = {{LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019},
URN = {urn:nbn:de:0030-drops-113014},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019},
annote = {Keywords: Mathematics of computing; Theory of computation}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019.0,
author = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {0:i--0:xxii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.0},
URN = {urn:nbn:de:0030-drops-112155},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
APPROX
The Query Complexity of Mastermind with l_p Distances
Abstract
Consider a variant of the Mastermind game in which queries are l_p distances, rather than the usual Hamming distance. That is, a codemaker chooses a hidden vector y in {-k,-k+1,...,k-1,k}^n and answers to queries of the form ||y-x||_p where x in {-k,-k+1,...,k-1,k}^n. The goal is to minimize the number of queries made in order to correctly guess y.
In this work, we show an upper bound of O(min{n,(n log k)/(log n)}) queries for any real 1<=p<infty and O(n) queries for p=infty. To prove this result, we in fact develop a nonadaptive polynomial time algorithm that works for a natural class of separable distance measures, i.e., coordinate-wise sums of functions of the absolute value. We also show matching lower bounds up to constant factors, even for adaptive algorithms for the approximation version of the problem, in which the problem is to output y' such that ||y'-y||_p <= R for any R <= k^{1-epsilon}n^{1/p} for constant epsilon>0. Thus, essentially any approximation of this problem is as hard as finding the hidden vector exactly, up to constant factors. Finally, we show that for the noisy version of the problem, i.e., the setting when the codemaker answers queries with any q = (1 +/- epsilon)||y-x||_p, there is no query efficient algorithm.
Cite as
Manuel Fernández V, David P. Woodruff, and Taisuke Yasuda. The Query Complexity of Mastermind with l_p Distances. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 1:1-1:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fernandezv_et_al:LIPIcs.APPROX-RANDOM.2019.1,
author = {Fern\'{a}ndez V, Manuel and Woodruff, David P. and Yasuda, Taisuke},
title = {{The Query Complexity of Mastermind with l\underlinep Distances}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {1:1--1:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.1},
URN = {urn:nbn:de:0030-drops-112165},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.1},
annote = {Keywords: Mastermind, Query Complexity, l\underlinep Distance}
}
Document
APPROX
Tracking the l_2 Norm with Constant Update Time
Abstract
The l_2 tracking problem is the task of obtaining a streaming algorithm that, given access to a stream of items a_1,a_2,a_3,... from a universe [n], outputs at each time t an estimate to the l_2 norm of the frequency vector f^{(t)}in R^n (where f^{(t)}_i is the number of occurrences of item i in the stream up to time t). The previous work [Braverman-Chestnut-Ivkin-Nelson-Wang-Woodruff, PODS 2017] gave a streaming algorithm with (the optimal) space using O(epsilon^{-2}log(1/delta)) words and O(epsilon^{-2}log(1/delta)) update time to obtain an epsilon-accurate estimate with probability at least 1-delta. We give the first algorithm that achieves update time of O(log 1/delta) which is independent of the accuracy parameter epsilon, together with the nearly optimal space using O(epsilon^{-2}log(1/delta)) words. Our algorithm is obtained using the Count Sketch of [Charilkar-Chen-Farach-Colton, ICALP 2002].
Cite as
Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2,
author = {Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum},
title = {{Tracking the l\underline2 Norm with Constant Update Time}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {2:1--2:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.2},
URN = {urn:nbn:de:0030-drops-112175},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2},
annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch}
}
Document
APPROX
Submodular Optimization with Contention Resolution Extensions
Abstract
This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractional solution to the multi-linear extension and (2) rounding this solution to an integral solution via a contention resolution scheme. This line of research has improved results by either optimizing (1) or (2).
Diverging from previous work, this paper introduces a principled method called contention resolution extensions of submodular functions. A contention resolution extension combines the contention resolution scheme into a continuous extension of a discrete submodular function. The contention resolution extension can be defined from effectively any contention resolution scheme. In the case where there is a loss in both (1) and (2), by optimizing them together, the losses can be combined resulting in an overall improvement. This paper showcases the concept by demonstrating that for the problem of optimizing a non-monotone submodular subject to the elements forming an independent set in an interval graph, the algorithm gives a .188-approximation. This improves upon the best known 1/(2e)~eq .1839 approximation.
Cite as
Benjamin Moseley and Maxim Sviridenko. Submodular Optimization with Contention Resolution Extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{moseley_et_al:LIPIcs.APPROX-RANDOM.2019.3,
author = {Moseley, Benjamin and Sviridenko, Maxim},
title = {{Submodular Optimization with Contention Resolution Extensions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {3:1--3:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.3},
URN = {urn:nbn:de:0030-drops-112188},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.3},
annote = {Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling}
}
Document
APPROX
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
Abstract
In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we introduce the MinEMax model to study "build versus rent" problems. In our model different scenarios appear independently. Before knowing which scenarios appear, we may build rigid resources that cannot be changed for different scenarios. Once we know which scenarios appear, we are allowed to rent reconfigurable but expensive resources to use across scenarios. Although computing the objective in our model might seem to require enumerating exponentially-many possibilities, we show it is well estimated by a surrogate objective which is representable by a polynomial-size LP. In this surrogate objective we pay for each scenario only to the extent that it exceeds a certain threshold. Using this objective we design algorithms that approximately-optimally balance inflexible and reconfigurable resources for several NP-hard covering problems. For example, we study variants of minimum spanning and Steiner trees, minimum cuts, and facility location. Up to constants, our approximation guarantees match those of previously-studied algorithms for demand-robust and stochastic two-stage models. Lastly, we demonstrate that our problem is sufficiently general to smoothly interpolate between previous demand-robust and stochastic two-stage problems.
Cite as
David Ellis Hershkowitz, R. Ravi, and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{hershkowitz_et_al:LIPIcs.APPROX-RANDOM.2019.4,
author = {Hershkowitz, David Ellis and Ravi, R. and Singla, Sahil},
title = {{Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {4:1--4:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.4},
URN = {urn:nbn:de:0030-drops-112196},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.4},
annote = {Keywords: Approximation Algorithms, Optimization Under Uncertainty, Two-Stage Optimization, Expected Max}
}
Document
APPROX
Streaming Hardness of Unique Games
Abstract
We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by p, the alphabet size of the Unique Game, gives a trivial p-approximation that can be computed in O(log n) space. Meanwhile, with high probability, a sample of O~(n) constraints suffices to estimate the optimal value to (1+epsilon) accuracy. We prove that any single-pass streaming algorithm that achieves a (p-epsilon)-approximation requires Omega_epsilon(sqrt n) space. Our proof is via a reduction from lower bounds for a communication problem that is a p-ary variant of the Boolean Hidden Matching problem studied in the literature. Given the utility of Unique Games as a starting point for reduction to other optimization problems, our strong hardness for approximating Unique Games could lead to downstream hardness results for streaming approximability for other CSP-like problems.
Cite as
Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2019.5,
author = {Guruswami, Venkatesan and Tao, Runzhou},
title = {{Streaming Hardness of Unique Games}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {5:1--5:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.5},
URN = {urn:nbn:de:0030-drops-112209},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.5},
annote = {Keywords: Communication complexity, CSP, Fourier Analysis, Lower bounds, Streaming algorithms, Unique Games}
}
Document
APPROX
On Strong Diameter Padded Decompositions
Abstract
Given a weighted graph G=(V,E,w), a partition of V is Delta-bounded if the diameter of each cluster is bounded by Delta. A distribution over Delta-bounded partitions is a beta-padded decomposition if every ball of radius gamma Delta is contained in a single cluster with probability at least e^{-beta * gamma}. The weak diameter of a cluster C is measured w.r.t. distances in G, while the strong diameter is measured w.r.t. distances in the induced graph G[C]. The decomposition is weak/strong according to the diameter guarantee.
Formerly, it was proven that K_r free graphs admit weak decompositions with padding parameter O(r), while for strong decompositions only O(r^2) padding parameter was known. Furthermore, for the case of a graph G, for which the induced shortest path metric d_G has doubling dimension ddim, a weak O(ddim)-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known.
We construct strong O(r)-padded decompositions for K_r free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension ddim we construct a strong O(ddim)-padded decomposition, which is also tight. We use this decomposition to construct (O(ddim),O~(ddim))-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.
Cite as
Arnold Filtser. On Strong Diameter Padded Decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{filtser:LIPIcs.APPROX-RANDOM.2019.6,
author = {Filtser, Arnold},
title = {{On Strong Diameter Padded Decompositions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {6:1--6:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.6},
URN = {urn:nbn:de:0030-drops-112217},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.6},
annote = {Keywords: Padded decomposition, Strong Diameter, Sparse Cover, Doubling Dimension, Minor free graphs, Unique Games, Spanners, Distance Oracles}
}
Document
APPROX
Max-Min Greedy Matching
Abstract
A bipartite graph G(U,V;E) that admits a perfect matching is given. One player imposes a permutation pi over V, the other player imposes a permutation sigma over U. In the greedy matching algorithm, vertices of U arrive in order sigma and each vertex is matched to the highest (under pi) yet unmatched neighbor in V (or left unmatched, if all its neighbors are already matched). The obtained matching is maximal, thus matches at least a half of the vertices. The max-min greedy matching problem asks: suppose the first (max) player reveals pi, and the second (min) player responds with the worst possible sigma for pi, does there exist a permutation pi ensuring to match strictly more than a half of the vertices? Can such a permutation be computed in polynomial time?
The main result of this paper is an affirmative answer for these questions: we show that there exists a polytime algorithm to compute pi for which for every sigma at least rho > 0.51 fraction of the vertices of V are matched. We provide additional lower and upper bounds for special families of graphs, including regular and Hamiltonian graphs. Our solution solves an open problem regarding the welfare guarantees attainable by pricing in sequential markets with binary unit-demand valuations.
Cite as
Alon Eden, Uriel Feige, and Michal Feldman. Max-Min Greedy Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{eden_et_al:LIPIcs.APPROX-RANDOM.2019.7,
author = {Eden, Alon and Feige, Uriel and Feldman, Michal},
title = {{Max-Min Greedy Matching}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {7:1--7:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.7},
URN = {urn:nbn:de:0030-drops-112229},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.7},
annote = {Keywords: Online matching, Pricing mechanism, Markets}
}
Document
APPROX
Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues
Abstract
We present two graph quantities Psi(G,S) and Psi_2(G) which give constant factor estimates to the Dirichlet and Neumann eigenvalues, lambda(G,S) and lambda_2(G), respectively. Our techniques make use of a discrete Hardy-type inequality due to Muckenhoupt.
Cite as
Gary L. Miller, Noel J. Walkington, and Alex L. Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{miller_et_al:LIPIcs.APPROX-RANDOM.2019.8,
author = {Miller, Gary L. and Walkington, Noel J. and Wang, Alex L.},
title = {{Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {8:1--8:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.8},
URN = {urn:nbn:de:0030-drops-112236},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.8},
annote = {Keywords: Hardy, Muckenhoupt, Laplacian, eigenvalue, effective resistance}
}
Document
APPROX
Improved 3LIN Hardness via Linear Label Cover
Abstract
We prove that for every constant c and epsilon = (log n)^{-c}, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 - epsilon)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + epsilon)-fraction of clauses unless NP subseteq BPP. The previous best hardness using a polynomial time reduction achieves epsilon = (log log n)^{-c}, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3-LIN of Håstad [J. ACM, 48(4):798 - 859, 2001].
Our main idea is to prove a hardness result for Label Cover similar to Moshkovitz and Raz where each projection has a linear structure. This linear structure of Label Cover allows us to use Hadamard codes instead of long codes, making the reduction more efficient. For the hardness of Linear Label Cover, we follow the work of Dinur and Harsha [SIAM J. Comput., 42(6):2452 - 2486, 2013] that simplified the construction of Moshkovitz and Raz, and observe that running their reduction from a hardness of the problem LIN (of unbounded arity) instead of the more standard problem of solving quadratic equations ensures the linearity of the resultant Label Cover.
Cite as
Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari. Improved 3LIN Hardness via Linear Label Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{harsha_et_al:LIPIcs.APPROX-RANDOM.2019.9,
author = {Harsha, Prahladh and Khot, Subhash and Lee, Euiwoong and Thiruvenkatachari, Devanathan},
title = {{Improved 3LIN Hardness via Linear Label Cover}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.9},
URN = {urn:nbn:de:0030-drops-112245},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.9},
annote = {Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error}
}
Document
APPROX
Dynamic Pricing of Servers on Trees
Abstract
In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server.
This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.
Cite as
Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Dynamic Pricing of Servers on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2019.10,
author = {Cohen, Ilan Reuven and Eden, Alon and Fiat, Amos and Je\.{z}, {\L}ukasz},
title = {{Dynamic Pricing of Servers on Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {10:1--10:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.10},
URN = {urn:nbn:de:0030-drops-112252},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.10},
annote = {Keywords: Online algorithms, Online mechanisms, k-server problem, Online pricing}
}
Document
APPROX
Approximating the Norms of Graph Spanners
Abstract
The l_p-norm of the degree vector was recently introduced by [Chlamtáč, Dinitz, Robinson ICALP '19] as a new cost metric for graph spanners, as it interpolates between two traditional notions of cost (the sparsity l_1 and the max degree l_infty) and is well-motivated from applications. We study this from an approximation algorithms point of view, analyzing old algorithms and designing new algorithms for this new context, as well as providing hardness results. Our main results are for the l_2-norm and stretch 3, where we give a tight analysis of the greedy algorithm and a new algorithm specifically tailored to this setting which gives an improved approximation ratio.
Cite as
Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. Approximating the Norms of Graph Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2019.11,
author = {Chlamt\'{a}\v{c}, Eden and Dinitz, Michael and Robinson, Thomas},
title = {{Approximating the Norms of Graph Spanners}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {11:1--11:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.11},
URN = {urn:nbn:de:0030-drops-112261},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.11},
annote = {Keywords: Spanners, Approximations}
}
Document
APPROX
Conditional Hardness of Earth Mover Distance
Abstract
The Earth Mover Distance (EMD) between two sets of points A, B subseteq R^d with |A| = |B| is the minimum total Euclidean distance of any perfect matching between A and B. One of its generalizations is asymmetric EMD, which is the minimum total Euclidean distance of any matching of size |A| between sets of points A,B subseteq R^d with |A| <= |B|. The problems of computing EMD and asymmetric EMD are well-studied and have many applications in computer science, some of which also ask for the EMD-optimal matching itself. Unfortunately, all known algorithms require at least quadratic time to compute EMD exactly. Approximation algorithms with nearly linear time complexity in n are known (even for finding approximately optimal matchings), but suffer from exponential dependence on the dimension.
In this paper we show that significant improvements in exact and approximate algorithms for EMD would contradict conjectures in fine-grained complexity. In particular, we prove the following results:
- Under the Orthogonal Vectors Conjecture, there is some c>0 such that EMD in Omega(c^{log^* n}) dimensions cannot be computed in truly subquadratic time.
- Under the Hitting Set Conjecture, for every delta>0, no truly subquadratic time algorithm can find a (1 + 1/n^delta)-approximate EMD matching in omega(log n) dimensions.
- Under the Hitting Set Conjecture, for every eta = 1/omega(log n), no truly subquadratic time algorithm can find a (1 + eta)-approximate asymmetric EMD matching in omega(log n) dimensions.
Cite as
Dhruv Rohatgi. Conditional Hardness of Earth Mover Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{rohatgi:LIPIcs.APPROX-RANDOM.2019.12,
author = {Rohatgi, Dhruv},
title = {{Conditional Hardness of Earth Mover Distance}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {12:1--12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.12},
URN = {urn:nbn:de:0030-drops-112270},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.12},
annote = {Keywords: Earth Mover Distance, Hardness of Approximation, Fine-Grained Complexity}
}
Document
APPROX
Single-Elimination Brackets Fail to Approximate Copeland Winner
Abstract
Single-elimination (SE) brackets appear commonly in both sports tournaments and the voting theory literature. In certain tournament models, they have been shown to select the unambiguously-strongest competitor with optimum probability. By contrast, we reevaluate SE brackets through the lens of approximation, where the goal is to select a winner who would beat the most other competitors in a round robin (i.e., maximize the Copeland score), and find them lacking. Our primary result establishes the approximation ratio of a randomly-seeded SE bracket is 2^{- Theta(sqrt{log n})}; this is underwhelming considering a 1/2 ratio is achieved by choosing a winner uniformly at random. We also establish that a generalized version of the SE bracket performs nearly as poorly, with an approximation ratio of 2^{- Omega(sqrt[4]{log n})}, addressing a decade-old open question in the voting tree literature.
Cite as
Reyna Hulett. Single-Elimination Brackets Fail to Approximate Copeland Winner. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{hulett:LIPIcs.APPROX-RANDOM.2019.13,
author = {Hulett, Reyna},
title = {{Single-Elimination Brackets Fail to Approximate Copeland Winner}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {13:1--13:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.13},
URN = {urn:nbn:de:0030-drops-112283},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.13},
annote = {Keywords: Voting theory, mechanism design, query complexity, approximation}
}
Document
APPROX
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
Abstract
The problem of routing in graphs using node-disjoint paths has received a lot of attention and a polylogarithmic approximation algorithm with constant congestion is known for undirected graphs [Chuzhoy and Li 2016] and [Chekuri and Ene 2013]. However, the problem is hard to approximate within polynomial factors on directed graphs, for any constant congestion [Chuzhoy, Kim and Li 2016].
Recently, [Chekuri, Ene and Pilipczuk 2016] have obtained a polylogarithmic approximation with constant congestion on directed planar graphs, for the special case of symmetric demands. We extend their result by obtaining a polylogarithmic approximation with constant congestion on arbitrary directed minor-free graphs, for the case of symmetric demands.
Cite as
Timothy Carpenter, Ario Salmasi, and Anastasios Sidiropoulos. Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{carpenter_et_al:LIPIcs.APPROX-RANDOM.2019.14,
author = {Carpenter, Timothy and Salmasi, Ario and Sidiropoulos, Anastasios},
title = {{Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.14},
URN = {urn:nbn:de:0030-drops-112290},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.14},
annote = {Keywords: Routing, Node-disjoint, Symmetric demands, Minor-free graphs}
}
Document
APPROX
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Abstract
A k-uniform hypergraph is said to be r-rainbow colorable if there is an r-coloring of its vertices such that every hyperedge intersects all r color classes. Given as input such a hypergraph, finding a r-rainbow coloring of it is NP-hard for all k >= 3 and r >= 2. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When r=k (the maximum possible value), i.e., the hypergraph is k-partite, one can efficiently 2-rainbow color the hypergraph, i.e., 2-color its vertices so that there are no monochromatic edges. In this work we consider the next smaller value of r=k-1, and prove that in this case it is NP-hard to rainbow color the hypergraph with q := ceil[(k-2)/2] colors. In particular, for k <=6, it is NP-hard to 2-color (k-1)-rainbow colorable k-uniform hypergraphs.
Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set [r]^n. We prove that any such polymorphism f: [r]^n -> [q] must be C-fixing, i.e., there is a small subset S of C coordinates and a setting a in [q]^S such that fixing x_{|S} = a determines the value of f(x). The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the C-fixing characterization, our NP-hardness is obtained via a reduction from smooth Label Cover.
Cite as
Venkatesan Guruswami and Sai Sandeep. Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{guruswami_et_al:LIPIcs.APPROX-RANDOM.2019.15,
author = {Guruswami, Venkatesan and Sandeep, Sai},
title = {{Rainbow Coloring Hardness via Low Sensitivity Polymorphisms}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.15},
URN = {urn:nbn:de:0030-drops-112303},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.15},
annote = {Keywords: inapproximability, hardness of approximation, constraint satisfaction, hypergraph coloring, polymorphisms}
}
Document
APPROX
Syntactic Separation of Subset Satisfiability Problems
Abstract
Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1-epsilon) for some constant epsilon > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.
Cite as
Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai. Syntactic Separation of Subset Satisfiability Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{allender_et_al:LIPIcs.APPROX-RANDOM.2019.16,
author = {Allender, Eric and Farach-Colton, Mart{\'\i}n and Tsai, Meng-Tsung},
title = {{Syntactic Separation of Subset Satisfiability Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {16:1--16:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.16},
URN = {urn:nbn:de:0030-drops-112319},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.16},
annote = {Keywords: Syntactic Class, Exponential Time Hypothesis, APX, PTAS}
}
Document
APPROX
Malleable Scheduling Beyond Identical Machines
Abstract
In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S for j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/(e-1), unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/(e-1) for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+phi for unrelated speeds (phi is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds.
Cite as
Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos. Malleable Scheduling Beyond Identical Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fotakis_et_al:LIPIcs.APPROX-RANDOM.2019.17,
author = {Fotakis, Dimitris and Matuschke, Jannik and Papadigenopoulos, Orestis},
title = {{Malleable Scheduling Beyond Identical Machines}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {17:1--17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.17},
URN = {urn:nbn:de:0030-drops-112324},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.17},
annote = {Keywords: malleable, jobs, moldable, machines, unrelated, uniform, parallel, speeds, approximation, scheduling}
}
Document
APPROX
On the Cost of Essentially Fair Clusterings
Abstract
Clustering is a fundamental tool in data mining and machine learning. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters - especially if the data is already biased.
At NIPS 2017, Chierichetti et al. [Flavio Chierichetti et al., 2017] proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair k-center problem and a O(t)-approximation for the fair k-median problem, where t is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair k-center [Clemens Rösner and Melanie Schmidt, 2018].
We extend and improve the known results. Firstly, we give a 5-approximation for the fair k-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives k-center, k-supplier, k-median, k-means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed.
Cite as
Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the Cost of Essentially Fair Clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bercea_et_al:LIPIcs.APPROX-RANDOM.2019.18,
author = {Bercea, Ioana O. and Gro{\ss}, Martin and Khuller, Samir and Kumar, Aounon and R\"{o}sner, Clemens and Schmidt, Daniel R. and Schmidt, Melanie},
title = {{On the Cost of Essentially Fair Clusterings}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {18:1--18:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.18},
URN = {urn:nbn:de:0030-drops-112337},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.18},
annote = {Keywords: approximation, clustering, fairness, LP rounding}
}
Document
APPROX
The Maximum Exposure Problem
Abstract
Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points.
Cite as
Neeraj Kumar, Stavros Sintos, and Subhash Suri. The Maximum Exposure Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{kumar_et_al:LIPIcs.APPROX-RANDOM.2019.19,
author = {Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
title = {{The Maximum Exposure Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {19:1--19:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.19},
URN = {urn:nbn:de:0030-drops-112344},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.19},
annote = {Keywords: max-exposure, PTAS, densest k-subgraphs, geometric constraint removal, Network resilience}
}
Document
APPROX
Small Space Stream Summary for Matroid Center
Abstract
In the matroid center problem, which generalizes the k-center problem, we need to pick a set of centers that is an independent set of a matroid with rank r. We study this problem in streaming, where elements of the ground set arrive in the stream. We first show that any randomized one-pass streaming algorithm that computes a better than Delta-approximation for partition-matroid center must use Omega(r^2) bits of space, where Delta is the aspect ratio of the metric and can be arbitrarily large. This shows a quadratic separation between matroid center and k-center, for which the Doubling algorithm [Charikar et al., 1997] gives an 8-approximation using O(k)-space and one pass. To complement this, we give a one-pass algorithm for matroid center that stores at most O(r^2 log(1/epsilon)/epsilon) points (viz., stream summary) among which a (7+epsilon)-approximate solution exists, which can be found by brute force, or a (17+epsilon)-approximation can be found with an efficient algorithm. If we are allowed a second pass, we can compute a (3+epsilon)-approximation efficiently.
We also consider the problem of matroid center with z outliers and give a one-pass algorithm that outputs a set of O((r^2+rz)log(1/epsilon)/epsilon) points that contains a (15+epsilon)-approximate solution. Our techniques extend to knapsack center and knapsack center with z outliers in a straightforward way, and we get algorithms that use space linear in the size of a largest feasible set (as opposed to quadratic space for matroid center).
Cite as
Sagar Kale. Small Space Stream Summary for Matroid Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{kale:LIPIcs.APPROX-RANDOM.2019.20,
author = {Kale, Sagar},
title = {{Small Space Stream Summary for Matroid Center}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {20:1--20:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.20},
URN = {urn:nbn:de:0030-drops-112359},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.20},
annote = {Keywords: Streaming Algorithms, Matroids, Clustering}
}
Document
APPROX
Improved Bounds for Open Online Dial-a-Ride on the Line
Abstract
We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.
Cite as
Alexander Birx, Yann Disser, and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{birx_et_al:LIPIcs.APPROX-RANDOM.2019.21,
author = {Birx, Alexander and Disser, Yann and Schewior, Kevin},
title = {{Improved Bounds for Open Online Dial-a-Ride on the Line}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {21:1--21:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.21},
URN = {urn:nbn:de:0030-drops-112367},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.21},
annote = {Keywords: dial-a-ride on the line, elevator problem, online algorithms, competitive analysis, smartstart, competitive ratio}
}
Document
APPROX
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
Abstract
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set.
We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem.
The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].
Cite as
Susanne Albers, Arindam Khan, and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{albers_et_al:LIPIcs.APPROX-RANDOM.2019.22,
author = {Albers, Susanne and Khan, Arindam and Ladewig, Leon},
title = {{Improved Online Algorithms for Knapsack and GAP in the Random Order Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {22:1--22:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.22},
URN = {urn:nbn:de:0030-drops-112376},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.22},
annote = {Keywords: Online algorithms, knapsack problem, random order model}
}
Document
APPROX
Fast and Deterministic Approximations for k-Cut
Abstract
In an undirected graph, a k-cut is a set of edges whose removal breaks the graph into at least k connected components. The minimum weight k-cut can be computed in n^O(k) time, but when k is treated as part of the input, computing the minimum weight k-cut is NP-Hard [Goldschmidt and Hochbaum, 1994]. For poly(m,n,k)-time algorithms, the best possible approximation factor is essentially 2 under the small set expansion hypothesis [Manurangsi, 2017]. Saran and Vazirani [1995] showed that a (2 - 2/k)-approximately minimum weight k-cut can be computed via O(k) minimum cuts, which implies a O~(km) randomized running time via the nearly linear time randomized min-cut algorithm of Karger [2000]. Nagamochi and Kamidoi [2007] showed that a (2 - 2/k)-approximately minimum weight k-cut can be computed deterministically in O(mn + n^2 log n) time. These results prompt two basic questions. The first concerns the role of randomization. Is there a deterministic algorithm for 2-approximate k-cuts matching the randomized running time of O~(km)? The second question qualitatively compares minimum cut to 2-approximate minimum k-cut. Can 2-approximate k-cuts be computed as fast as the minimum cut - in O~(m) randomized time?
We give a deterministic approximation algorithm that computes (2 + eps)-minimum k-cuts in O(m log^3 n / eps^2) time, via a (1 + eps)-approximation for an LP relaxation of k-cut.
Cite as
Kent Quanrud. Fast and Deterministic Approximations for k-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{quanrud:LIPIcs.APPROX-RANDOM.2019.23,
author = {Quanrud, Kent},
title = {{Fast and Deterministic Approximations for k-Cut}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {23:1--23:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.23},
URN = {urn:nbn:de:0030-drops-112388},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.23},
annote = {Keywords: k-cut, multiplicative weight updates}
}
Document
APPROX
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Abstract
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within ~~0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within ~~0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (~~0.878 for Max-Cut, and ~~0.940 for Max-2-Sat).
The hardness for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem.
Cite as
Per Austrin and Aleksa Stanković. Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{austrin_et_al:LIPIcs.APPROX-RANDOM.2019.24,
author = {Austrin, Per and Stankovi\'{c}, Aleksa},
title = {{Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {24:1--24:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.24},
URN = {urn:nbn:de:0030-drops-112394},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.24},
annote = {Keywords: Constraint satisfaction problems, global cardinality constraints, semidefinite programming, inapproximability, Unique Games Conjecture, Max-Cut, Max-2-Sat}
}
Document
APPROX
Robust Appointment Scheduling with Heterogeneous Costs
Abstract
Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs.
For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.
Cite as
Andreas S. Schulz and Rajan Udwani. Robust Appointment Scheduling with Heterogeneous Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{schulz_et_al:LIPIcs.APPROX-RANDOM.2019.25,
author = {Schulz, Andreas S. and Udwani, Rajan},
title = {{Robust Appointment Scheduling with Heterogeneous Costs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.25},
URN = {urn:nbn:de:0030-drops-112407},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.25},
annote = {Keywords: Appointment scheduling, approximation algorithms, robust optimization}
}
Document
APPROX
Collapsing Superstring Conjecture
Abstract
In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits 2 11/23-approximation in polynomial time (Mucha, SODA'13). While this algorithm and its analysis are technically involved, the 30 years old Greedy Conjecture claims that the trivial and efficient Greedy Algorithm gives a 2-approximation for SCS.
We develop a graph-theoretic framework for studying approximation algorithms for SCS. The framework is reminiscent of the classical 2-approximation for Traveling Salesman: take two copies of an optimal solution, apply a trivial edge-collapsing procedure, and get an approximate solution. In this framework, we observe two surprising properties of SCS solutions, and we conjecture that they hold for all input instances. The first conjecture, that we call Collapsing Superstring conjecture, claims that there is an elementary way to transform any solution repeated twice into the same graph G. This conjecture would give an elementary 2-approximate algorithm for SCS. The second conjecture claims that not only the resulting graph G is the same for all solutions, but that G can be computed by an elementary greedy procedure called Greedy Hierarchical Algorithm.
While the second conjecture clearly implies the first one, perhaps surprisingly we prove their equivalence. We support these equivalent conjectures by giving a proof for the special case where all input strings have length at most 3 (which until recently had been the only case where the Greedy Conjecture was proven). We also tested our conjectures on millions of instances of SCS.
We prove that the standard Greedy Conjecture implies Greedy Hierarchical Conjecture, while the latter is sufficient for an efficient greedy 2-approximate approximation of SCS. Except for its (conjectured) good approximation ratio, the Greedy Hierarchical Algorithm provably finds a 3.5-approximation, and finds exact solutions for the special cases where we know polynomial time (not greedy) exact algorithms: (1) when the input strings form a spectrum of a string (2) when all input strings have length at most 2.
Cite as
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, and Maksim Nikolaev. Collapsing Superstring Conjecture. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.26,
author = {Golovnev, Alexander and Kulikov, Alexander S. and Logunov, Alexander and Mihajlin, Ivan and Nikolaev, Maksim},
title = {{Collapsing Superstring Conjecture}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {26:1--26:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.26},
URN = {urn:nbn:de:0030-drops-112411},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.26},
annote = {Keywords: superstring, shortest common superstring, approximation, greedy algorithms, greedy conjecture}
}
Document
APPROX
Improved Algorithms for Time Decay Streams
Abstract
In the time-decay model for data streams, elements of an underlying data set arrive sequentially with the recently arrived elements being more important. A common approach for handling large data sets is to maintain a coreset, a succinct summary of the processed data that allows approximate recovery of a predetermined query. We provide a general framework that takes any offline-coreset and gives a time-decay coreset for polynomial time decay functions.
We also consider the exponential time decay model for k-median clustering, where we provide a constant factor approximation algorithm that utilizes the online facility location algorithm. Our algorithm stores O(k log(h Delta)+h) points where h is the half-life of the decay function and Delta is the aspect ratio of the dataset. Our techniques extend to k-means clustering and M-estimators as well.
Cite as
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou. Improved Algorithms for Time Decay Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2019.27,
author = {Braverman, Vladimir and Lang, Harry and Ullah, Enayat and Zhou, Samson},
title = {{Improved Algorithms for Time Decay Streams}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.27},
URN = {urn:nbn:de:0030-drops-112429},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.27},
annote = {Keywords: Streaming algorithms, approximation algorithms, facility location and clustering}
}
Document
APPROX
Approximation Algorithms for Partially Colorable Graphs
Abstract
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For alpha <= 1 and k in Z^+, we say that a graph G=(V,E) is alpha-partially k-colorable, if there exists a subset S subset V of cardinality |S| >= alpha |V| such that the graph induced on S is k-colorable. Partial k-colorability is a more robust structural property of a graph than k-colorability. For graphs that arise in practice, partial k-colorability might be a better notion to use than k-colorability, since data arising in practice often contains various forms of noise.
We give a polynomial time algorithm that takes as input a (1 - epsilon)-partially 3-colorable graph G and a constant gamma in [epsilon, 1/10], and colors a (1 - epsilon/gamma) fraction of the vertices using O~(n^{0.25 + O(gamma^{1/2})}) colors. We also study natural semi-random families of instances of partially 3-colorable graphs and partially 2-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances.
Cite as
Suprovat Ghoshal, Anand Louis, and Rahul Raychaudhury. Approximation Algorithms for Partially Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{ghoshal_et_al:LIPIcs.APPROX-RANDOM.2019.28,
author = {Ghoshal, Suprovat and Louis, Anand and Raychaudhury, Rahul},
title = {{Approximation Algorithms for Partially Colorable Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {28:1--28:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.28},
URN = {urn:nbn:de:0030-drops-112438},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.28},
annote = {Keywords: Approximation Algorithms, Vertex Coloring, Semi-random Models}
}
Document
APPROX
Towards Optimal Moment Estimation in Streaming and Distributed Models
Abstract
One of the oldest problems in the data stream model is to approximate the p-th moment ||X||_p^p = sum_{i=1}^n X_i^p of an underlying non-negative vector X in R^n, which is presented as a sequence of poly(n) updates to its coordinates. Of particular interest is when p in (0,2]. Although a tight space bound of Theta(epsilon^-2 log n) bits is known for this problem when both positive and negative updates are allowed, surprisingly there is still a gap in the space complexity of this problem when all updates are positive. Specifically, the upper bound is O(epsilon^-2 log n) bits, while the lower bound is only Omega(epsilon^-2 + log n) bits. Recently, an upper bound of O~(epsilon^-2 + log n) bits was obtained under the assumption that the updates arrive in a random order.
We show that for p in (0, 1], the random order assumption is not needed. Namely, we give an upper bound for worst-case streams of O~(epsilon^-2 + log n) bits for estimating |X |_p^p. Our techniques also give new upper bounds for estimating the empirical entropy in a stream. On the other hand, we show that for p in (1,2], in the natural coordinator and blackboard distributed communication topologies, there is an O~(epsilon^-2) bit max-communication upper bound based on a randomized rounding scheme. Our protocols also give rise to protocols for heavy hitters and approximate matrix product. We generalize our results to arbitrary communication topologies G, obtaining an O~(epsilon^2 log d) max-communication upper bound, where d is the diameter of G. Interestingly, our upper bound rules out natural communication complexity-based approaches for proving an Omega(epsilon^-2 log n) bit lower bound for p in (1,2] for streaming algorithms. In particular, any such lower bound must come from a topology with large diameter.
Cite as
Rajesh Jayaram and David P. Woodruff. Towards Optimal Moment Estimation in Streaming and Distributed Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{jayaram_et_al:LIPIcs.APPROX-RANDOM.2019.29,
author = {Jayaram, Rajesh and Woodruff, David P.},
title = {{Towards Optimal Moment Estimation in Streaming and Distributed Models}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {29:1--29:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.29},
URN = {urn:nbn:de:0030-drops-112443},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.29},
annote = {Keywords: Streaming, Sketching, Message Passing, Moment Estimation}
}
Document
APPROX
The Complexity of Partial Function Extension for Coverage Functions
Abstract
Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of [m] and a value at each point, does there exist a coverage function defined on all subsets of [m] that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes.
We show that determining extendibility of a partial function to a coverage function is NP-complete, establishing in the process that there is a polynomial-sized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The two notions correspond roughly to multiplicative point-wise approximation and additive L_1 approximation. We show upper and lower bounds for both notions of approximation. In the second case we obtain nearly tight bounds.
Cite as
Umang Bhaskar and Gunjan Kumar. The Complexity of Partial Function Extension for Coverage Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bhaskar_et_al:LIPIcs.APPROX-RANDOM.2019.30,
author = {Bhaskar, Umang and Kumar, Gunjan},
title = {{The Complexity of Partial Function Extension for Coverage Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {30:1--30:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.30},
URN = {urn:nbn:de:0030-drops-112457},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.30},
annote = {Keywords: Coverage Functions, PAC Learning, Approximation Algorithm, Partial Function Extension}
}
Document
APPROX
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut
Abstract
Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.
Cite as
Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{gharibian_et_al:LIPIcs.APPROX-RANDOM.2019.31,
author = {Gharibian, Sevag and Parekh, Ojas},
title = {{Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {31:1--31:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.31},
URN = {urn:nbn:de:0030-drops-112463},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.31},
annote = {Keywords: Approximation algorithm, Max-Cut, local Hamiltonian, QMA-hard, Heisenberg model, product state}
}
Document
APPROX
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint
Abstract
Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint.
We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
Cite as
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2019.32,
author = {Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Mitchell, Joseph S. B. and Mustafa, Nabil H.},
title = {{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {32:1--32:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.32},
URN = {urn:nbn:de:0030-drops-112471},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.32},
annote = {Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint}
}
Document
APPROX
Robust Correlation Clustering
Abstract
In this paper, we introduce and study the Robust-Correlation-Clustering problem: given a graph G = (V,E) where every edge is either labeled + or - (denoting similar or dissimilar pairs of vertices), and a parameter m, the goal is to delete a set D of m vertices, and partition the remaining vertices V \ D into clusters to minimize the cost of the clustering, which is the sum of the number of + edges with end-points in different clusters and the number of - edges with end-points in the same cluster. This generalizes the classical Correlation-Clustering problem which is the special case when m = 0. Correlation clustering is useful when we have (only) qualitative information about the similarity or dissimilarity of pairs of points, and Robust-Correlation-Clustering equips this model with the capability to handle noise in datasets.
In this work, we present a constant-factor bi-criteria algorithm for Robust-Correlation-Clustering on complete graphs (where our solution is O(1)-approximate w.r.t the cost while however discarding O(1) m points as outliers), and also complement this by showing that no finite approximation is possible if we do not violate the outlier budget. Our algorithm is very simple in that it first does a simple LP-based pre-processing to delete O(m) vertices, and subsequently runs a particular Correlation-Clustering algorithm ACNAlg [Ailon et al., 2005] on the residual instance. We then consider general graphs, and show (O(log n), O(log^2 n)) bi-criteria algorithms while also showing a hardness of alpha_MC on both the cost and the outlier violation, where alpha_MC is the lower bound for the Minimum-Multicut problem.
Cite as
Devvrit, Ravishankar Krishnaswamy, and Nived Rajaraman. Robust Correlation Clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{devvrit_et_al:LIPIcs.APPROX-RANDOM.2019.33,
author = {Devvrit and Krishnaswamy, Ravishankar and Rajaraman, Nived},
title = {{Robust Correlation Clustering}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {33:1--33:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.33},
URN = {urn:nbn:de:0030-drops-112483},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.33},
annote = {Keywords: Correlation Clustering, Outlier Detection, Clustering, Approximation Algorithms}
}
Document
RANDOM
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
Abstract
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every Delta-regular bipartite graph if Delta >= 53. In the weighted case, for all sufficiently large integers Delta and weight parameters lambda = Omega~ (1/(Delta)), we also obtain an FPTAS on almost every Delta-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all q >= 3 and sufficiently large integers Delta=Delta(q), there is an FPTAS to count the number of q-colorings on almost every Delta-regular bipartite graph.
Cite as
Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting Independent Sets and Colorings on Random Regular Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{liao_et_al:LIPIcs.APPROX-RANDOM.2019.34,
author = {Liao, Chao and Lin, Jiabao and Lu, Pinyan and Mao, Zhenyu},
title = {{Counting Independent Sets and Colorings on Random Regular Bipartite Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {34:1--34:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.34},
URN = {urn:nbn:de:0030-drops-112498},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.34},
annote = {Keywords: Approximate counting, Polymer model, Hardcore model, Coloring, Random bipartite graphs}
}
Document
RANDOM
The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions
Abstract
The Maximal points in a set S are those that are not dominated by any other point in S. Such points arise in multiple application settings and are called by a variety of different names, e.g., maxima, Pareto optimums, skylines. Their ubiquity has inspired a large literature on the expected number of maxima in a set S of n points chosen IID from some distribution. Most such results assume that the underlying distribution is uniform over some spatial region and strongly use this uniformity in their analysis.
This research was initially motivated by the question of how this expected number changes if the input distribution is perturbed by random noise. More specifically, let B_p denote the uniform distribution from the 2-dimensional unit ball in the metric L_p. Let delta B_q denote the 2-dimensional L_q-ball, of radius delta and B_p + delta B_q be the convolution of the two distributions, i.e., a point v in B_p is reported with an error chosen from delta B_q. The question is how the expected number of maxima change as a function of delta. Although the original motivation is for small delta, the problem is well defined for any delta and our analysis treats the general case.
More specifically, we study, as a function of n,delta, the expected number of maximal points when the n points in S are chosen IID from distributions of the type B_p + delta B_q where p,q in {1,2,infty} for delta > 0 and also of the type B_infty + delta B_q where q in [1,infty) for delta > 0.
For fixed p,q we show that this function changes "smoothly" as a function of delta but that this smooth behavior sometimes transitions unexpectedly between different growth behaviors.
Cite as
Josep Diaz and Mordecai Golin. The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{diaz_et_al:LIPIcs.APPROX-RANDOM.2019.35,
author = {Diaz, Josep and Golin, Mordecai},
title = {{The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.35},
URN = {urn:nbn:de:0030-drops-112501},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.35},
annote = {Keywords: maximal points, probabilistic geometry, perturbations, Minkowski sum}
}
Document
RANDOM
On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
Abstract
Let Omega_q=Omega_q(H) denote the set of proper [q]-colorings of the hypergraph H. Let Gamma_q be the graph with vertex set Omega_q where two vertices are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_{n,m;k}, k >= 2, the random k-uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Gamma_q is connected if d is sufficiently large and q >~ (d/log d)^{1/(k-1)}. This is optimal to the first order in d. Furthermore, with a few more colors, we find that the diameter of Gamma_q is O(n) w.h.p, where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber Dynamics Markov Chain on Omega_q is ergodic w.h.p.
Cite as
Michael Anastos and Alan Frieze. On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 36:1-36:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{anastos_et_al:LIPIcs.APPROX-RANDOM.2019.36,
author = {Anastos, Michael and Frieze, Alan},
title = {{On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {36:1--36:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.36},
URN = {urn:nbn:de:0030-drops-112513},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.36},
annote = {Keywords: Random Graphs, Colorings, Ergodicity}
}
Document
RANDOM
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases
Abstract
The six-vertex model in statistical physics is a weighted generalization of the ice model on Z^2 (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model represents its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.
Cite as
Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{fahrbach_et_al:LIPIcs.APPROX-RANDOM.2019.37,
author = {Fahrbach, Matthew and Randall, Dana},
title = {{Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {37:1--37:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.37},
URN = {urn:nbn:de:0030-drops-112523},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.37},
annote = {Keywords: Correlated random walk, Markov chain Monte Carlo, Six-vertex model}
}
Document
RANDOM
Lifted Multiplicity Codes and the Disjoint Repair Group Property
Abstract
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the t-disjoint-repair-group property than previously known constructions. More precisely, we show that, for t <=sqrt{N}, lifted multiplicity codes with length N and redundancy O(t^{0.585} sqrt{N}) have the property that any symbol of a codeword can be reconstructed in t different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant t < sqrt{N}. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.
Cite as
Ray Li and Mary Wootters. Lifted Multiplicity Codes and the Disjoint Repair Group Property. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.38,
author = {Li, Ray and Wootters, Mary},
title = {{Lifted Multiplicity Codes and the Disjoint Repair Group Property}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {38:1--38:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.38},
URN = {urn:nbn:de:0030-drops-112539},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.38},
annote = {Keywords: Lifted codes, Multiplicity codes, Disjoint repair group property, PIR code, Coding theory}
}
Document
RANDOM
Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
Abstract
We study the r-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the r-complex contagion model, each uninfected vertex in the network becomes infected if it has at least r infected neighbors.
In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability omega (n^{-(1+1/r)}), under certain mild assumptions, we prove that the optimal seeding strategy is to put all the seeds in a single community. This matches the intuition that in a nonsubmodular cascade model placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model and the linear threshold model) in which nearby seeds tend to erode each others' effects.
Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in omega (n^{-(1+1/r)}) or in o (n^{-2}).
Cite as
Grant Schoenebeck, Biaoshuai Tao, and Fang-Yi Yu. Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{schoenebeck_et_al:LIPIcs.APPROX-RANDOM.2019.39,
author = {Schoenebeck, Grant and Tao, Biaoshuai and Yu, Fang-Yi},
title = {{Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {39:1--39:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.39},
URN = {urn:nbn:de:0030-drops-112542},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.39},
annote = {Keywords: Nonsubmodular Influence Maximization, Bootstrap Percolation, Stochastic Blockmodel}
}
Document
RANDOM
Direct Sum Testing: The General Case
Abstract
A function f:[n_1] x ... x[n_d]->F_2 is a direct sum if it is of the form f (a_1,...,a_d) = f_1(a_1) oplus ... oplus f_d (a_d), for some d functions f_i:[n_i]->F_2 for all i=1,..., d, and where n_1,...,n_d in N. We present a 4-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on the direct product test constructed by Dinur & Steurer (2014).
We also present a different test, which queries the function (d+1) times, but is easier to analyze.
In multiplicative +/- 1 notation, this reads as follows. A d-dimensional tensor with +/- 1 entries is called a tensor product if it is a tensor product of d vectors with +/- 1 entries, or equivalently, if it is of rank 1. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products.
Cite as
Irit Dinur and Konstantin Golubev. Direct Sum Testing: The General Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 40:1-40:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{dinur_et_al:LIPIcs.APPROX-RANDOM.2019.40,
author = {Dinur, Irit and Golubev, Konstantin},
title = {{Direct Sum Testing: The General Case}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {40:1--40:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.40},
URN = {urn:nbn:de:0030-drops-112554},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.40},
annote = {Keywords: property testing, direct sum, tensor product}
}
Document
RANDOM
Fast Algorithms at Low Temperatures via Markov Chains
Abstract
For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok’s polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.
Cite as
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast Algorithms at Low Temperatures via Markov Chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2019.41,
author = {Chen, Zongchen and Galanis, Andreas and Goldberg, Leslie Ann and Perkins, Will and Stewart, James and Vigoda, Eric},
title = {{Fast Algorithms at Low Temperatures via Markov Chains}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.41},
URN = {urn:nbn:de:0030-drops-112560},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.41},
annote = {Keywords: Markov chains, approximate counting, Potts model, hard-core model, expander graphs}
}
Document
RANDOM
Deterministic Approximation of Random Walks in Small Space
Abstract
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph G, a positive integer r, and a set S of vertices, approximates the conductance of S in the r-step random walk on G to within a factor of 1+epsilon, where epsilon>0 is an arbitrarily small constant. More generally, our algorithm computes an epsilon-spectral approximation to the normalized Laplacian of the r-step walk.
Our algorithm combines the derandomized square graph operation [Eyal Rozenman and Salil Vadhan, 2005], which we recently used for solving Laplacian systems in nearly logarithmic space [Murtagh et al., 2017], with ideas from [Cheng et al., 2015], which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even r (while ours works for all r). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd r. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
Cite as
Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. Deterministic Approximation of Random Walks in Small Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 42:1-42:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{murtagh_et_al:LIPIcs.APPROX-RANDOM.2019.42,
author = {Murtagh, Jack and Reingold, Omer and Sidford, Aaron and Vadhan, Salil},
title = {{Deterministic Approximation of Random Walks in Small Space}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {42:1--42:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.42},
URN = {urn:nbn:de:0030-drops-112577},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.42},
annote = {Keywords: random walks, space complexity, derandomization, spectral approximation, expander graphs}
}
Document
RANDOM
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions
Abstract
In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error epsilon for n-bit sources having min-entropy {polylog}(n/epsilon). Unfortunately, the construction’s running-time is {poly}(n/epsilon), which means that with polynomial-time constructions, only polynomially-small errors are possible. Our main result is a {poly}(n,log(1/epsilon))-time computable two-source condenser. For any k >= {polylog}(n/epsilon), our condenser transforms two independent (n,k)-sources to a distribution over m = k-O(log(1/epsilon)) bits that is epsilon-close to having min-entropy m - o(log(1/epsilon)). Hence, achieving entropy gap of o(log(1/epsilon)).
The bottleneck for obtaining low error in recent constructions of two-source extractors lies in the use of resilient functions. Informally, this is a function that receives input bits from r players with the property that the function’s output has small bias even if a bounded number of corrupted players feed adversarial inputs after seeing the inputs of the other players. The drawback of using resilient functions is that the error cannot be smaller than ln r/r. This, in return, forces the running time of the construction to be polynomial in 1/epsilon.
A key component in our construction is a variant of resilient functions which we call entropy-resilient functions. This variant can be seen as playing the above game for several rounds, each round outputting one bit. The goal of the corrupted players is to reduce, with as high probability as they can, the min-entropy accumulated throughout the rounds. We show that while the bias decreases only polynomially with the number of players in a one-round game, their success probability decreases exponentially in the entropy gap they are attempting to incur in a repeated game.
Cite as
Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43,
author = {Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon},
title = {{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {43:1--43:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.43},
URN = {urn:nbn:de:0030-drops-112587},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.43},
annote = {Keywords: Condensers, Extractors, Resilient functions, Explicit constructions}
}
Document
RANDOM
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions
Abstract
A number of recent works have considered the trace reconstruction problem, in which an unknown source string x in {0,1}^n is transmitted through a probabilistic channel which may randomly delete coordinates or insert random bits, resulting in a trace of x. The goal is to reconstruct the original string x from independent traces of x. While the asymptotically best algorithms known for worst-case strings use exp(O(n^{1/3})) traces [De et al., 2017; Fedor Nazarov and Yuval Peres, 2017], several highly efficient algorithms are known [Yuval Peres and Alex Zhai, 2017; Nina Holden et al., 2018] for the average-case version of the problem, in which the source string x is chosen uniformly at random from {0,1}^n. In this paper we consider a generalization of the above-described average-case trace reconstruction problem, which we call average-case population recovery in the presence of insertions and deletions. In this problem, rather than a single unknown source string there is an unknown distribution over s unknown source strings x^1,...,x^s in {0,1}^n, and each sample given to the algorithm is independently generated by drawing some x^i from this distribution and returning an independent trace of x^i. Building on the results of [Yuval Peres and Alex Zhai, 2017] and [Nina Holden et al., 2018], we give an efficient algorithm for the average-case population recovery problem in the presence of insertions and deletions. For any support size 1 <= s <= exp(Theta(n^{1/3})), for a 1-o(1) fraction of all s-element support sets {x^1,...,x^s} subset {0,1}^n, for every distribution D supported on {x^1,...,x^s}, our algorithm can efficiently recover D up to total variation distance at most epsilon with high probability, given access to independent traces of independent draws from D. The running time of our algorithm is poly(n,s,1/epsilon) and its sample complexity is poly (s,1/epsilon,exp(log^{1/3} n)). This polynomial dependence on the support size s is in sharp contrast with the worst-case version of the problem (when x^1,...,x^s may be any strings in {0,1}^n), in which the sample complexity of the most efficient known algorithm [Frank Ban et al., 2019] is doubly exponential in s.
Cite as
Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{ban_et_al:LIPIcs.APPROX-RANDOM.2019.44,
author = {Ban, Frank and Chen, Xi and Servedio, Rocco A. and Sinha, Sandip},
title = {{Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {44:1--44:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.44},
URN = {urn:nbn:de:0030-drops-112592},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.44},
annote = {Keywords: population recovery, deletion channel, trace reconstruction}
}
Document
RANDOM
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
Abstract
We give the best known pseudorandom generators for two touchstone classes in unconditional derandomization: small-depth circuits and sparse F_2 polynomials. Our main results are an epsilon-PRG for the class of size-M depth-d AC^0 circuits with seed length log(M)^{d+O(1)}* log(1/epsilon), and an epsilon-PRG for the class of S-sparse F_2 polynomials with seed length 2^{O(sqrt{log S})}* log(1/epsilon). These results bring the state of the art for unconditional derandomization of these classes into sharp alignment with the state of the art for computational hardness for all parameter settings: improving on the seed lengths of either PRG would require breakthrough progress on longstanding and notorious circuit lower bounds.
The key enabling ingredient in our approach is a new pseudorandom multi-switching lemma. We derandomize recently-developed multi-switching lemmas, which are powerful generalizations of Håstad’s switching lemma that deal with families of depth-two circuits. Our pseudorandom multi-switching lemma - a randomness-efficient algorithm for sampling restrictions that simultaneously simplify all circuits in a family - achieves the parameters obtained by the (full randomness) multi-switching lemmas of Impagliazzo, Matthews, and Paturi [Impagliazzo et al., 2012] and Håstad [Johan Håstad, 2014]. This optimality of our derandomization translates into the optimality (given current circuit lower bounds) of our PRGs for AC^0 and sparse F_2 polynomials.
Cite as
Rocco A. Servedio and Li-Yang Tan. Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{servedio_et_al:LIPIcs.APPROX-RANDOM.2019.45,
author = {Servedio, Rocco A. and Tan, Li-Yang},
title = {{Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {45:1--45:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.45},
URN = {urn:nbn:de:0030-drops-112605},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.45},
annote = {Keywords: pseudorandom generators, switching lemmas, circuit complexity, unconditional derandomization}
}
Document
RANDOM
Unconstraining Graph-Constrained Group Testing
Abstract
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graph-constrained group testing. Graph-constrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology.
The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graph-constrained group testing is near-optimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs.
Finally, we provide empirical results which suggest that our connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.
Cite as
Bruce Spang and Mary Wootters. Unconstraining Graph-Constrained Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{spang_et_al:LIPIcs.APPROX-RANDOM.2019.46,
author = {Spang, Bruce and Wootters, Mary},
title = {{Unconstraining Graph-Constrained Group Testing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {46:1--46:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.46},
URN = {urn:nbn:de:0030-drops-112615},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.46},
annote = {Keywords: Group testing, network tomography, random graphs}
}
Document
RANDOM
Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of l_1
Abstract
Randomized dimensionality reduction has been recognized as one of the fundamental techniques in handling high-dimensional data. Starting with the celebrated Johnson-Lindenstrauss Lemma, such reductions have been studied in depth for the Euclidean (l_2) metric, but much less for the Manhattan (l_1) metric. Our primary motivation is the approximate nearest neighbor problem in l_1. We exploit its reduction to the decision-with-witness version, called approximate near neighbor, which incurs a roughly logarithmic overhead. In 2007, Indyk and Naor, in the context of approximate nearest neighbors, introduced the notion of nearest neighbor-preserving embeddings. These are randomized embeddings between two metric spaces with guaranteed bounded distortion only for the distances between a query point and a point set. Such embeddings are known to exist for both l_2 and l_1 metrics, as well as for doubling subsets of l_2. The case that remained open were doubling subsets of l_1. In this paper, we propose a dimension reduction by means of a near neighbor-preserving embedding for doubling subsets of l_1. Our approach is to represent the pointset with a carefully chosen covering set, then randomly project the latter. We study two types of covering sets: c-approximate r-nets and randomly shifted grids, and we discuss the tradeoff between them in terms of preprocessing time and target dimension. We employ Cauchy variables: certain concentration bounds derived should be of independent interest.
Cite as
Ioannis Z. Emiris, Vasilis Margonis, and Ioannis Psarros. Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of l_1. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{emiris_et_al:LIPIcs.APPROX-RANDOM.2019.47,
author = {Emiris, Ioannis Z. and Margonis, Vasilis and Psarros, Ioannis},
title = {{Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of l\underline1}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {47:1--47:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.47},
URN = {urn:nbn:de:0030-drops-112628},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.47},
annote = {Keywords: Approximate nearest neighbor, Manhattan metric, randomized embedding}
}
Document
RANDOM
Improved Strong Spatial Mixing for Colorings on Trees
Abstract
Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is the algorithm of Weitz (2006) for the hard-core model on weighted independent sets. We study SSM for the q-colorings problem on the infinite (d+1)-regular tree. Weak spatial mixing (WSM) captures whether the influence of the leaves on the root vanishes as the height of the tree grows. Jonasson (2002) established WSM when q>d+1. In contrast, in SSM, we first fix a coloring on a subset of internal vertices, and we again ask if the influence of the leaves on the root is vanishing. It was known that SSM holds on the (d+1)-regular tree when q>alpha d where alpha ~~ 1.763... is a constant that has arisen in a variety of results concerning random colorings. Here we improve on this bound by showing SSM for q>1.59d. Our proof establishes an L^2 contraction for the BP operator. For the contraction we bound the norm of the BP Jacobian by exploiting combinatorial properties of the coloring of the tree.
Cite as
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{efthymiou_et_al:LIPIcs.APPROX-RANDOM.2019.48,
author = {Efthymiou, Charilaos and Galanis, Andreas and Hayes, Thomas P. and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric},
title = {{Improved Strong Spatial Mixing for Colorings on Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.48},
URN = {urn:nbn:de:0030-drops-112630},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.48},
annote = {Keywords: colorings, regular tree, spatial mixing, phase transitions}
}
Document
RANDOM
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Abstract
Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge e exists, we need to perform an expensive test, in which case the edge e appears independently with a known probability p_e. Given a budget on the total cost of the tests, our goal is to find a testing strategy that maximizes the expected maximum matching size.
The above application is an example of the stochastic probing problem. In general the optimal stochastic probing strategy is difficult to find because it is adaptive - decides on the next edge to probe based on the outcomes of the probed edges. An alternate approach is to show the adaptivity gap is small, i.e., the best non-adaptive strategy always has a value close to the best adaptive strategy. This allows us to focus on designing non-adaptive strategies that are much simpler. Previous works, however, have focused on Bernoulli random variables that can only capture whether an edge appears or not. In this work we introduce a multi-value stochastic probing problem, which can also model situations where the weight of an edge has a probability distribution over multiple values.
Our main technical contribution is to obtain (near) optimal bounds for the (worst-case) adaptivity gaps for multi-value stochastic probing over prefix-closed constraints. For a monotone submodular function, we show the adaptivity gap is at most 2 and provide a matching lower bound. For a weighted rank function of a k-extendible system (a generalization of intersection of k matroids), we show the adaptivity gap is between O(k log k) and k. None of these results were known even in the Bernoulli case where both our upper and lower bounds also apply, thereby resolving an open question of Gupta et al. [Gupta et al., 2017].
Cite as
Domagoj Bradac, Sahil Singla, and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bradac_et_al:LIPIcs.APPROX-RANDOM.2019.49,
author = {Bradac, Domagoj and Singla, Sahil and Zuzic, Goran},
title = {{(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {49:1--49:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.49},
URN = {urn:nbn:de:0030-drops-112641},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.49},
annote = {Keywords: stochastic programming, adaptivity gaps, stochastic multi-value probing, submodular functions, k-extendible systems, adaptive strategy, matroid intersection}
}
Document
RANDOM
Testing Odd Direct Sums Using High Dimensional Expanders
Abstract
In this work, using methods from high dimensional expansion, we show that the property of k-direct-sum is testable for odd values of k . Previous work of [Kaufman and Lubotzky, 2014] could inherently deal only with the case that k is even, using a reduction to linearity testing. Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result.
The classical k-direct-sum problem applies to the complete complex; Namely it considers a function defined over all k-subsets of some n sized universe. Our result here applies to any collection of k-subsets of an n-universe, assuming this collection of subsets forms a high dimensional expander.
Cite as
Roy Gotlib and Tali Kaufman. Testing Odd Direct Sums Using High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{gotlib_et_al:LIPIcs.APPROX-RANDOM.2019.50,
author = {Gotlib, Roy and Kaufman, Tali},
title = {{Testing Odd Direct Sums Using High Dimensional Expanders}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {50:1--50:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.50},
URN = {urn:nbn:de:0030-drops-112651},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.50},
annote = {Keywords: High Dimensional Expanders, Property Testing, Direct Sum}
}
Document
RANDOM
A Lower Bound for Sampling Disjoint Sets
Abstract
Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set x subseteq[n] and Bob ends up with a set y subseteq[n], such that (x,y) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant beta<1, this requires Omega(n) communication even to get within statistical distance 1-beta^n of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that Omega(sqrt{n}) communication is required to get within some constant statistical distance epsilon>0 of the uniform distribution over all pairs of disjoint sets of size sqrt{n}.
Cite as
Mika Göös and Thomas Watson. A Lower Bound for Sampling Disjoint Sets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2019.51,
author = {G\"{o}\"{o}s, Mika and Watson, Thomas},
title = {{A Lower Bound for Sampling Disjoint Sets}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {51:1--51:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.51},
URN = {urn:nbn:de:0030-drops-112666},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.51},
annote = {Keywords: Communication complexity, set disjointness, sampling}
}
Document
RANDOM
Approximating the Noise Sensitivity of a Monotone Boolean Function
Abstract
The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure.
The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]).
Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n.
We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.
Cite as
Ronitt Rubinfeld and Arsen Vasilyan. Approximating the Noise Sensitivity of a Monotone Boolean Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{rubinfeld_et_al:LIPIcs.APPROX-RANDOM.2019.52,
author = {Rubinfeld, Ronitt and Vasilyan, Arsen},
title = {{Approximating the Noise Sensitivity of a Monotone Boolean Function}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {52:1--52:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.52},
URN = {urn:nbn:de:0030-drops-112672},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.52},
annote = {Keywords: Monotone Boolean functions, noise sensitivity, influence}
}
Document
RANDOM
Connectivity of Random Annulus Graphs and the Geometric Block Model
Abstract
Random geometric graph (Gilbert, 1961) is a basic model of random graphs for spatial networks proposed shortly after the introduction of the Erdős-Rényi random graphs. The geometric block model (GBM) is a probabilistic model for community detection defined over random geometric graphs (RGG) similar in spirit to the popular stochastic block model which is defined over Erdős-Rényi random graphs. The GBM naturally inherits many desirable properties of RGGs such as transitivity ("friends having common friends') and has been shown to model many real-world networks better than the stochastic block model. Analyzing the properties of a GBM requires new tools and perspectives to handle correlation in edge formation. In this paper, we study the necessary and sufficient conditions for community recovery over GBM in the connectivity regime. We provide efficient algorithms that recover the communities exactly with high probability and match the lower bound within a small constant factor. This requires us to prove new connectivity results for vertex-random graphs or random annulus graphs which are natural generalizations of random geometric graphs.
A vertex-random graph is a model of random graphs where the randomness lies in the vertices as opposed to an Erdős-Rényi random graph where the randomness lies in the edges. A vertex-random graph G(n, [r_1, r_2]), 0 <=r_1 <r_2 <=1 with n vertices is defined by assigning a real number in [0,1] randomly and uniformly to each vertices and adding an edge between two vertices if the "distance" between the corresponding two random numbers is between r_1 and r_2. For the special case of r_1=0, this corresponds to random geometric graph in one dimension. We can extend this model naturally to higher dimensions; these higher dimensional counterparts are referred to as random annulus graphs. Random annulus graphs appear naturally whenever the well-known Goldilocks principle ("not too close, not too far') holds in a network. In this paper, we study the connectivity properties of such graphs, providing both necessary and sufficient conditions. We show a surprising long edge phenomena for vertex-random graphs: the minimum gap for connectivity between r_1 and r_2 is significantly less when r_1 >0 vs when r_1=0 (RGG). We then extend the connectivity results to high dimensions. These results play a crucial role in analyzing the GBM.
Cite as
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connectivity of Random Annulus Graphs and the Geometric Block Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{galhotra_et_al:LIPIcs.APPROX-RANDOM.2019.53,
author = {Galhotra, Sainyam and Mazumdar, Arya and Pal, Soumyabrata and Saha, Barna},
title = {{Connectivity of Random Annulus Graphs and the Geometric Block Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {53:1--53:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.53},
URN = {urn:nbn:de:0030-drops-112682},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.53},
annote = {Keywords: random graphs, geometric graphs, community detection, block model}
}
Document
RANDOM
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Abstract
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.
Cite as
Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2019.54,
author = {Cannon, Sarah and Daymude, Joshua J. and G\"{o}kmen, Cem and Randall, Dana and Richa, Andr\'{e}a W.},
title = {{A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {54:1--54:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.54},
URN = {urn:nbn:de:0030-drops-112696},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.54},
annote = {Keywords: Markov chains, Programmable matter, Cluster expansion}
}
Document
RANDOM
The Large-Error Approximate Degree of AC^0
Abstract
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016).
Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3.
Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.
Cite as
Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2019.55,
author = {Bun, Mark and Thaler, Justin},
title = {{The Large-Error Approximate Degree of AC^0}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {55:1--55:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.55},
URN = {urn:nbn:de:0030-drops-112709},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.55},
annote = {Keywords: approximate degree, discrepancy, margin complexity, polynomial approximations, secret sharing, threshold circuits}
}
Document
RANDOM
String Matching: Communication, Circuits, and Learning
Abstract
String matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings.
- Communication complexity. For small k, we provide near-optimal upper and lower bounds on the communication complexity of string matching. For large k, our bounds leave open an exponential gap; we exhibit some evidence for the existence of a better protocol.
- Circuit complexity. We present several upper and lower bounds on the size of circuits with threshold and DeMorgan gates solving the string matching problem. Similarly to the above, our bounds are near-optimal for small k.
- Learning. We consider the problem of learning a hidden pattern of length at most k relative to the classifier that assigns 1 to every string that contains the pattern. We prove optimal bounds on the VC dimension and sample complexity of this problem.
Cite as
Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar. String Matching: Communication, Circuits, and Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.56,
author = {Golovnev, Alexander and G\"{o}\"{o}s, Mika and Reichman, Daniel and Shinkar, Igor},
title = {{String Matching: Communication, Circuits, and Learning}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {56:1--56:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.56},
URN = {urn:nbn:de:0030-drops-112717},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.56},
annote = {Keywords: string matching, communication complexity, circuit complexity, PAC learning}
}
Document
RANDOM
Efficient Black-Box Identity Testing for Free Group Algebras
Abstract
Hrubeš and Wigderson [Pavel Hrubeš and Avi Wigderson, 2014] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. For noncommutative formulas with inverses the problem can be solved in deterministic polynomial time in the white-box model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the black-box model [Harm Derksen and Visu Makam, 2017], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions, in general, remains open for noncommutative circuits with inverses.
We solve the problem for a natural special case. We consider expressions in the free group algebra F(X,X^{-1}) where X={x_1, x_2, ..., x_n}. Our main results are the following.
1) Given a degree d expression f in F(X,X^{-1}) as a black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an Amitsur-Levitzki type theorem [A. S. Amitsur and J. Levitzki, 1950] for F(X, X^{-1}). This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression.
2) Given an expression f in F(X,X^{-1}) of degree D and sparsity s, as black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomial-time algorithm when D and s are exponential in n.
Cite as
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Efficient Black-Box Identity Testing for Free Group Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{arvind_et_al:LIPIcs.APPROX-RANDOM.2019.57,
author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
title = {{Efficient Black-Box Identity Testing for Free Group Algebras}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {57:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.57},
URN = {urn:nbn:de:0030-drops-112723},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.57},
annote = {Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms}
}
Document
RANDOM
The Maximum Label Propagation Algorithm on Sparse Random Graphs
Abstract
In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.
Cite as
Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger. The Maximum Label Propagation Algorithm on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{knierim_et_al:LIPIcs.APPROX-RANDOM.2019.58,
author = {Knierim, Charlotte and Lengler, Johannes and Pfister, Pascal and Schaller, Ulysse and Steger, Angelika},
title = {{The Maximum Label Propagation Algorithm on Sparse Random Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {58:1--58:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.58},
URN = {urn:nbn:de:0030-drops-112731},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.58},
annote = {Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection}
}
Document
RANDOM
Samplers and Extractors for Unbounded Functions
Abstract
Błasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions f from {0,1}^m to the real numbers such that f(U_m) has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best known constructions of averaging samplers for [0,1]-bounded functions in the regime of parameters where the approximation error epsilon and failure probability delta are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman’s equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the Kullback-Leibler (KL) divergence, are of independent interest. In particular, KL-extractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and non-constructively) as standard extractors.
Cite as
Rohit Agrawal. Samplers and Extractors for Unbounded Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 59:1-59:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{agrawal:LIPIcs.APPROX-RANDOM.2019.59,
author = {Agrawal, Rohit},
title = {{Samplers and Extractors for Unbounded Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {59:1--59:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.59},
URN = {urn:nbn:de:0030-drops-112749},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.59},
annote = {Keywords: averaging samplers, subgaussian samplers, randomness extractors, Kullback-Leibler divergence}
}
Document
RANDOM
Successive Minimum Spanning Trees
Abstract
In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution Exp(1)), let T_1 be the MST (the spanning tree of minimum weight) and let T_k be the MST after deletion of the edges of all previous trees T_i, i<k. We show that each tree’s weight w(T_k) converges in probability to a constant gamma_k with 2k-2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k-1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2.
Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) -> gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal’s algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) -> rho_infty(x) as k -> infty, uniformly in x in R.
Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.
Cite as
Svante Janson and Gregory B. Sorkin. Successive Minimum Spanning Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{janson_et_al:LIPIcs.APPROX-RANDOM.2019.60,
author = {Janson, Svante and Sorkin, Gregory B.},
title = {{Successive Minimum Spanning Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {60:1--60:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.60},
URN = {urn:nbn:de:0030-drops-112759},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.60},
annote = {Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type branching process, functional fixed point, robust optimization, Kruskal’s algorithm}
}
Document
RANDOM
Simple Analysis of Sparse, Sign-Consistent JL
Abstract
Allen-Zhu, Gelashvili, Micali, and Shavit construct a sparse, sign-consistent Johnson-Lindenstrauss distribution, and prove that this distribution yields an essentially optimal dimension for the correct choice of sparsity. However, their analysis of the upper bound on the dimension and sparsity requires a complicated combinatorial graph-based argument similar to Kane and Nelson’s analysis of sparse JL. We present a simple, combinatorics-free analysis of sparse, sign-consistent JL that yields the same dimension and sparsity upper bounds as the original analysis. Our analysis also yields dimension/sparsity tradeoffs, which were not previously known.
As with previous proofs in this area, our analysis is based on applying Markov’s inequality to the pth moment of an error term that can be expressed as a quadratic form of Rademacher variables. Interestingly, we show that, unlike in previous work in the area, the traditionally used Hanson-Wright bound is not strong enough to yield our desired result. Indeed, although the Hanson-Wright bound is known to be optimal for gaussian degree-2 chaos, it was already shown to be suboptimal for Rademachers. Surprisingly, we are able to show a simple moment bound for quadratic forms of Rademachers that is sufficiently tight to achieve our desired result, which given the ubiquity of moment and tail bounds in theoretical computer science, is likely to be of broader interest.
Cite as
Meena Jagadeesan. Simple Analysis of Sparse, Sign-Consistent JL. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{jagadeesan:LIPIcs.APPROX-RANDOM.2019.61,
author = {Jagadeesan, Meena},
title = {{Simple Analysis of Sparse, Sign-Consistent JL}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {61:1--61:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.61},
URN = {urn:nbn:de:0030-drops-112762},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.61},
annote = {Keywords: Dimensionality reduction, Random projections, Johnson-Lindenstrauss distribution, Hanson-Wright bound, Neuroscience-based constraints}
}
Document
RANDOM
Streaming Coreset Constructions for M-Estimators
Abstract
We introduce a new method of maintaining a (k,epsilon)-coreset for clustering M-estimators over insertion-only streams. Let (P,w) be a weighted set (where w : P - > [0,infty) is the weight function) of points in a rho-metric space (meaning a set X equipped with a positive-semidefinite symmetric function D such that D(x,z) <=rho(D(x,y) + D(y,z)) for all x,y,z in X). For any set of points C, we define COST(P,w,C) = sum_{p in P} w(p) min_{c in C} D(p,c). A (k,epsilon)-coreset for (P,w) is a weighted set (Q,v) such that for every set C of k points, (1-epsilon)COST(P,w,C) <= COST(Q,v,C) <= (1+epsilon)COST(P,w,C). Essentially, the coreset (Q,v) can be used in place of (P,w) for all operations concerning the COST function. Coresets, as a method of data reduction, are used to solve fundamental problems in machine learning of streaming and distributed data.
M-estimators are functions D(x,y) that can be written as psi(d(x,y)) where ({X}, d) is a true metric (i.e. 1-metric) space. Special cases of M-estimators include the well-known k-median (psi(x) =x) and k-means (psi(x) = x^2) functions. Our technique takes an existing offline construction for an M-estimator coreset and converts it into the streaming setting, where n data points arrive sequentially. To our knowledge, this is the first streaming construction for any M-estimator that does not rely on the merge-and-reduce tree. For example, our coreset for streaming metric k-means uses O(epsilon^{-2} k log k log n) points of storage. The previous state-of-the-art required storing at least O(epsilon^{-2} k log k log^{4} n) points.
Cite as
Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. Streaming Coreset Constructions for M-Estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2019.62,
author = {Braverman, Vladimir and Feldman, Dan and Lang, Harry and Rus, Daniela},
title = {{Streaming Coreset Constructions for M-Estimators}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {62:1--62:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.62},
URN = {urn:nbn:de:0030-drops-112778},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.62},
annote = {Keywords: Streaming, Clustering, Coresets}
}
Document
RANDOM
Pairwise Independent Random Walks Can Be Slightly Unbounded
Abstract
A family of problems that have been studied in the context of various streaming algorithms are generalizations of the fact that the expected maximum distance of a 4-wise independent random walk on a line over n steps is O(sqrt{n}). For small values of k, there exist k-wise independent random walks that can be stored in much less space than storing n random bits, so these properties are often useful for lowering space bounds. In this paper, we show that for all of these examples, 4-wise independence is required by demonstrating a pairwise independent random walk with steps uniform in +/- 1 and expected maximum distance Omega(sqrt{n} lg n) from the origin. We also show that this bound is tight for the first and second moment, i.e. the expected maximum square distance of a 2-wise independent random walk is always O(n lg^2 n). Also, for any even k >= 4, we show that the kth moment of the maximum distance of any k-wise independent random walk is O(n^{k/2}). The previous two results generalize to random walks tracking insertion-only streams, and provide higher moment bounds than currently known. We also prove a generalization of Kolmogorov’s maximal inequality by showing an asymptotically equivalent statement that requires only 4-wise independent random variables with bounded second moments, which also generalizes a result of Błasiok.
Cite as
Shyam Narayanan. Pairwise Independent Random Walks Can Be Slightly Unbounded. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 63:1-63:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{narayanan:LIPIcs.APPROX-RANDOM.2019.63,
author = {Narayanan, Shyam},
title = {{Pairwise Independent Random Walks Can Be Slightly Unbounded}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {63:1--63:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.63},
URN = {urn:nbn:de:0030-drops-112787},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.63},
annote = {Keywords: k-wise Independence, Random Walks, Moments, Chaining}
}
Document
RANDOM
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Abstract
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to e^{-f} where f:R^d -> R is mu-strongly convex and L-smooth (the condition number is kappa = L/mu). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is O(kappa), improving on the previous best bound of O(kappa^{1.5}); we complement this with an example where the relaxation time is Omega(kappa). When implemented using a nearly optimal ODE solver, HMC returns an epsilon-approximate point in 2-Wasserstein distance using O~((kappa d)^{0.5} epsilon^{-1}) gradient evaluations per step and O~((kappa d)^{1.5}epsilon^{-1}) total time.
Cite as
Zongchen Chen and Santosh S. Vempala. Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2019.64,
author = {Chen, Zongchen and Vempala, Santosh S.},
title = {{Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {64:1--64:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.64},
URN = {urn:nbn:de:0030-drops-112790},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.64},
annote = {Keywords: logconcave distribution, sampling, Hamiltonian Monte Carlo, spectral gap, strong convexity}
}
Document
RANDOM
Exploring Differential Obliviousness
Abstract
In a recent paper, Chan et al. [SODA '19] proposed a relaxation of the notion of (full) memory obliviousness, which was introduced by Goldreich and Ostrovsky [J. ACM '96] and extensively researched by cryptographers. The new notion, differential obliviousness, requires that any two neighboring inputs exhibit similar memory access patterns, where the similarity requirement is that of differential privacy. Chan et al. demonstrated that differential obliviousness allows achieving improved efficiency for several algorithmic tasks, including sorting, merging of sorted lists, and range query data structures.
In this work, we continue the exploration of differential obliviousness, focusing on algorithms that do not necessarily examine all their input. This choice is motivated by the fact that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input. In particular, we explore property testing, where we show that differential obliviousness yields an almost linear improvement in overhead in the dense graph model, and at most quadratic improvement in the bounded degree model. We also explore tasks where a non-oblivious algorithm would need to explore different portions of the input, where the latter would depend on the input itself, and where we show that such a behavior can be maintained under differential obliviousness, but not under full obliviousness. Our examples suggest that there would be benefits in further exploring which class of computational tasks are amenable to differential obliviousness.
Cite as
Amos Beimel, Kobbi Nissim, and Mohammad Zaheri. Exploring Differential Obliviousness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{beimel_et_al:LIPIcs.APPROX-RANDOM.2019.65,
author = {Beimel, Amos and Nissim, Kobbi and Zaheri, Mohammad},
title = {{Exploring Differential Obliviousness}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {65:1--65:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.65},
URN = {urn:nbn:de:0030-drops-112803},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.65},
annote = {Keywords: Differential Obliviousness, Differential Privacy, Oblivious RAM, Graph Property Testing}
}
Document
RANDOM
Thresholds in Random Motif Graphs
Abstract
We introduce a natural generalization of the Erdős-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph G(H,n,p) is the random (multi)graph obtained by adding an instance of a fixed graph H on each of the copies of H in the complete graph on n vertices, independently with probability p. We establish that every monotone property has a threshold in this model, and determine the thresholds for connectivity, Hamiltonicity, the existence of a perfect matching, and subgraph appearance. Moreover, in the first three cases we give the analogous hitting time results; with high probability, the first graph in the random motif graph process that has minimum degree one (or two) is connected and contains a perfect matching (or Hamiltonian respectively).
Cite as
Michael Anastos, Peleg Michaeli, and Samantha Petti. Thresholds in Random Motif Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{anastos_et_al:LIPIcs.APPROX-RANDOM.2019.66,
author = {Anastos, Michael and Michaeli, Peleg and Petti, Samantha},
title = {{Thresholds in Random Motif Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {66:1--66:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.66},
URN = {urn:nbn:de:0030-drops-112819},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.66},
annote = {Keywords: Random graph, Connectivity, Hamiltonicty, Small subgraphs}
}
Document
RANDOM
Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions
Abstract
The random-cluster (FK) model is a key tool for the study of phase transitions and for the design of efficient Markov chain Monte Carlo (MCMC) sampling algorithms for the Ising/Potts model. It is well-known that in the high-temperature region beta<beta_c(q) of the q-state Ising/Potts model on an n x n box Lambda_n of the integer lattice Z^2, spin correlations decay exponentially fast; this property holds even arbitrarily close to the boundary of Lambda_n and uniformly over all boundary conditions. A direct consequence of this property is that the corresponding single-site update Markov chain, known as the Glauber dynamics, mixes in optimal O(n^2 log{n}) steps on Lambda_{n} for all choices of boundary conditions. We study the effect of boundary conditions on the FK-dynamics, the analogous Glauber dynamics for the random-cluster model.
On Lambda_n the random-cluster model with parameters (p,q) has a sharp phase transition at p = p_c(q). Unlike the Ising/Potts model, the random-cluster model has non-local interactions which can be forced by boundary conditions: external wirings of boundary vertices of Lambda_n. We consider the broad and natural class of boundary conditions that are realizable as a configuration on Z^2 \ Lambda_n. Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures (p << p_c(q)). In this paper, we prove that when q>1 and p != p_c(q) the mixing time of the FK-dynamics is polynomial in n for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), Blanca and Sinclair (2017) had proved that the FK-dynamics in the same setting mixes in optimal O(n^2 log n) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.
Cite as
Antonio Blanca, Reza Gheissari, and Eric Vigoda. Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{blanca_et_al:LIPIcs.APPROX-RANDOM.2019.67,
author = {Blanca, Antonio and Gheissari, Reza and Vigoda, Eric},
title = {{Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {67:1--67:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.67},
URN = {urn:nbn:de:0030-drops-112827},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.67},
annote = {Keywords: Markov chain, mixing time, random-cluster model, Glauber dynamics, spatial mixing}
}
Document
RANDOM
On List Recovery of High-Rate Tensor Codes
Abstract
We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms.
In the current work we obtain the following results:
1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms.
2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time N^{o(1)}. This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity N^{epsilon} with rate that is exponentially small in 1/epsilon.
3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of N^{Omega(1/log log N)} on the product of query complexity and output list size for locally list recovering high-rate tensor codes.
Cite as
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On List Recovery of High-Rate Tensor Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 68:1-68:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{kopparty_et_al:LIPIcs.APPROX-RANDOM.2019.68,
author = {Kopparty, Swastik and Resch, Nicolas and Ron-Zewi, Noga and Saraf, Shubhangi and Silas, Shashwat},
title = {{On List Recovery of High-Rate Tensor Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {68:1--68:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.68},
URN = {urn:nbn:de:0030-drops-112832},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.68},
annote = {Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes}
}
Document
RANDOM
Approximate F_2-Sketching of Valuation Functions
Abstract
We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function f : F_2^n - > R with small expected squared error. We develop a general theory of linear sketching for such functions through which we analyze their dimension for most commonly studied types of valuation functions: additive, budget-additive, coverage, alpha-Lipschitz submodular and matroid rank functions. This gives a characterization of how many bits of information have to be stored about the input x so that one can compute f under additive updates to its coordinates.
Our results are tight in most cases and we also give extensions to the distributional version of the problem where the input x in F_2^n is generated uniformly at random. Using known connections with dynamic streaming algorithms, both upper and lower bounds on dimension obtained in our work extend to the space complexity of algorithms evaluating f(x) under long sequences of additive updates to the input x presented as a stream. Similar results hold for simultaneous communication in a distributed setting.
Cite as
Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 69:1-69:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{yaroslavtsev_et_al:LIPIcs.APPROX-RANDOM.2019.69,
author = {Yaroslavtsev, Grigory and Zhou, Samson},
title = {{Approximate F\underline2-Sketching of Valuation Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {69:1--69:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.69},
URN = {urn:nbn:de:0030-drops-112848},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.69},
annote = {Keywords: Sublinear algorithms, linear sketches, approximation algorithms}
}
Document
RANDOM
Streaming Verification of Graph Computations via Graph Structure
Abstract
We give new algorithms in the annotated data streaming setting - also known as verifiable data stream computation - for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to trust the prover. As is well established, several problems that admit no sublinear-space algorithms under traditional streaming do allow protocols using a sublinear amount of prover/verifier communication and sublinear-space verification. We give algorithms for many well-studied graph problems including triangle counting, its generalization to subgraph counting, maximum matching, problems about the existence (or not) of short paths, finding the shortest path between two vertices, and testing for an independent set. While some of these problems have been studied before, our results achieve new tradeoffs between space and communication costs that were hitherto unknown. In particular, two of our results disprove explicit conjectures of Thaler (ICALP, 2016) by giving triangle counting and maximum matching algorithms for n-vertex graphs, using o(n) space and o(n^2) communication.
Cite as
Amit Chakrabarti and Prantar Ghosh. Streaming Verification of Graph Computations via Graph Structure. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{chakrabarti_et_al:LIPIcs.APPROX-RANDOM.2019.70,
author = {Chakrabarti, Amit and Ghosh, Prantar},
title = {{Streaming Verification of Graph Computations via Graph Structure}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {70:1--70:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.70},
URN = {urn:nbn:de:0030-drops-112856},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.70},
annote = {Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms}
}
Document
RANDOM
Approximate Degree, Secret Sharing, and Concentration Phenomena
Abstract
The epsilon-approximate degree deg~_epsilon(f) of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are:
- We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution.
- We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg~_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena.
As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg~_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg~_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.
Cite as
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71,
author = {Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher},
title = {{Approximate Degree, Secret Sharing, and Concentration Phenomena}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {71:1--71:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.71},
URN = {urn:nbn:de:0030-drops-112869},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.71},
annote = {Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing}
}
Document
RANDOM
Improved Extractors for Recognizable and Algebraic Sources
Abstract
We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = 1} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.
Our first method shows that if C admits XOR amplification, then we can construct a seedless extractor for C-recognizable sources by using a mildly hard function for C as a black box. By exploiting this reduction, we give polynomial-time, seedless randomness extractors for three natural recognizable sources: (1) constant-degree algebraic sources over any prime field, where constant-degree algebraic sources are uniform distributions over the set of zeros of a system of constant degree polynomials; (2) sources recognizable by randomized multiparty communication protocols of cn bits, where c>0 is a small enough constant; (3) halfspace sources, or sources recognizable by linear threshold functions. In particular, the new extractor for each of these three sources has linear output length and exponentially small error for min-entropy k >= (1-alpha)n, where alpha>0 is a small enough constant.
Our second method shows that a seed-extending pseudorandom generator with exponentially small error for C yields an extractor with exponentially small error for C-recognizable sources, improving a reduction by Kinne, Melkebeek, and Shaltiel [Kinne et al., 2012]. Using the hardness of the parity function against AC^0 [Håstad, 1987], we significantly improve Shaltiel’s extractor [Shaltiel, 2011] for AC^0-recognizable sources. Finally, assuming sufficiently strong one-way permutations, we construct seedless extractors for sources recognizable by BPP algorithms, and these extractors run in quasi-polynomial time.
Cite as
Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
Copy BibTex To Clipboard
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.72,
author = {Li, Fu and Zuckerman, David},
title = {{Improved Extractors for Recognizable and Algebraic Sources}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {72:1--72:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
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.2019.72},
URN = {urn:nbn:de:0030-drops-112873},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.72},
annote = {Keywords: Extractor, Pseudorandomness}
}