Madelaine, Florent R.; Martin, Barnaby D. On the complexity of the model checking problem. (English) Zbl 1393.68078 SIAM J. Comput. 47, No. 3, 769-797 (2018). MSC: 68Q25 03B70 06A15 08A70 68Q60 PDF BibTeX XML Cite \textit{F. R. Madelaine} and \textit{B. D. Martin}, SIAM J. Comput. 47, No. 3, 769--797 (2018; Zbl 1393.68078) Full Text: DOI arXiv Link OpenURL
David, Roee; Feige, Uriel Random walks with the minimum degree local rule have \(O(n^2)\) cover time. (English) Zbl 1391.05233 SIAM J. Comput. 47, No. 3, 755-768 (2018). MSC: 05C81 60J10 05C22 05C05 PDF BibTeX XML Cite \textit{R. David} and \textit{U. Feige}, SIAM J. Comput. 47, No. 3, 755--768 (2018; Zbl 1391.05233) Full Text: DOI OpenURL
Cousins, Ben; Vempala, Santosh Gaussian cooling and \(O^\ast(n^3)\) algorithms for volume and Gaussian volume. (English) Zbl 1397.68217 SIAM J. Comput. 47, No. 3, 1237-1273 (2018). MSC: 68W20 52A38 65C40 68Q25 PDF BibTeX XML Cite \textit{B. Cousins} and \textit{S. Vempala}, SIAM J. Comput. 47, No. 3, 1237--1273 (2018; Zbl 1397.68217) Full Text: DOI OpenURL
Cole, Richard; Gkatzelis, Vasilis Approximating the Nash social welfare with indivisible items. (English) Zbl 1397.91302 SIAM J. Comput. 47, No. 3, 1211-1236 (2018). MSC: 91B32 68W25 90C27 PDF BibTeX XML Cite \textit{R. Cole} and \textit{V. Gkatzelis}, SIAM J. Comput. 47, No. 3, 1211--1236 (2018; Zbl 1397.91302) Full Text: DOI OpenURL
Bitansky, Nir; Canetti, Ran; Garg, Sanjam; Holmgren, Justin; Jain, Abhishek; Lin, Huijia; Pass, Rafael; Telang, Sidharth; Vaikuntanathan, Vinod Indistinguishability obfuscation for RAM programs and succinct randomized encodings. (English) Zbl 1396.68041 SIAM J. Comput. 47, No. 3, 1123-1210 (2018). MSC: 68P25 68Q10 68W20 PDF BibTeX XML Cite \textit{N. Bitansky} et al., SIAM J. Comput. 47, No. 3, 1123--1210 (2018; Zbl 1396.68041) Full Text: DOI OpenURL
Abboud, Amir; Vassilevska Williams, Virginia; Yu, Huacheng Matching triangles and basing hardness on an extremely popular conjecture. (English) Zbl 1396.68052 SIAM J. Comput. 47, No. 3, 1098-1122 (2018). MSC: 68Q25 05C21 68Q17 PDF BibTeX XML Cite \textit{A. Abboud} et al., SIAM J. Comput. 47, No. 3, 1098--1122 (2018; Zbl 1396.68052) Full Text: DOI OpenURL
Backurs, Arturs; Indyk, Piotr Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). (English) Zbl 1396.68137 SIAM J. Comput. 47, No. 3, 1087-1097 (2018). MSC: 68W32 68Q17 68Q25 PDF BibTeX XML Cite \textit{A. Backurs} and \textit{P. Indyk}, SIAM J. Comput. 47, No. 3, 1087--1097 (2018; Zbl 1396.68137) Full Text: DOI OpenURL
Korula, Nitish; Mirrokni, Vahab; Zadimoghaddam, Morteza Online submodular welfare maximization: greedy beats 1/2 in random order. (English) Zbl 1397.91265 SIAM J. Comput. 47, No. 3, 1056-1086 (2018). MSC: 91B26 68W27 90C27 PDF BibTeX XML Cite \textit{N. Korula} et al., SIAM J. Comput. 47, No. 3, 1056--1086 (2018; Zbl 1397.91265) Full Text: DOI arXiv OpenURL
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru On the Lovász theta function for independent sets in sparse graphs. (English) Zbl 1397.05124 SIAM J. Comput. 47, No. 3, 1039-1055 (2018). MSC: 05C69 05C55 05C85 68Q25 68W25 90C22 PDF BibTeX XML Cite \textit{N. Bansal} et al., SIAM J. Comput. 47, No. 3, 1039--1055 (2018; Zbl 1397.05124) Full Text: DOI OpenURL
Aaronson, Scott; Ambainis, Andris Forrelation: a problem that optimally separates quantum from classical computing. (English) Zbl 1396.68047 SIAM J. Comput. 47, No. 3, 982-1038 (2018). MSC: 68Q12 81P68 PDF BibTeX XML Cite \textit{S. Aaronson} and \textit{A. Ambainis}, SIAM J. Comput. 47, No. 3, 982--1038 (2018; Zbl 1396.68047) Full Text: DOI arXiv OpenURL
Barman, Siddharth Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem. (English) Zbl 1416.91016 SIAM J. Comput. 47, No. 3, 960-981 (2018). MSC: 91A10 91-04 68W25 68Q25 91A05 52C99 PDF BibTeX XML Cite \textit{S. Barman}, SIAM J. Comput. 47, No. 3, 960--981 (2018; Zbl 1416.91016) Full Text: DOI OpenURL
Rubinstein, Aviad Inapproximability of Nash equilibrium. (English) Zbl 1396.68060 SIAM J. Comput. 47, No. 3, 917-959 (2018). MSC: 68Q25 68W25 91A10 91B52 PDF BibTeX XML Cite \textit{A. Rubinstein}, SIAM J. Comput. 47, No. 3, 917--959 (2018; Zbl 1396.68060) Full Text: DOI OpenURL
Andoni, Alexandr; Krauthgamer, Robert; Razenshteyn, Ilya Sketching and embedding are equivalent for norms. (English) Zbl 1406.46015 SIAM J. Comput. 47, No. 3, 890-916 (2018). Reviewer: Mikhail Ostrovskii (Queens) MSC: 46B85 68P05 30L05 68W20 68W25 PDF BibTeX XML Cite \textit{A. Andoni} et al., SIAM J. Comput. 47, No. 3, 890--916 (2018; Zbl 1406.46015) Full Text: DOI OpenURL
Daskalakis, Costis (ed.); Kalai, Yael (ed.); Irani, Sandy (ed.) Special section on the forty-seventh annual ACM symposium on theory of computing (STOC 2015). (English) Zbl 1390.00142 SIAM J. Comput. 47, No. 3, 888-889 (2018). MSC: 00B25 68-06 PDF BibTeX XML Cite \textit{C. Daskalakis} (ed.) et al., SIAM J. Comput. 47, No. 3, 888--889 (2018; Zbl 1390.00142) Full Text: DOI OpenURL
Bhattacharya, Sayan; Henzinger, Monika; Italiano, Giuseppe F. Deterministic fully dynamic data structures for vertex cover and matching. (English) Zbl 1390.05221 SIAM J. Comput. 47, No. 3, 859-887 (2018). MSC: 05C85 05C70 68P05 PDF BibTeX XML Cite \textit{S. Bhattacharya} et al., SIAM J. Comput. 47, No. 3, 859--887 (2018; Zbl 1390.05221) Full Text: DOI arXiv OpenURL
Elkin, Michael; Filtser, Arnold; Neiman, Ofer Prioritized metric structures and embedding. (English) Zbl 1396.68038 SIAM J. Comput. 47, No. 3, 829-858 (2018). MSC: 68P05 05C22 68U05 PDF BibTeX XML Cite \textit{M. Elkin} et al., SIAM J. Comput. 47, No. 3, 829--858 (2018; Zbl 1396.68038) Full Text: DOI arXiv OpenURL
Lin, Jiabao; Wang, Hanpin The complexity of Boolean Holant problems with nonnegative weights. (English) Zbl 1397.68105 SIAM J. Comput. 47, No. 3, 798-828 (2018). MSC: 68Q25 68Q17 PDF BibTeX XML Cite \textit{J. Lin} and \textit{H. Wang}, SIAM J. Comput. 47, No. 3, 798--828 (2018; Zbl 1397.68105) Full Text: DOI OpenURL
Balcan, Maria-Florina; Harvey, Nicholas J. A. Submodular functions: learnability, structure, and optimization. (English) Zbl 1395.68228 SIAM J. Comput. 47, No. 3, 703-754 (2018). MSC: 68T05 05B35 90C27 91A26 PDF BibTeX XML Cite \textit{M.-F. Balcan} and \textit{N. J. A. Harvey}, SIAM J. Comput. 47, No. 3, 703--754 (2018; Zbl 1395.68228) Full Text: DOI arXiv OpenURL
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket Slightly superexponential parameterized problems. (English) Zbl 1393.68077 SIAM J. Comput. 47, No. 3, 675-702 (2018). MSC: 68Q25 05C85 68Q17 68W32 68W40 PDF BibTeX XML Cite \textit{D. Lokshtanov} et al., SIAM J. Comput. 47, No. 3, 675--702 (2018; Zbl 1393.68077) Full Text: DOI arXiv OpenURL
Huang, Zhiyi; Mansour, Yishay; Roughgarden, Tim Making the most of your samples. (English) Zbl 1390.91146 SIAM J. Comput. 47, No. 3, 651-674 (2018). MSC: 91B26 68Q25 PDF BibTeX XML Cite \textit{Z. Huang} et al., SIAM J. Comput. 47, No. 3, 651--674 (2018; Zbl 1390.91146) Full Text: DOI arXiv OpenURL
Baswana, Surender; Gupta, Manoj; Sen, Sandeep Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version). (English) Zbl 1387.05188 SIAM J. Comput. 47, No. 3, 617-650 (2018). MSC: 05C70 05C85 68W05 68W20 68W40 PDF BibTeX XML Cite \textit{S. Baswana} et al., SIAM J. Comput. 47, No. 3, 617--650 (2018; Zbl 1387.05188) Full Text: DOI OpenURL