- Timothy M. Chan, Yakov Nekrich
:
Towards an Optimal Method for Dynamic Planar Point Location. SIAM J. Comput. 47(6): 2337-2361 (2018) - Chandra Chekuri, Chao Xu:
Minimum Cuts and Sparsification in Hypergraphs. SIAM J. Comput. 47(6): 2118-2156 (2018) - Chandra Chekuri, Anastasios Sidiropoulos:
Approximation Algorithms for Euler Genus and Related Problems. SIAM J. Comput. 47(4): 1610-1643 (2018) - Aloni Cohen, Justin Holmgren, Ryo Nishimaki
, Vinod Vaikuntanathan, Daniel Wichs:
Watermarking Cryptographic Capabilities. SIAM J. Comput. 47(6): 2157-2202 (2018) - Richard Cole, Vasilis Gkatzelis:
Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput. 47(3): 1211-1236 (2018) - Ben Cousins, Santosh S. Vempala:
Gaussian Cooling and O*(n3) Algorithms for Volume and Gaussian Volume. SIAM J. Comput. 47(3): 1237-1273 (2018) - Artur Czumaj, Peter Davies
:
Deterministic Communication in Radio Networks. SIAM J. Comput. 47(1): 218-240 (2018) - Amit Daniely, Michael Schapira, Gal Shahaf:
Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik-Chervonenkis Dimension. SIAM J. Comput. 47(1): 96-120 (2018) - Costis Daskalakis, Yael Kalai, Sandy Irani:
Special Section on the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015). SIAM J. Comput. 47(3): 888-889 (2018) - Roee David, Uriel Feige:
Random Walks with the Minimum Degree Local Rule Have O(n2) Cover Time. SIAM J. Comput. 47(3): 755-768 (2018) - Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
:
Erasure-Resilient Property Testing. SIAM J. Comput. 47(2): 295-329 (2018) - Michael Elkin, Arnold Filtser
, Ofer Neiman:
Prioritized Metric Structures and Embedding. SIAM J. Comput. 47(3): 829-858 (2018) - Vitaly Feldman, Will Perkins
, Santosh S. Vempala:
On the Complexity of Random Satisfiability Problems with Planted Solutions. SIAM J. Comput. 47(4): 1294-1338 (2018) - Moran Feldman
, Rico Zenklusen:
The Submodular Secretary Problem Goes Linear. SIAM J. Comput. 47(2): 330-366 (2018) - Andreas Emil Feldmann
, Wai Shing Fung, Jochen Könemann, Ian Post:
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM J. Comput. 47(4): 1667-1704 (2018) - Venkata Gandikota
, Badih Ghazi, Elena Grigorescu:
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. SIAM J. Comput. 47(4): 1547-1584 (2018) - Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir:
Near-Optimal Distributed Maximum Flow. SIAM J. Comput. 47(6): 2078-2117 (2018) - Yiannis Giannakopoulos
, Elias Koutsoupias:
Duality and Optimality of Auctions for Uniform Distributions. SIAM J. Comput. 47(1): 121-165 (2018) - Wojciech M. Golab, Xiaozhou (Steve) Li, Alejandro López-Ortiz, Naomi Nishimura:
Computing k-Atomicity in Polynomial Time. SIAM J. Comput. 47(2): 420-455 (2018) - Mika Göös, Rahul Jain
, Thomas Watson:
Extension Complexity of Independent Set Polytopes. SIAM J. Comput. 47(1): 241-269 (2018) - Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. SIAM J. Comput. 47(6): 2435-2450 (2018) - Mika Göös, Toniann Pitassi:
Communication Lower Bounds via Critical Block Sensitivity. SIAM J. Comput. 47(5): 1778-1806 (2018) - Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the Discrete Fourier Transform. SIAM J. Comput. 47(6): 2451-2487 (2018) - Georg Gottlob, Enrico Malizia
:
Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic. SIAM J. Comput. 47(2): 456-492 (2018) - Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. SIAM J. Comput. 47(2): 493-523 (2018) - Hamed Hatami, Kaave Hosseini
, Shachar Lovett
:
Structure of Protocols for XOR Functions. SIAM J. Comput. 47(1): 208-217 (2018) - Zhiyi Huang
, Yishay Mansour, Tim Roughgarden:
Making the Most of Your Samples. SIAM J. Comput. 47(3): 651-674 (2018) - Haim Kaplan, Wolfgang Mulzer
, Liam Roditty, Paul Seiferth:
Spanners for Directed Transmission Graphs. SIAM J. Comput. 47(4): 1585-1609 (2018) - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs. SIAM J. Comput. 47(4): 1483-1504 (2018) - Thomas Kesselheim, Klaus Radke, Andreas Tönnis
, Berthold Vöcking:
Primal Beats Dual on Online Packing LPs in the Random-Order Model. SIAM J. Comput. 47(5): 1939-1964 (2018)