×

Found 43 Documents (Results 1–43)

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI Link

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
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: Link

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: Link

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
Full Text: DOI Link

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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).
PDFBibTeX XMLCite

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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

Filter Results by …

Document Type

Database

all top 5

Year of Publication

all top 3

Main Field

Software