Boyle, Elette (ed.); Cohen-Addad, Vincent (ed.); Kolla, Alexandra (ed.); Thorup, Mikkel (ed.) Special section on the fifty-ninth annual IEEE symposium on foundations of computer science (2018). (English) Zbl 1525.00033 SIAM J. Comput. 52, No. 6, FOCS18-i (2023). MSC: 00B25 68-06 PDFBibTeX XMLCite \textit{E. Boyle} (ed.) et al., SIAM J. Comput. 52, No. 6, FOCS18-i (2023; Zbl 1525.00033) Full Text: DOI
Carlson, Charlie; Davies, Ewan; Kolla, Alexandra; Potukuchi, Aditya Approximately counting independent sets in dense bipartite graphs via subspace enumeration. arXiv:2307.09533 Preprint, arXiv:2307.09533 [cs.DS] (2023). MSC: 68W25 BibTeX Cite \textit{C. Carlson} et al., ``Approximately counting independent sets in dense bipartite graphs via subspace enumeration'', Preprint, arXiv:2307.09533 [cs.DS] (2023) Full Text: arXiv OA License
Carlson, Charlie; Davies, Ewan; Kolla, Alexandra; Perkins, Will 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 \textit{C. Carlson} et al., in: 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; Zbl 07774430) Full Text: DOI arXiv
Carlson, Charlie; Davies, Ewan; Fraiman, Nicolas; Kolla, Alexandra; Potukuchi, Aditya; Yap, Corrine Algorithms for the ferromagnetic Potts model on expanders. arXiv:2204.01923 Preprint, arXiv:2204.01923 [cs.DS] (2022). BibTeX Cite \textit{C. Carlson} et al., ``Algorithms for the ferromagnetic Potts model on expanders'', Preprint, arXiv:2204.01923 [cs.DS] (2022) Full Text: arXiv OA License
Greenblatt, Jordan; Kolla, Alexandra; Krause, Ben Dimension-free \(L^p\)-maximal inequalities for spherical means in \(\mathbb{Z}_{m+1}^N\). (English) Zbl 1478.42017 Int. Math. Res. Not. 2021, No. 9, 6586-6620 (2021). MSC: 42B25 42A85 43A07 22D40 28D15 PDFBibTeX XMLCite \textit{J. Greenblatt} et al., Int. Math. Res. Not. 2021, No. 9, 6586--6620 (2021; Zbl 1478.42017) Full Text: DOI
Carlson, Charles; Kolla, Alexandra; Li, Ray; Mani, Nitya; Sudakov, Benny; Trevisan, Luca Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming. (English) Zbl 1475.05094 SIAM J. Discrete Math. 35, No. 3, 1557-1568 (2021). Reviewer: I. M. Erusalimskiy (Rostow-na-Donu) MSC: 05C35 90C22 PDFBibTeX XMLCite \textit{C. Carlson} et al., SIAM J. Discrete Math. 35, No. 3, 1557--1568 (2021; Zbl 1475.05094) Full Text: DOI arXiv
Carlson, Charles; Kolla, Alexandra; Li, Ray; Mani, Nitya; Sudakov, Benny; Trevisan, Luca 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 \textit{C. Carlson} et al., Lect. Notes Comput. Sci. 12118, 479--490 (2020; Zbl 07600797) Full Text: DOI
Coulson, Matthew; Davies, Ewan; Kolla, Alexandra; Patel, Viresh; Regts, Guus 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 \textit{M. Coulson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 13, 27 p. (2020; Zbl 07561741) Full Text: DOI arXiv
Carlson, Charles; Chandrasekaran, Karthekeyan; Chang, Hsien-Chih; Kakimura, Naonori; Kolla, Alexandra Spectral aspects of symmetric matrix signings. (English) Zbl 1506.68068 Discrete Optim. 37, Article ID 100582, 21 p. (2020). MSC: 68R10 05C22 05C50 05C70 05C85 68Q17 PDFBibTeX XMLCite \textit{C. Carlson} et al., Discrete Optim. 37, Article ID 100582, 21 p. (2020; Zbl 1506.68068) Full Text: DOI Link
Carlson, Charles; Davies, Ewan; Kolla, Alexandra Efficient algorithms for the Potts model on small-set expanders. arXiv:2003.01154 Preprint, arXiv:2003.01154 [cs.DS] (2020). BibTeX Cite \textit{C. Carlson} et al., ``Efficient algorithms for the Potts model on small-set expanders'', Preprint, arXiv:2003.01154 [cs.DS] (2020) Full Text: arXiv OA License
Carlson, Charles; Chandrasekaran, Karthekeyan; Chang, Hsien-Chih; Kakimura, Naonori; Kolla, Alexandra 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). MSC: 68R10 05C22 05C50 05C70 05C85 68Q17 PDFBibTeX XMLCite \textit{C. Carlson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 81, 13 p. (2019; Zbl 1507.68225) Full Text: DOI
Carlson, Charles; Kolla, Alexandra; Srivastava, Nikhil; Trevisan, Luca 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 \textit{C. Carlson} et al., in: 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; Zbl 1432.68343) Full Text: DOI arXiv
Agarwal, Naman; Chandrasekaran, Karthekeyan; Kolla, Alexandra; Madan, Vivek On the expansion of group-based lifts. (English) Zbl 1419.05119 SIAM J. Discrete Math. 33, No. 3, 1338-1373 (2019). MSC: 05C50 05C25 PDFBibTeX XMLCite \textit{N. Agarwal} et al., SIAM J. Discrete Math. 33, No. 3, 1338--1373 (2019; Zbl 1419.05119) Full Text: DOI arXiv
Kolla, Alexandra; Koutis, Ioannis; Madan, Vivek; Sinop, Ali Kemal 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). MSC: 68R10 05C50 05C60 68Q17 68W25 PDFBibTeX XMLCite \textit{A. Kolla} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 84, 13 p. (2018; Zbl 1499.68280) Full Text: DOI arXiv
Agarwal, Naman; Chandrasekaran, Karthekeyan; Kolla, Alexandra; Madan, Vivek 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 \textit{N. Agarwal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 24, 13 p. (2017; Zbl 1470.05097) Full Text: DOI
Kindler, Guy; Kolla, Alexandra; Trevisan, Luca 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 \textit{G. Kindler} et al., in: 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; Zbl 1410.68171) Full Text: DOI arXiv
Carlson, Charles; Chandrasekaran, Karthekeyan; Chang, Hsien-Chih; Kolla, Alexandra Invertibility and Largest Eigenvalue of Symmetric Matrix Signings. arXiv:1611.03624 Preprint, arXiv:1611.03624 [cs.DM] (2016). BibTeX Cite \textit{C. Carlson} et al., ``Invertibility and Largest Eigenvalue of Symmetric Matrix Signings'', Preprint, arXiv:1611.03624 [cs.DM] (2016) Full Text: arXiv OA License
Agarwal, Naman; Kindler, Guy; Kolla, Alexandra; Trevisan, Luca Unique games on the hypercube. (English) Zbl 1336.68092 Chic. J. Theor. Comput. Sci. 2015, Article No. 1, 20 p. (2015). MSC: 68Q17 05C57 90C22 PDFBibTeX XMLCite \textit{N. Agarwal} et al., Chic. J. Theor. Comput. Sci. 2015, Article No. 1, 20 p. (2015; Zbl 1336.68092) Full Text: DOI arXiv
Agarwal, Naman; Bandeira, Afonso S.; Koiliaris, Konstantinos; Kolla, Alexandra Multisection in the Stochastic Block Model using Semidefinite Programming. arXiv:1507.02323 Preprint, arXiv:1507.02323 [cs.DS] (2015). BibTeX Cite \textit{N. Agarwal} et al., ``Multisection in the Stochastic Block Model using Semidefinite Programming'', Preprint, arXiv:1507.02323 [cs.DS] (2015) Full Text: arXiv OA License
Harrow, Aram W.; Kolla, Alexandra; Schulman, Leonard J. Dimension-free \(L_2\) maximal inequality for spherical means in the hypercube. (English) Zbl 1298.42022 Theory Comput. 10, Paper No. 3, 55-75 (2014). MSC: 42B25 PDFBibTeX XMLCite \textit{A. W. Harrow} et al., Theory Comput. 10, Paper No. 3, 55--75 (2014; Zbl 1298.42022) Full Text: DOI arXiv
Greenblatt, Jordan; Kolla, Alexandra; Krause, Ben Dimension-Free \(L^p\)-Maximal Inequalities in \(\mathbb{Z}_{m+1}^N\). arXiv:1406.7229 Preprint, arXiv:1406.7229 [math.CA] (2014). BibTeX Cite \textit{J. Greenblatt} et al., ``Dimension-Free $L^p$-Maximal Inequalities in $\mathbb{Z}_{m+1}^N$'', Preprint, arXiv:1406.7229 [math.CA] (2014) Full Text: arXiv OA License
Kolla, Alexandra; Makarychev, Konstantin; Makarychev, Yury 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 \textit{A. Kolla} 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. 443--452 (2011; Zbl 1292.68114) Full Text: DOI
Kolla, Alexandra Spectral algorithms for unique games. (English) Zbl 1234.68120 Comput. Complexity 20, No. 2, 177-206 (2011). MSC: 68R10 68Q15 68W25 05C50 05C57 05C85 PDFBibTeX XMLCite \textit{A. Kolla}, Comput. Complexity 20, No. 2, 177--206 (2011; Zbl 1234.68120) Full Text: DOI arXiv
Kolla, Alexandra; Makarychev, Yury; Saberi, Amin; Teng, Shang-Hua 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 \textit{A. Kolla} 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). 57--66 (2010; Zbl 1293.05370) Full Text: DOI
Jain, Rahul; Kolla, Alexandra; Midrijanis, Gatis; Reichardt, Ben W. On parallel composition of zero-knowledge proofs with black-box quantum simulators. (English) Zbl 1170.81326 Quantum Inf. Comput. 9, No. 5-6, 513-532 (2009). MSC: 81P68 94B60 PDFBibTeX XMLCite \textit{R. Jain} et al., Quantum Inf. Comput. 9, No. 5--6, 513--532 (2009; Zbl 1170.81326) Full Text: arXiv
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)
Hallgren, Sean; Kolla, Alexandra; Sen, Pranab; Zhang, Shengyu 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 \textit{S. Hallgren} et al., Lect. Notes Comput. Sci. 5126, 592--603 (2008; Zbl 1155.94370) Full Text: DOI