- 2018
- Lin Chen
, Nicole Megow, Kevin Schewior:
An O(log m)-Competitive Algorithm for Online Machine Minimization. SIAM J. Comput. 47(6): 2057-2077 (2018) - Scott Aaronson, Andris Ambainis:
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. 47(3): 982-1038 (2018) - Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47(6): 2203-2236 (2018) - Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. SIAM J. Comput. 47(6): 2527-2555 (2018) - Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. SIAM J. Comput. 47(3): 1098-1122 (2018) - Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett:
Non-Malleable Codes from Additive Combinatorics. SIAM J. Comput. 47(2): 524-546 (2018) - Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. SIAM J. Comput. 47(4): 1339-1372 (2018) - Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn:
Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. 47(3): 890-916 (2018) - Benny Applebaum, Shachar Lovett:
Algebraic Attacks against Random Local Functions and Their Countermeasures. SIAM J. Comput. 47(1): 52-79 (2018) - Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Approximate Polytope Membership Queries. SIAM J. Comput. 47(1): 1-51 (2018) - Arturs Backurs, Piotr Indyk:
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM J. Comput. 47(3): 1087-1097 (2018) - Maria-Florina Balcan, Nicholas J. A. Harvey:
Submodular Functions: Learnability, Structure, and Optimization. SIAM J. Comput. 47(3): 703-754 (2018) - Nikhil Bansal, Anupam Gupta, Guru Guruganesh:
On the Lovász Theta Function for Independent Sets in Sparse Graphs. SIAM J. Comput. 47(3): 1039-1055 (2018) - Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas:
Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. SIAM J. Comput. 47(5): 1755-1777 (2018) - Siddharth Barman:
Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem. SIAM J. Comput. 47(3): 960-981 (2018) - Surender Baswana, Keerti Choudhary, Liam Roditty:
Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal. SIAM J. Comput. 47(1): 80-95 (2018) - Surender Baswana, Manoj Gupta, Sandeep Sen:
Fully Dynamic Maximal Matching in O(log n) Update Time (Corrected Version). SIAM J. Comput. 47(3): 617-650 (2018) - Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, Vahid Liaghat:
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems. SIAM J. Comput. 47(4): 1275-1293 (2018) - Mikhail Belkin, Luis Rademacher, James R. Voss:
Eigenvectors of Orthogonally Decomposable Functions. SIAM J. Comput. 47(2): 547-615 (2018) - Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young:
Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. SIAM J. Comput. 47(5): 1735-1754 (2018) - Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano:
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. SIAM J. Comput. 47(3): 859-887 (2018) - Nir Bitansky, Ran Canetti, Sanjam Garg, Justin Holmgren, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang, Vinod Vaikuntanathan:
Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings. SIAM J. Comput. 47(3): 1123-1210 (2018) - Nicolas Bousquet, Jean Daligault, Stéphan Thomassé:
Multicut Is FPT. SIAM J. Comput. 47(1): 166-207 (2018) - Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette:
Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness. SIAM J. Comput. 47(6): 2277-2314 (2018) - Niv Buchbinder, Joseph (Seffi) Naor, Roy Schwartz:
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem. SIAM J. Comput. 47(4): 1463-1482 (2018) - Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting Codes and the Price of Approximate Differential Privacy. SIAM J. Comput. 47(5): 1888-1938 (2018) - Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld:
Sampling Correctors. SIAM J. Comput. 47(4): 1373-1423 (2018) - Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. SIAM J. Comput. 47(4): 1505-1528 (2018) - T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao:
Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming. SIAM J. Comput. 47(4): 1529-1546 (2018) - T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang:
A PTAS for the Steiner Forest Problem in Doubling Metrics. SIAM J. Comput. 47(4): 1705-1734 (2018)
