Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
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)
@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} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eshan Chattopadhyay, Anindya De, and Rocco A. Servedio. Simple and Efficient Pseudorandom Generators from Gaussian Processes. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.4, author = {Chattopadhyay, Eshan and De, Anindya and Servedio, Rocco A.}, title = {{Simple and Efficient Pseudorandom Generators from Gaussian Processes}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {4:1--4:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.4}, URN = {urn:nbn:de:0030-drops-108262}, doi = {10.4230/LIPIcs.CCC.2019.4}, annote = {Keywords: Polynomial threshold functions, Gaussian processes, Johnson-Lindenstrauss, pseudorandom generators} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Noah Stephens-Davidowitz. A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{stephensdavidowitz:LIPIcs.CCC.2019.11, author = {Stephens-Davidowitz, Noah}, title = {{A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {11:1--11:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.11}, URN = {urn:nbn:de:0030-drops-108331}, doi = {10.4230/LIPIcs.CCC.2019.11}, annote = {Keywords: Lattices, guaranteed distance decoding, GDD, GDDP} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
David Gosset and John Smolin. A Compressed Classical Description of Quantum States. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gosset_et_al:LIPIcs.TQC.2019.8, author = {Gosset, David and Smolin, John}, title = {{A Compressed Classical Description of Quantum States}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {8:1--8:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.8}, URN = {urn:nbn:de:0030-drops-104005}, doi = {10.4230/LIPIcs.TQC.2019.8}, annote = {Keywords: Quantum computation, Quantum communication complexity, Classical simulation} }
Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)
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)
@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} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
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)
@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} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
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)
@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} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
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)
@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} }
Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)
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)
@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} }
Feedback for Dagstuhl Publishing