×

Found 27 Documents (Results 1–27)

Computational thresholds for the fixed-magnetization Ising model. (English) Zbl 07774430

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1459-1472 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lower bounds for max-cut via semidefinite programming. (English) Zbl 07600797

Kohayakawa, Yoshiharu (ed.) et al., Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12118, 479-490 (2020).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Statistical physics approaches to unique games. (English) Zbl 07561741

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 13, 27 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Spectral aspects of symmetric matrix signings. (English) Zbl 1507.68225

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 81, 13 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Optimal lower bounds for sketching graph cuts. (English) Zbl 1432.68343

Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2565-2569 (2019).
MSC:  68R10 68P05 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Spectrally robust graph isomorphism. (English) Zbl 1499.68280

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 84, 13 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the expansion of group-based lifts. (English) Zbl 1470.05097

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 24, 13 p. (2017).
MSC:  05C48 05C50
PDFBibTeX XMLCite
Full Text: DOI

Approximation of non-Boolean 2CSP. (English) Zbl 1410.68171

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1705-1714 (2016).
MSC:  68Q25 68W25 90C22
PDFBibTeX XMLCite
Full Text: DOI arXiv

How to play unique games against a semi-random adversary: study of semi-random models of unique games. (English) Zbl 1292.68114

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). 443-452 (2011).
MSC:  68Q87 91A40 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Subgraph sparsification and nearly optimal ultrasparsifiers. (English) Zbl 1293.05370

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). 57-66 (2010).
MSC:  05C85 68W25 68W40
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

Making classical honest verifier zero knowledge protocols secure against quantum attacks. (English) Zbl 1155.94370

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 592-603 (2008).
MSC:  94A60 81P68
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Database

all top 5

Year of Publication

all top 3

Main Field

Software