Search Results

Documents authored by Regev, Oded

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.43
Nearly Optimal Embeddings of Flat Tori

Authors: Ishan Agarwal, Oded Regev, and Yi Tang

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

Abstract
We show that for any n-dimensional lattice ℒ ⊆ ℝⁿ, the torus ℝⁿ/ℒ can be embedded into Hilbert space with O(√{nlog n}) distortion. This improves the previously best known upper bound of O(n√{log n}) shown by Haviv and Regev (APPROX 2010, J. Topol. Anal. 2013) and approaches the lower bound of Ω(√n) due to Khot and Naor (FOCS 2005, Math. Ann. 2006).
Cite as

Ishan Agarwal, Oded Regev, and Yi Tang. Nearly Optimal Embeddings of Flat Tori. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.APPROX/RANDOM.2020.43,
  author =	{Agarwal, Ishan and Regev, Oded and Tang, Yi},
  title =	{{Nearly Optimal Embeddings of Flat Tori}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.43},
  URN =		{urn:nbn:de:0030-drops-126464},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.43},
  annote =	{Keywords: Lattices, metric embeddings, flat torus}
}
Document
DOI: 10.4230/DagRep.7.3.45
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)

Authors: Anna Gál, Michal Koucký, Oded Regev, and Till Tantau

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in alphabetical order. The last section contains the abstracts of the talks.
Cite as

Anna Gál, Michal Koucký, Oded Regev, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). In Dagstuhl Reports, Volume 7, Issue 3, pp. 45-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.7.3.45,
  author =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)}},
  pages =	{45--69},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.45},
  URN =		{urn:nbn:de:0030-drops-73611},
  doi =		{10.4230/DagRep.7.3.45},
  annote =	{Keywords: Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.46
The Minrank of Random Graphs

Authors: Alexander Golovnev, Oded Regev, and Omri Weinstein

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

Abstract
The minrank of a directed graph G is the minimum rank of a matrix M that can be obtained from the adjacency matrix of G by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al., FOCS'06), network coding and distributed storage, and to Valiant's approach for proving superlinear circuit lower bounds (Valiant, Boolean Function Complexity '92). We prove tight bounds on the minrank of directed Erdos-Renyi random graphs G(n,p) for all regimes of 0<p<1. In particular, for any constant p, we show that minrk(G) = Theta(n/log n) with high probability, where G is chosen from G(n,p). This bound gives a near quadratic improvement over the previous best lower bound of Omega(sqrt{n}) (Haviv and Langberg, ISIT'12), and partially settles an open problem raised by Lubetzky and Stav (FOCS '07). Our lower bound matches the well-known upper bound obtained by the "clique covering" solution, and settles the linear index coding problem for random graphs. Finally, our result suggests a new avenue of attack, via derandomization, on Valiant's approach for proving superlinear lower bounds for logarithmic-depth semilinear circuits.
Cite as

Alexander Golovnev, Oded Regev, and Omri Weinstein. The Minrank of Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2017.46,
  author =	{Golovnev, Alexander and Regev, Oded and Weinstein, Omri},
  title =	{{The Minrank of Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.46},
  URN =		{urn:nbn:de:0030-drops-75953},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.46},
  annote =	{Keywords: circuit complexity, index coding, information theory}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.110
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Authors: Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright

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

Abstract
We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.
Cite as

Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 110-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.APPROX-RANDOM.2015.110,
  author =	{Barak, Boaz and Moitra, Ankur and O’Donnell, Ryan and Raghavendra, Prasad and Regev, Oded and Steurer, David and Trevisan, Luca and Vijayaraghavan, Aravindan and Witmer, David and Wright, John},
  title =	{{Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{110--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  URN =		{urn:nbn:de:0030-drops-52981},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  annote =	{Keywords: constraint satisfaction problems, bounded degree, advantage over random}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.58
The List-Decoding Size of Fourier-Sparse Boolean Functions

Authors: Ishay Haviv and Oded Regev

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F_2^n -> R and parameters k and d, we prove a strong upper bound on the number of k-Fourier-sparse Boolean functions that disagree with f on at most d inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of k-Fourier-sparse Boolean functions on n variables exactly is at most O(n * k * log(k)). As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz [Chicago J. Theor. Comput. Sci.,2013].
Cite as

Ishay Haviv and Oded Regev. The List-Decoding Size of Fourier-Sparse Boolean Functions. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.CCC.2015.58,
  author =	{Haviv, Ishay and Regev, Oded},
  title =	{{The List-Decoding Size of Fourier-Sparse Boolean Functions}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{58--71},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.58},
  URN =		{urn:nbn:de:0030-drops-50600},
  doi =		{10.4230/LIPIcs.CCC.2015.58},
  annote =	{Keywords: Fourier-sparse functions, list-decoding, learning theory, property testing}
}
Document
DOI: 10.4230/DagRep.4.3.62
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)

Authors: Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk

Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk. Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). In Dagstuhl Reports, Volume 4, Issue 3, pp. 62-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.4.3.62,
  author =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)}},
  pages =	{62--84},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{3},
  editor =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.62},
  URN =		{urn:nbn:de:0030-drops-45921},
  doi =		{10.4230/DagRep.4.3.62},
  annote =	{Keywords: discrete problems, computational complexity, Turing machines, Boolean circuits, arithmetic circuits, quantum computing, communication complexity, pseudorandomness, derandomization, approximation, data streams}
}
Document
DOI: 10.4230/DagSemProc.07411.6
The Unique Games Conjecture with Entangled Provers is False

Authors: Julia Kempe, Oded Regev, and Ben Toner

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers.
Cite as

Julia Kempe, Oded Regev, and Ben Toner. The Unique Games Conjecture with Entangled Provers is False. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kempe_et_al:DagSemProc.07411.6,
  author =	{Kempe, Julia and Regev, Oded and Toner, Ben},
  title =	{{The Unique Games Conjecture with Entangled Provers is False}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.6},
  URN =		{urn:nbn:de:0030-drops-13048},
  doi =		{10.4230/DagSemProc.07411.6},
  annote =	{Keywords: Unique games, entanglement}
}
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