Steurer, David; Tiegel, Stefan SoS degree reduction with applications to clustering and robust moment estimation. (English) Zbl 07788362 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 374-393 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Steurer} and \textit{S. Tiegel}, in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 374--393 (2021; Zbl 07788362) Full Text: DOI arXiv
Bafna, Mitali; Barak, Boaz; Kothari, Pravesh K.; Schramm, Tselil; Steurer, David Playing unique games on certified small-set expanders. (English) Zbl 07765275 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1629-1642 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Bafna} et al., in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 1629--1642 (2021; Zbl 07765275) Full Text: DOI arXiv
Barak, Boaz; Kothari, Pravesh K.; Steurer, David Small-set expansion in shortcode graph and the 2-to-2 conjecture. (English) Zbl 1518.68136 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 9, 12 p. (2019). MSC: 68Q17 68R10 PDFBibTeX XMLCite \textit{B. Barak} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 9, 12 p. (2019; Zbl 1518.68136) Full Text: DOI arXiv
Raghavendra, Prasad; Schramm, Tselil; Steurer, David High dimensional estimation via sum-of-squares proofs. (English) Zbl 1451.90113 Sirakov, Boyan (ed.) et al., Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1–9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3389-3423 (2018). MSC: 90C22 PDFBibTeX XMLCite \textit{P. Raghavendra} et al., in: Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1--9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3389--3423 (2018; Zbl 1451.90113) Full Text: DOI arXiv
Kothari, Pravesh K.; Steinhardt, Jacob; Steurer, David Robust moment estimation and improved clustering via sum of squares. (English) Zbl 1434.62125 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1035-1046 (2018). MSC: 62H30 68T05 PDFBibTeX XMLCite \textit{P. K. Kothari} et al., in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1035--1046 (2018; Zbl 1434.62125) Full Text: DOI
Blais, Eric (ed.); Jansen, Klaus (ed.); Rolim, José D. P. (ed.); Steurer, David (ed.) Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. (English) Zbl 1393.68012 LIPIcs – Leibniz International Proceedings in Informatics 116. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-085-9). xvi, 58 articles, not consecutively paged, electronic only, open access (2018). MSC: 68-06 68W20 68W25 90C27 00B25 PDFBibTeX XMLCite \textit{E. Blais} (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20--22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl -- Leibniz Zentrum für Informatik (2018; Zbl 1393.68012) Full Text: DOI Link
Barak, Boaz; Kothari, Pravesh K.; Steurer, David Quantum entanglement, sum of squares, and the log rank conjecture. (English) Zbl 1369.68230 Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 975-988 (2017). MSC: 68Q25 81P15 90C22 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 975--988 (2017; Zbl 1369.68230) Full Text: DOI arXiv
Hopkins, Samuel B.; Steurer, David Bayesian estimation from few samples: community detection and related problems. arXiv:1710.00264 Preprint, arXiv:1710.00264 [cs.DS] (2017). BibTeX Cite \textit{S. B. Hopkins} and \textit{D. Steurer}, ``Bayesian estimation from few samples: community detection and related problems'', Preprint, arXiv:1710.00264 [cs.DS] (2017) Full Text: arXiv OA License
Chan, Siu On; Lee, James R.; Raghavendra, Prasad; Steurer, David Approximate constraint satisfaction requires large LP relaxations. (English) Zbl 1394.68170 J. ACM 63, No. 4, Article No. 34, 22 p. (2016). MSC: 68Q25 68Q17 90C05 PDFBibTeX XMLCite \textit{S. O. Chan} et al., J. ACM 63, No. 4, Article No. 34, 22 p. (2016; Zbl 1394.68170) Full Text: DOI arXiv
Hopkins, Samuel B.; Schramm, Tselil; Shi, Jonathan; Steurer, David Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. (English) Zbl 1377.68199 Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 178-191 (2016). MSC: 68T05 15A69 15B52 90C22 PDFBibTeX XMLCite \textit{S. B. Hopkins} et al., in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 178--191 (2016; Zbl 1377.68199) Full Text: DOI arXiv
Arora, Sanjeev; Barak, Boaz; Steurer, David Subexponential algorithms for unique games and related problems. (English) Zbl 1426.05159 J. ACM 62, No. 5, Article No. 42, 25 p. (2015). MSC: 05C85 05C50 05C57 05C70 68Q17 68W25 68W40 PDFBibTeX XMLCite \textit{S. Arora} et al., J. ACM 62, No. 5, Article No. 42, 25 p. (2015; Zbl 1426.05159) Full Text: DOI
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John Beating the random assignment on constraint satisfaction problems of bounded degree. (English) Zbl 1375.68102 Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 110-123 (2015). MSC: 68T20 PDFBibTeX XMLCite \textit{B. Barak} et al., LIPIcs -- Leibniz Int. Proc. Inform. 40, 110--123 (2015; Zbl 1375.68102) Full Text: DOI arXiv
Held, Ulrike; Brunner, Florian; Steurer, Johann; Wertli, Maria M. Bayesian meta-analysis of test accuracy in the absence of a perfect reference test applied to bone scintigraphy for the diagnosis of complex regional pain syndrome. (English) Zbl 1386.62051 Biom. J. 57, No. 6, 1020-1037 (2015). MSC: 62P10 62F15 PDFBibTeX XMLCite \textit{U. Held} et al., Biom. J. 57, No. 6, 1020--1037 (2015; Zbl 1386.62051) Full Text: DOI
Barak, Boaz; Gopalan, Parikshit; Håstad, Johan; Meka, Raghu; Raghavendra, Prasad; Steurer, David Making the long code shorter. (English) Zbl 1330.68089 SIAM J. Comput. 44, No. 5, 1287-1324 (2015). MSC: 68Q17 05C50 94B60 PDFBibTeX XMLCite \textit{B. Barak} et al., SIAM J. Comput. 44, No. 5, 1287--1324 (2015; Zbl 1330.68089) Full Text: DOI Link
Braun, Gábor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David Approximation limits of linear programs (beyond hierarchies). (English) Zbl 1343.68308 Math. Oper. Res. 40, No. 3, 756-772 (2015). MSC: 68W25 68Q17 90C05 90C22 90C27 90C59 PDFBibTeX XMLCite \textit{G. Braun} et al., Math. Oper. Res. 40, No. 3, 756--772 (2015; Zbl 1343.68308) Full Text: DOI arXiv
Lee, James R.; Raghavendra, Prasad; Steurer, David Lower bounds on the size of semidefinite programming relaxations. (English) Zbl 1321.90099 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 567-576 (2015). MSC: 90C22 68Q17 PDFBibTeX XMLCite \textit{J. R. Lee} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 567--576 (2015; Zbl 1321.90099) Full Text: DOI arXiv
Barak, Boaz; Kelner, Jonathan A.; Steurer, David Dictionary learning and tensor decomposition via the sum-of-squares method. (English) Zbl 1321.68396 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 143-151 (2015). MSC: 68T05 90C22 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 143--151 (2015; Zbl 1321.68396) Full Text: DOI arXiv
Dinur, Irit; Steurer, David; Vidick, Thomas A parallel repetition theorem for entangled projection games. (English) Zbl 1329.68116 Comput. Complexity 24, No. 2, 201-254 (2015). MSC: 68Q12 81P40 91A05 PDFBibTeX XMLCite \textit{I. Dinur} et al., Comput. Complexity 24, No. 2, 201--254 (2015; Zbl 1329.68116) Full Text: DOI arXiv Link
Letchford, Adam N. (ed.); Lasserre, Jean B. (ed.); Parrilo, Pablo A. (ed.); Steurer, David (ed.) The 2013 Newton Institute Programme on polynomial optimization. (English) Zbl 1314.00109 Math. Program. 151, No. 2 (B), 375-377 (2015). MSC: 00B25 90-06 PDFBibTeX XMLCite \textit{A. N. Letchford} (ed.) et al., Math. Program. 151, No. 2 (B), 375--377 (2015; Zbl 1314.00109) Full Text: DOI
Barak, Boaz; Steurer, David Sum-of-squares proofs and the quest toward optimal algorithms. (English) Zbl 1373.68253 Jang, Sun Young (ed.) et al., Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa (ISBN 978-89-6105-807-0/hbk; 978-89-6105-803-2/set). 509-533 (2014). MSC: 68Q25 68Q17 90C22 PDFBibTeX XMLCite \textit{B. Barak} and \textit{D. Steurer}, in: Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13--21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa. 509--533 (2014; Zbl 1373.68253) Full Text: arXiv
Dinur, Irit; Steurer, David Analytical approach to parallel repetition. (English) Zbl 1315.91001 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 624-633 (2014). MSC: 91A05 91A43 68Q17 68Q25 PDFBibTeX XMLCite \textit{I. Dinur} and \textit{D. Steurer}, in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 624--633 (2014; Zbl 1315.91001) Full Text: DOI arXiv
Barak, Boaz; Kelner, Jonathan A.; Steurer, David Rounding sum-of-squares relaxations. (English) Zbl 1315.90028 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 31-40 (2014). MSC: 90C22 68Q12 68Q25 68W25 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 31--40 (2014; Zbl 1315.90028) Full Text: DOI arXiv
Barak, Boaz; Kindler, Guy; Steurer, David On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. (English) Zbl 1361.68104 Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13, Berkeley, CA, USA, January 9–12, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1859-4). 197-214 (2013). MSC: 68Q25 68Q17 90C22 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 4th conference on innovations in theoretical computer science, ITCS'13, Berkeley, CA, USA, January 9--12, 2013. New York, NY: Association for Computing Machinery (ACM). 197--214 (2013; Zbl 1361.68104) Full Text: DOI
Arora, Sanjeev; Daskalakis, Constantinos; Steurer, David Message-passing algorithms and improved LP decoding. (English) Zbl 1364.94699 IEEE Trans. Inf. Theory 58, No. 12, 7260-7271 (2012). MSC: 94B35 PDFBibTeX XMLCite \textit{S. Arora} et al., IEEE Trans. Inf. Theory 58, No. 12, 7260--7271 (2012; Zbl 1364.94699) Full Text: DOI
Barak, Boaz; Brandão, Fernando G. S. L.; Harrow, Aram W.; Kelner, Jonathan; Steurer, David; Zhou, Yuan Hypercontractivity, sum-of-squares proofs, and their applications. (English) Zbl 1286.68176 Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 307-326 (2012). MSC: 68Q17 47A30 81P45 90C22 94A24 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19--22, 2012. New York, NY: Association for Computing Machinery (ACM). 307--326 (2012; Zbl 1286.68176) Full Text: DOI arXiv
Barak, Boaz; Hardt, Moritz; Holenstein, Thomas; Steurer, David Subsampling mathematical relaxations and average-case complexity. (English) Zbl 1373.68252 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 512-531 (2011). MSC: 68Q25 90C05 90C22 90C60 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 512--531 (2011; Zbl 1373.68252) Full Text: Link
Barak, Boaz; Raghavendra, Prasad; Steurer, David Rounding semidefinite programming hierarchies via global correlation. (English) Zbl 1292.90226 Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 472-481 (2011). MSC: 90C22 68Q17 PDFBibTeX XMLCite \textit{B. Barak} et al., in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science -- FOCS 2011, Palm Springs, CA, USA, October 22--25. Los Alamitos, CA: IEEE Computer Society. 472--481 (2011; Zbl 1292.90226) Full Text: DOI
Raghavendra, Prasad; Steurer, David Graph expansion and the unique games conjecture. (English) Zbl 1293.05373 Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 755-764 (2010). MSC: 05C85 05C70 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. Raghavendra} and \textit{D. Steurer}, in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC '10. Cambridge, MA, USA, June 5--8, 2010. New York, NY: Association for Computing Machinery (ACM). 755--764 (2010; Zbl 1293.05373) Full Text: DOI
Raghavendra, Prasad; Steurer, David; Tetali, Prasad Approximations for the isoperimetric and spectral profile of graphs and related parameters. (English) Zbl 1293.05214 Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 631-640 (2010). MSC: 05C50 05C75 68W25 90C22 60J20 65F15 PDFBibTeX XMLCite \textit{P. Raghavendra} et al., in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC '10. Cambridge, MA, USA, June 5--8, 2010. New York, NY: Association for Computing Machinery (ACM). 631--640 (2010; Zbl 1293.05214) Full Text: DOI
Steurer, David Fast SDP algorithms for constraint satisfaction problems. (English) Zbl 1288.68277 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 684-697 (2010). MSC: 68W25 68Q25 90C22 90C59 PDFBibTeX XMLCite \textit{D. Steurer}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 684--697 (2010; Zbl 1288.68277)
Steurer, David Improved rounding for parallel repeated unique games. (English) Zbl 1305.68104 Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 724-737 (2010). MSC: 68Q25 68Q17 91A20 PDFBibTeX XMLCite \textit{D. Steurer}, Lect. Notes Comput. Sci. 6302, 724--737 (2010; Zbl 1305.68104) Full Text: DOI
Raghavendra, Prasad; Steurer, David Towards computing the Grothendieck constant. (English) Zbl 1422.68135 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 525-534 (2009). MSC: 68Q25 15A60 68Q17 68W25 90C20 PDFBibTeX XMLCite \textit{P. Raghavendra} and \textit{D. Steurer}, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 525--534 (2009; Zbl 1422.68135) Full Text: Link
Arora, Sanjeev; Daskalakis, Constantinos; Steurer, David Message passing algorithms and improved LP decoding. (English) Zbl 1304.94117 Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 3-12 (2009). MSC: 94B35 68Q25 PDFBibTeX XMLCite \textit{S. Arora} et al., in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC '09. Bethesda, MD, USA, May 31 -- June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 3--12 (2009; Zbl 1304.94117) Full Text: DOI Link
Raghavendra, Prasad; Steurer, David How to round any CSP. (English) Zbl 1292.90231 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 586-594 (2009). MSC: 90C22 68Q25 68T20 90C09 90C15 PDFBibTeX XMLCite \textit{P. Raghavendra} and \textit{D. Steurer}, in: 2009 IEEE 50th annual symposium on foundations of computer science -- FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24--27, 2009. Los Alamitos, CA: IEEE Computer Society. 586--594 (2009; Zbl 1292.90231) Full Text: DOI
Raghavendra, Prasad; Steurer, David Integrality gaps for strong SDP relaxations of unique games. (English) Zbl 1292.90230 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 575-585 (2009). MSC: 90C22 68Q17 68W25 90C09 PDFBibTeX XMLCite \textit{P. Raghavendra} and \textit{D. Steurer}, in: 2009 IEEE 50th annual symposium on foundations of computer science -- FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24--27, 2009. Los Alamitos, CA: IEEE Computer Society. 575--585 (2009; Zbl 1292.90230) Full Text: DOI
Arora, Sanjeev; Steurer, David; Wigderson, Avi Towards a study of low-complexity graphs. (English) Zbl 1248.68365 Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 119-131 (2009). MSC: 68R10 68Q15 PDFBibTeX XMLCite \textit{S. Arora} et al., Lect. Notes Comput. Sci. 5555, 119--131 (2009; Zbl 1248.68365) Full Text: DOI
Sanders, Peter; Steurer, David An asymptotic approximation scheme for multigraph edge coloring. (English) Zbl 1445.68176 ACM Trans. Algorithms 4, No. 2, Article No. 21, 24 p. (2008). MSC: 68R10 05C15 05C85 68W25 PDFBibTeX XMLCite \textit{P. Sanders} and \textit{D. Steurer}, ACM Trans. Algorithms 4, No. 2, Article No. 21, 24 p. (2008; Zbl 1445.68176) Full Text: DOI
Steurer, Walter; Deloudi, Sofia Fascinating quasicrystals. (English) Zbl 1370.82128 Acta Crystallogr., Sect. A 64, No. 1, 1-11 (2008). MSC: 82D25 52C23 82-02 PDFBibTeX XMLCite \textit{W. Steurer} and \textit{S. Deloudi}, Acta Crystallogr., Sect. A 64, No. 1, 1--11 (2008; Zbl 1370.82128) Full Text: DOI
Arora, Sanjeev; Khot, Subrash A.; Kolla, Alexandra; Steurer, David; Yulsiani, Madhur; Vishnoi, Nisheeth K. Unique games on expanding constraint graphs are easy (extended abstract). (English) Zbl 1231.68147 STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 21-28 (2008). MSC: 68Q25 05C57 05C85 68R10 PDFBibTeX XMLCite \textit{S. Arora} et al., in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 21--28 (2008; Zbl 1231.68147)
Bläser, Markus; Hardt, Moritz; Steurer, David Asymptotically optimal hitting sets against polynomials. (English) Zbl 1153.68569 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 345-356 (2008). MSC: 68W30 PDFBibTeX XMLCite \textit{M. Bläser} et al., Lect. Notes Comput. Sci. 5125, 345--356 (2008; Zbl 1153.68569) Full Text: DOI
Doerr, Benjamin; Lengler, Johannes; Steurer, David The interval liar game. (English) Zbl 1332.68005 Hliněný, Petr (ed.) et al., 6th Czech-Slovak international symposium on combinatorics, graph theory, algorithms and applications, DIMATIA Center, Charles University, Prague, Czech Republic, July 10–16, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 28, 425-432 (2007). MSC: 68M10 68M12 68M15 68Q25 90B18 91A05 91A28 91A80 PDFBibTeX XMLCite \textit{B. Doerr} et al., Electron. Notes Discrete Math. 28, 425--432 (2007; Zbl 1332.68005) Full Text: DOI
Doerr, Benjamin; Lengler, Johannes; Steurer, David The interval liar game. (English) Zbl 1135.68314 Asano, Tetsuo (ed.), Algorithms and computation. 17th international symposium, ISAAC 2006, Kolkata, India, December 18–20, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49694-6/pbk). Lecture Notes in Computer Science 4288, 318-327 (2006). MSC: 68M10 68M12 68M15 68Q25 90B18 91A05 91A28 91A80 PDFBibTeX XMLCite \textit{B. Doerr} et al., Lect. Notes Comput. Sci. 4288, 318--327 (2006; Zbl 1135.68314) Full Text: DOI
Sanders, Peter; Steurer, David An asymptotic approximation scheme for multigraph edge coloring. (English) Zbl 1297.05091 Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 897-906 (2005). MSC: 05C15 05C85 PDFBibTeX XMLCite \textit{P. Sanders} and \textit{D. Steurer}, in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 897--906 (2005; Zbl 1297.05091)