Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri ETH hardness for densest-\(k\)-subgraph with perfect completeness. (English) Zbl 1409.68125 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1326-1341 (2017). MSC: 68Q17 05C42 05C69 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Braverman} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1326--1341 (2017; Zbl 1409.68125) Full Text: DOI arXiv
Braverman, Mark; Garg, Sumegha; Schvartzman, Ariel Coding in undirected graphs is either very helpful or not helpful at all. (English) Zbl 1402.90030 Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 18, 18 p. (2017). MSC: 90B18 05C21 05C76 94A29 PDFBibTeX XMLCite \textit{M. Braverman} et al., LIPIcs -- Leibniz Int. Proc. Inform. 67, Article 18, 18 p. (2017; Zbl 1402.90030) Full Text: DOI arXiv
Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin Fractional pebbling and thrifty branching programs. (English) Zbl 1248.68200 Kannan, Ravi (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2009), December 15–17, 2009, Kanpur, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-13-2). LIPIcs – Leibniz International Proceedings in Informatics 4, 109-120, electronic only (2009). MSC: 68Q15 68R10 68Q17 05C05 PDFBibTeX XMLCite \textit{M. Braverman} et al., LIPIcs -- Leibniz Int. Proc. Inform. 4, 109--120 (2009; Zbl 1248.68200) Full Text: DOI Link
Braverman, Mark; Kulkarni, Raghav; Roy, Sambuddha Space-efficient counting in graphs on surfaces. (English) Zbl 1205.05215 Comput. Complexity 18, No. 4, 601-649 (2009). MSC: 05C85 05C30 57M15 68R10 PDFBibTeX XMLCite \textit{M. Braverman} et al., Comput. Complexity 18, No. 4, 601--649 (2009; Zbl 1205.05215) Full Text: DOI
Braverman, Mark; Mossel, Elchanan Noisy sorting without resampling. (English) Zbl 1192.94077 Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 268-276 (2008). MSC: 94A20 68P10 05A05 PDFBibTeX XMLCite \textit{M. Braverman} and \textit{E. Mossel}, in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 268--276 (2008; Zbl 1192.94077) Full Text: Link