- 2020
- Nima Anari
, Vijay V. Vazirani:
Planar Graph Perfect Matching Is in NC. J. ACM 67(4): 21:1-21:34 (2020) - Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, Yaniv Plan:
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes. J. ACM 67(6): 32:1-32:42 (2020) - Albert Atserias, Moritz Müller:
Automating Resolution is NP-Hard. J. ACM 67(5): 31:1-31:17 (2020) - Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg:
A Simple and Approximately Optimal Mechanism for an Additive Buyer. J. ACM 67(4): 24:1-24:40 (2020) - Laasya Bangalore, Ashish Choudhury, Arpita Patra:
The Power of Shunning: Efficient Asynchronous Byzantine Agreement Revisited. J. ACM 67(3): 14:1-14:59 (2020) - Pablo Barceló, Diego Figueira, Georg Gottlob, Andreas Pieris:
Semantic Optimization of Conjunctive Queries. J. ACM 67(6): 34:1-34:60 (2020) - Olaf Beyersdorff, Ilario Bonacina, Leroy Chew, Ján Pich:
Frege Systems for Quantified Boolean Logic. J. ACM 67(2): 9:1-9:36 (2020) - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. J. ACM 67(2): 8:1-8:28 (2020) - Guy E. Blelloch, Yan Gu, Julian Shun, Yihan Sun:
Parallelism in Randomized Incremental Algorithms. J. ACM 67(5): 27:1-27:27 (2020) - Ran Canetti:
Universally Composable Security. J. ACM 67(5): 28:1-28:94 (2020) - Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67(6): 36:1-36:22 (2020) - Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif:
The Log-Approximate-Rank Conjecture Is False. J. ACM 67(4): 23:1-23:28 (2020) - Jeroen Chua, Pedro F. Felzenszwalb:
Scene Grammars, Factor Graphs, and Belief Propagation. J. ACM 67(4): 19:1-19:41 (2020) - Maria Chudnovsky, Alex Scott, Paul D. Seymour, Sophie Spirkl:
Detecting an Odd Hole. J. ACM 67(1): 5:1-5:12 (2020) - Paolo Ciaccia, Davide Martinenghi, Riccardo Torlone:
Foundations of Context-aware Preference Propagation. J. ACM 67(1): 4:1-4:43 (2020) - Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan:
Oracle-efficient Online Learning and Auction Design. J. ACM 67(5): 26:1-26:57 (2020) - Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood:
Planar Graphs Have Bounded Queue-Number. J. ACM 67(4): 22:1-22:38 (2020) - Michael Elkin:
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. J. ACM 67(2): 13:1-13:15 (2020) - Michael Elkin:
Distributed Exact Shortest Paths in Sublinear Time. J. ACM 67(3): 15:1-15:36 (2020) - Yuval Emek, Shay Kutten, Ron Lavi, Yangguang Shi:
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency. J. ACM 67(1): 7:1-7:33 (2020) - Javier Esparza, Jan Kretínský, Salomon Sickert:
A Unified Translation of Linear Temporal Logic to ω-Automata. J. ACM 67(6): 33:1-33:61 (2020) - Travis Gagie, Gonzalo Navarro, Nicola Prezza:
Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space. J. ACM 67(1): 2:1-2:54 (2020) - Daniel Gaina:
Forcing and Calculi for Hybrid Logics. J. ACM 67(4): 25:1-25:55 (2020) - Michel X. Goemans, Thomas Rothvoss:
Polynomiality for Bin Packing with a Constant Number of Item Types. J. ACM 67(6): 38:1-38:21 (2020) - Guy Goren, Yoram Moses:
Silence. J. ACM 67(1): 3:1-3:26 (2020) - Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu:
Fully Online Matching. J. ACM 67(3): 17:1-17:25 (2020) - Elaye Karstadt, Oded Schwartz:
Matrix Multiplication, a Little Faster. J. ACM 67(1): 1:1-1:31 (2020) - Dariusz R. Kowalski, Miguel A. Mosteiro:
Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. J. ACM 67(2): 11:1-11:17 (2020) - Stefan Kratsch, Magnus Wahlström:
Representative Sets and Irrelevant Vertices: New Tools for Kernelization. J. ACM 67(3): 16:1-16:50 (2020) - Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, Martin Tancer:
Embeddability in R3 is NP-hard. J. ACM 67(4): 20:1-20:29 (2020)
