8 Search Results for "Minzer, Dor"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.9
Quantum Merlin-Arthur and Proofs Without Relative Phase

Authors: Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [Grilo et al., 2014]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu [Jeronimo and Wu, 2023]) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some other constant gap is equal to QMA. One interpretation is that Merlin’s ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) ⊆ NEXP.
Cite as

Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and Proofs Without Relative Phase. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.ITCS.2024.9,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal},
  title =	{{Quantum Merlin-Arthur and Proofs Without Relative Phase}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.9},
  URN =		{urn:nbn:de:0030-drops-195370},
  doi =		{10.4230/LIPIcs.ITCS.2024.9},
  annote =	{Keywords: quantum complexity, QMA(2), PCPs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.51
NP-Hardness of Almost Coloring Almost 3-Colorable Graphs

Authors: Yahli Hecht, Dor Minzer, and Muli Safra

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

Abstract
A graph G = (V,E) is said to be (k,δ) almost colorable if there is a subset of vertices V' ⊆ V of size at least (1-δ)|V| such that the induced subgraph of G on V' is k-colorable. We prove that for all k, there exists δ > 0 such for all ε > 0, given a graph G it is NP-hard (under randomized reductions) to distinguish between: 1) Yes case: G is (3,ε) almost colorable. 2) No case: G is not (k,δ) almost colorable. This improves upon an earlier result of Khot et al. [Irit Dinur et al., 2018], who showed a weaker result wherein in the "yes case" the graph is (4,ε) almost colorable.
Cite as

Yahli Hecht, Dor Minzer, and Muli Safra. NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hecht_et_al:LIPIcs.APPROX/RANDOM.2023.51,
  author =	{Hecht, Yahli and Minzer, Dor and Safra, Muli},
  title =	{{NP-Hardness of Almost Coloring Almost 3-Colorable Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.51},
  URN =		{urn:nbn:de:0030-drops-188761},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.51},
  annote =	{Keywords: PCP, Hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.25
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
DOI: 10.4230/LIPIcs.ITCS.2023.26
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.43
Expander Random Walks: The General Case and Limitations

Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.
Cite as

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43,
  author =	{Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon},
  title =	{{Expander Random Walks: The General Case and Limitations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43},
  URN =		{urn:nbn:de:0030-drops-163849},
  doi =		{10.4230/LIPIcs.ICALP.2022.43},
  annote =	{Keywords: Expander Graphs, Random Walks, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.5
Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies

Authors: Mark Braverman and Dor Minzer

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
What is the least surface area of a permutation-symmetric body B whose ℤⁿ translations tile ℝⁿ? Since any such body must have volume 1, the isoperimetric inequality implies that its surface area must be at least Ω(√n). Remarkably, Kindler et al. showed that for general bodies B this is tight, i.e. that there is a tiling body of ℝⁿ whose surface area is O(√n). In theoretical computer science, the tiling problem is intimately related to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct non-trivial tilings of ℝⁿ. In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutation-symmetric variant of the tiling problem in ℝⁿ. We show that any permutation-symmetric body that tiles ℝⁿ must have surface area at least Ω(n/√{log n}), and that this bound is tight, i.e. that there is a permutation-symmetric tiling body of ℝⁿ with surface area O(n/√{log n}). We also give matching bounds for the value of the symmetric parallel repetition of Raz’s odd cycle game. Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies.
Cite as

Mark Braverman and Dor Minzer. Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 5:1-5:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.CCC.2021.5,
  author =	{Braverman, Mark and Minzer, Dor},
  title =	{{Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{5:1--5:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.5},
  URN =		{urn:nbn:de:0030-drops-142796},
  doi =		{10.4230/LIPIcs.CCC.2021.5},
  annote =	{Keywords: PCP, Parallel Repetition, Tilings}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.26
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

Authors: Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, we avoid using the hypercontractive inequality that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.
Cite as

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kelman_et_al:LIPIcs.ITCS.2021.26,
  author =	{Kelman, Esty and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli},
  title =	{{Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.26},
  URN =		{urn:nbn:de:0030-drops-135657},
  doi =		{10.4230/LIPIcs.ITCS.2021.26},
  annote =	{Keywords: Fourier Analysis, Hypercontractivity, Log-Sobolev Inequality}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.27
On Rich 2-to-1 Games

Authors: Mark Braverman, Subhash Khot, and Dor Minzer

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.
Cite as

Mark Braverman, Subhash Khot, and Dor Minzer. On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ITCS.2021.27,
  author =	{Braverman, Mark and Khot, Subhash and Minzer, Dor},
  title =	{{On Rich 2-to-1 Games}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.27},
  URN =		{urn:nbn:de:0030-drops-135666},
  doi =		{10.4230/LIPIcs.ITCS.2021.27},
  annote =	{Keywords: PCP, Unique-Games, Perfect Completeness}
}
  • Refine by Author
  • 7 Minzer, Dor
  • 4 Braverman, Mark
  • 3 Khot, Subhash
  • 2 Kindler, Guy
  • 2 Safra, Muli
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Quantum complexity theory
  • Show More...

  • Refine by Keyword
  • 3 PCP
  • 2 Parallel Repetition
  • 1 Expander Graphs
  • 1 Fourier Analysis
  • 1 Hardness of approximation
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2021
  • 3 2023
  • 1 2022
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact