145 Search Results for "Braverman, Mark"


Volume

LIPIcs, Volume 215

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

ITCS 2022, January 31 to February 3, 2022, Berkeley, CA, USA

Editors: Mark Braverman

Document
Improved Monotonicity Testers via Hypercube Embeddings

Authors: Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer

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


Abstract
We show improved monotonicity testers for the Boolean hypercube under the p-biased measure, as well as over the hypergrid [m]ⁿ. Our results are: 1) For any p ∈ (0,1), for the p-biased hypercube we show a non-adaptive tester that makes Õ(√n/ε²) queries, accepts monotone functions with probability 1 and rejects functions that are ε-far from monotone with probability at least 2/3. 2) For all m ∈ ℕ, we show an Õ(√nm³/ε²) query monotonicity tester over [m]ⁿ. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [Subhash Khot et al., 2018]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [Hadley Black et al., 2018] had Ω(n^{5/6}) query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n', while preserving its distance from being monotone; an embedding is considered efficient if n' is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings.

Cite as

Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer. Improved Monotonicity Testers via Hypercube Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.25,
  author =	{Braverman, Mark and Khot, Subhash and Kindler, Guy and Minzer, Dor},
  title =	{{Improved Monotonicity Testers via Hypercube Embeddings}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{25:1--25:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.25},
  URN =		{urn:nbn:de:0030-drops-175285},
  doi =		{10.4230/LIPIcs.ITCS.2023.25},
  annote =	{Keywords: Property Testing, Monotonicity Testing, Isoperimetric Inequalities}
}
Document
Rounding via Low Dimensional Embeddings

Authors: Mark Braverman and Dor Minzer

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


Abstract
A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set of vertices of fractional size at most ε, at least γ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1) Max-Cut: we show that if a regular graph G = (V,E) is an (ε,γ) small-set expander that contains a cut of fractional size at least 1-δ, then one can find in G a cut of fractional size at least 1-O(δ/(εγ⁶)) in polynomial time. 2) Improved spectral partitioning, Cheeger’s inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders. Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining 𝓁₂² distances, and then perform a pre-processing step using low-dimensional geometry and the properties of 𝓁₂² distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes.

Cite as

Mark Braverman and Dor Minzer. Rounding via Low Dimensional Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 26:1-26:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.26,
  author =	{Braverman, Mark and Minzer, Dor},
  title =	{{Rounding via Low Dimensional Embeddings}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{26:1--26:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.26},
  URN =		{urn:nbn:de:0030-drops-175291},
  doi =		{10.4230/LIPIcs.ITCS.2023.26},
  annote =	{Keywords: Parallel Repetition, Small Set Expanders, Semi-Definite Programs}
}
Document
Complete Volume
LIPIcs, Volume 215, ITCS 2022, Complete Volume

Authors: Mark Braverman

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


Abstract
LIPIcs, Volume 215, ITCS 2022, Complete Volume

Cite as

13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 1-2410, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{braverman:LIPIcs.ITCS.2022,
  title =	{{LIPIcs, Volume 215, ITCS 2022, Complete Volume}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{1--2410},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022},
  URN =		{urn:nbn:de:0030-drops-155957},
  doi =		{10.4230/LIPIcs.ITCS.2022},
  annote =	{Keywords: LIPIcs, Volume 215, ITCS 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mark Braverman

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


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 0:i-0:xxiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{braverman:LIPIcs.ITCS.2022.0,
  author =	{Braverman, Mark},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{0:i--0:xxiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.0},
  URN =		{urn:nbn:de:0030-drops-155967},
  doi =		{10.4230/LIPIcs.ITCS.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Maximizing Revenue in the Presence of Intermediaries

Authors: Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, and Andres Perlroth

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


Abstract
We study the mechanism design problem of selling k items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who represents a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers. We first consider the case of k identical items where each buyer draws its private valuation for an item i.i.d. from a known λ-regular distribution. We construct a robust mechanism that, independent of the demand structure and under certain conditions on the contracts between intermediaries and buyers, obtains a constant factor of the revenue that the mechanism designer could obtain had she known the buyers' valuations. In other words, our mechanism’s expected revenue achieves a constant factor of the optimal welfare, regardless of the demand structure. Our mechanism is a simple posted-price mechanism that sets a take-it-or-leave-it per-item price that depends on k and the total number of buyers, but does not depend on the demand structure or the downstream contracts. Next we generalize our result to the case when the items are not identical. We assume that the item valuations are separable, i.e. v_{i j} = η_j v_i for buyer i and item j, with each private v_i drawn i.i.d. from a known λ-regular distribution. For this case, we design a mechanism that obtains at least a constant fraction of the optimal welfare, by using a menu of posted prices. This mechanism is also independent of the demand structure, but makes a relatively stronger assumption on the contracts between intermediaries and buyers, namely that each intermediary prefers outcomes with a higher sum of utilities of the subset of buyers represented by it.

Cite as

Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, and Andres Perlroth. Maximizing Revenue in the Presence of Intermediaries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aggarwal_et_al:LIPIcs.ITCS.2022.1,
  author =	{Aggarwal, Gagan and Bhawalkar, Kshipra and Guruganesh, Guru and Perlroth, Andres},
  title =	{{Maximizing Revenue in the Presence of Intermediaries}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.1},
  URN =		{urn:nbn:de:0030-drops-155979},
  doi =		{10.4230/LIPIcs.ITCS.2022.1},
  annote =	{Keywords: Mechanism Design, Revenue Maximization, Posted Price Mechanisms}
}
Document
Algebraic Restriction Codes and Their Applications

Authors: Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski

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


Abstract
Consider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it possible to encode the inputs in such a way that only linear functions can be evaluated over the encodings? I.e., learning an arbitrary function of the encodings will not reveal more information about the inputs than a linear combination. In this work, we introduce the notion of algebraic restriction codes (AR codes), which constrain adversaries who might compute any function to computing a linear function. Our main result is an information-theoretic construction AR codes that restrict any class of function with a bounded number of output bits to linear functions. Our construction relies on a seed which is not provided to the adversary. While interesting and natural on its own, we show an application of this notion in cryptography. In particular, we show that AR codes lead to the first construction of rate-1 oblivious transfer with statistical sender security from the Decisional Diffie-Hellman assumption, and the first-ever construction that makes black-box use of cryptography. Previously, such protocols were known only from the LWE assumption, using non-black-box cryptographic techniques. We expect our new notion of AR codes to find further applications, e.g., in the context of non-malleability, in the future.

Cite as

Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski. Algebraic Restriction Codes and Their Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aggarwal_et_al:LIPIcs.ITCS.2022.2,
  author =	{Aggarwal, Divesh and D\"{o}ttling, Nico and Dujmovic, Jesko and Hajiabadi, Mohammad and Malavolta, Giulio and Obremski, Maciej},
  title =	{{Algebraic Restriction Codes and Their Applications}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.2},
  URN =		{urn:nbn:de:0030-drops-155987},
  doi =		{10.4230/LIPIcs.ITCS.2022.2},
  annote =	{Keywords: Algebraic Restriction Codes, Oblivious Transfer, Rate 1, Statistically Sender Private, OT, Diffie-Hellman, DDH}
}
Document
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Authors: Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams

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


Abstract
In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin-Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: - Certifying that a list of n integers has no 3-SUM solution can be done in Merlin-Arthur time Õ(n). Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in Õ(n^{1.5}) time (that is, there is a proof system with proofs of length Õ(n^{1.5}) and a deterministic verifier running in Õ(n^{1.5}) time). - Counting the number of k-cliques with total edge weight equal to zero in an n-node graph can be done in Merlin-Arthur time Õ(n^{⌈ k/2⌉}) (where k ≥ 3). For odd k, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in an m-edge graph can be done in Merlin-Arthur time Õ(m). Previous Merlin-Arthur protocols by Williams [CCC'16] and Björklund and Kaski [PODC'16] could only count k-cliques in unweighted graphs, and had worse running times for small k. - Computing the All-Pairs Shortest Distances matrix for an n-node graph can be done in Merlin-Arthur time Õ(n²). Note this is optimal, as the matrix can have Ω(n²) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an Õ(n^{2.94}) nondeterministic time algorithm. - Certifying that an n-variable k-CNF is unsatisfiable can be done in Merlin-Arthur time 2^{n/2 - n/O(k)}. We also observe an algebrization barrier for the previous 2^{n/2}⋅ poly(n)-time Merlin-Arthur protocol of R. Williams [CCC'16] for #SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol for k-UNSAT running in 2^{n/2}/n^{ω(1)} time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol. - Certifying a Quantified Boolean Formula is true can be done in Merlin-Arthur time 2^{4n/5}⋅ poly(n). Previously, the only nontrivial result known along these lines was an Arthur-Merlin-Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in 2^{2n/3}⋅poly(n) time. Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution to n integers can be done in Merlin-Arthur time 2^{n/3}⋅poly(n), improving on the previous best protocol by Nederlof [IPL 2017] which took 2^{0.49991n}⋅poly(n) time.

Cite as

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ITCS.2022.3,
  author =	{Akmal, Shyan and Chen, Lijie and Jin, Ce and Raj, Malvika and Williams, Ryan},
  title =	{{Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{3:1--3:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.3},
  URN =		{urn:nbn:de:0030-drops-155991},
  doi =		{10.4230/LIPIcs.ITCS.2022.3},
  annote =	{Keywords: Fine-grained complexity, Merlin-Arthur proofs}
}
Document
Pre-Constrained Encryption

Authors: Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta

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


Abstract
In all existing encryption systems, the owner of the master secret key has the ability to decrypt all ciphertexts. In this work, we propose a new notion of pre-constrained encryption (PCE) where the owner of the master secret key does not have "full" decryption power. Instead, its decryption power is constrained in a pre-specified manner during the system setup. We present formal definitions and constructions of PCE, and discuss societal applications and implications to some well-studied cryptographic primitives.

Cite as

Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta. Pre-Constrained Encryption. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITCS.2022.4,
  author =	{Ananth, Prabhanjan and Jain, Abhishek and Jin, Zhengzhong and Malavolta, Giulio},
  title =	{{Pre-Constrained Encryption}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.4},
  URN =		{urn:nbn:de:0030-drops-156001},
  doi =		{10.4230/LIPIcs.ITCS.2022.4},
  annote =	{Keywords: Advanced encryption systems}
}
Document
Domain Sparsification of Discrete Distributions Using Entropic Independence

Authors: Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang

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


Abstract
We present a framework for speeding up the time it takes to sample from discrete distributions μ defined over subsets of size k of a ground set of n elements, in the regime where k is much smaller than n. We show that if one has access to estimates of marginals P_{S∼ μ} {i ∈ S}, then the task of sampling from μ can be reduced to sampling from related distributions ν supported on size k subsets of a ground set of only n^{1-α}⋅ poly(k) elements. Here, 1/α ∈ [1, k] is the parameter of entropic independence for μ. Further, our algorithm only requires sparsified distributions ν that are obtained by applying a sparse (mostly 0) external field to μ, an operation that for many distributions μ of interest, retains algorithmic tractability of sampling from ν. This phenomenon, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals of μ, and in return reduce the amortized cost needed to produce many samples from the distribution μ, as is often needed in upstream tasks such as counting and inference. For a wide range of distributions where α = Ω(1), our result reduces the domain size, and as a corollary, the cost-per-sample, by a poly(n) factor. Examples include monomers in a monomer-dimer system, non-symmetric determinantal point processes, and partition-constrained Strongly Rayleigh measures. Our work significantly extends the reach of prior work of Anari and Dereziński who obtained domain sparsification for distributions with a log-concave generating polynomial (corresponding to α = 1). As a corollary of our new analysis techniques, we also obtain a less stringent requirement on the accuracy of marginal estimates even for the case of log-concave polynomials; roughly speaking, we show that constant-factor approximation is enough for domain sparsification, improving over O(1/k) relative error established in prior work.

Cite as

Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.ITCS.2022.5,
  author =	{Anari, Nima and Derezi\'{n}ski, Micha{\l} and Vuong, Thuy-Duong and Yang, Elizabeth},
  title =	{{Domain Sparsification of Discrete Distributions Using Entropic Independence}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.5},
  URN =		{urn:nbn:de:0030-drops-156013},
  doi =		{10.4230/LIPIcs.ITCS.2022.5},
  annote =	{Keywords: Domain Sparsification, Markov Chains, Sampling, Entropic Independence}
}
Document
Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians

Authors: Anurag Anshu and Chinmay Nirkhe

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


Abstract
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings [Freedman and Hastings, 2014] - which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states - identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.

Cite as

Anurag Anshu and Chinmay Nirkhe. Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.ITCS.2022.6,
  author =	{Anshu, Anurag and Nirkhe, Chinmay},
  title =	{{Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.6},
  URN =		{urn:nbn:de:0030-drops-156023},
  doi =		{10.4230/LIPIcs.ITCS.2022.6},
  annote =	{Keywords: quantum pcps, local hamiltonians, error-correcting codes}
}
Document
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems

Authors: Shiri Antaki, Quanquan C. Liu, and Shay Solomon

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


Abstract
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in O(1) (perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and (Δ + 1)-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular - robust against an adaptive adversary. Most of our focus is on our MIS algorithm, which achieves O (m^{2/3}log² n) amortized messages in O(log² n) amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan [SOSA'21] up to a polylog n factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. [STOC'18], uses O(m^{3/4}) amortized messages in O(1) amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog n increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the network is connected at all times, which seems excessively strong when it comes to dynamic networks. Using techniques similar to the ones we developed for our MIS algorithm, we also provide deterministic algorithms for MM, approximate MCM and (Δ + 1)-vertex coloring whose message complexities match or nearly match the update times of the best centralized algorithms, while having either constant or polylog(n) round complexities.

Cite as

Shiri Antaki, Quanquan C. Liu, and Shay Solomon. Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{antaki_et_al:LIPIcs.ITCS.2022.7,
  author =	{Antaki, Shiri and Liu, Quanquan C. and Solomon, Shay},
  title =	{{Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{7:1--7:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-156039},
  doi =		{10.4230/LIPIcs.ITCS.2022.7},
  annote =	{Keywords: dynamic graph algorithms, distributed algorithms, symmetry breaking problems, maximal independent set, matching, coloring}
}
Document
Secret Sharing, Slice Formulas, and Monotone Real Circuits

Authors: Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi

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


Abstract
A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined "authorized" sets of parties can reconstruct the secret s, and all other "unauthorized" sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^{n-o(n)} and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^{0.994n+o(n)}, and this was further improved by several follow-ups accumulating in an upper bound of 1.5^{n+o(n)} (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^{n^{1-ε}} for some constant ε > 0, or even all the way down to polynomial upper-bounds. In this paper, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) - a computational model that was introduced by Pudlák (J. Symb. Log., 1997) in the context of proof complexity. We introduce a new notion of "separable" MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes implicitly give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques. We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity 1.5^{n+o(n)}. To the best of our knowledge, this is the first improvement over the trivial 2^{n-o(n)} upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.

Cite as

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITCS.2022.8,
  author =	{Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann},
  title =	{{Secret Sharing, Slice Formulas, and Monotone Real Circuits}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.8},
  URN =		{urn:nbn:de:0030-drops-156046},
  doi =		{10.4230/LIPIcs.ITCS.2022.8},
  annote =	{Keywords: Secret Sharing Schemes, Monotone Real Circuits}
}
Document
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams

Authors: Sepehr Assadi and Vihan Shah

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


Abstract
We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with asymptotically optimal space: for any n-vertex graph, our algorithm with high probability outputs an α-approximate matching in a single pass using O(n²/α³) bits of space. A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to n^{o(1)} factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to polylog factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the Dark-Konrad lower bound up to O(1) factors, thus completing this research direction. Our approach consists of two main steps: we first (provably) identify a family of graphs, similar to the instances used in prior work to establish the lower bounds for this problem, as the only "hard" instances to focus on. These graphs include an induced subgraph which is both sparse and contains a large matching. We then design a dynamic streaming algorithm for this family of graphs which is more efficient than prior work. The key to this efficiency is a novel sketching method, which bypasses the typical loss of polylog(n)-factors in space compared to standard L₀-sampling primitives, and can be of independent interest in designing optimal algorithms for other streaming problems.

Cite as

Sepehr Assadi and Vihan Shah. An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.9,
  author =	{Assadi, Sepehr and Shah, Vihan},
  title =	{{An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.9},
  URN =		{urn:nbn:de:0030-drops-156054},
  doi =		{10.4230/LIPIcs.ITCS.2022.9},
  annote =	{Keywords: Graph streaming algorithms, Sketching, Maximum matching}
}
Document
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

Authors: Sepehr Assadi and Chen Wang

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


Abstract
We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for n-vertex (+/-)-labeled graphs G: - A sublinear-time algorithm that with high probability returns a constant approximation clustering of G in O(nlog²n) time assuming access to the adjacency list of the (+)-labeled edges of G (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee. - A semi-streaming algorithm that with high probability returns a constant approximation clustering of G in O(n log n) space and a single pass over the edges of the graph G (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with o(n²) space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest.

Cite as

Sepehr Assadi and Chen Wang. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.10,
  author =	{Assadi, Sepehr and Wang, Chen},
  title =	{{Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.10},
  URN =		{urn:nbn:de:0030-drops-156067},
  doi =		{10.4230/LIPIcs.ITCS.2022.10},
  annote =	{Keywords: Correlation Clustering, Sublinear Algorithms, Semi-streaming Algorithms, Sublinear time Algorithms}
}
  • Refine by Author
  • 19 Braverman, Mark
  • 4 Malavolta, Giulio
  • 4 Minzer, Dor
  • 3 Hirahara, Shuichi
  • 3 Ishai, Yuval
  • Show More...

  • Refine by Classification
  • 12 Theory of computation → Problems, reductions and completeness
  • 8 Theory of computation → Circuit complexity
  • 8 Theory of computation → Computational complexity and cryptography
  • 8 Theory of computation → Design and analysis of algorithms
  • 8 Theory of computation → Quantum complexity theory
  • Show More...

  • Refine by Keyword
  • 6 communication complexity
  • 4 Communication Complexity
  • 4 Lower Bounds
  • 4 Mechanism Design
  • 4 average-case complexity
  • Show More...

  • Refine by Type
  • 144 document
  • 1 volume

  • Refine by Publication Year
  • 123 2022
  • 6 2021
  • 3 2018
  • 2 2009
  • 2 2013
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail