default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 49
Volume 49, Number 1, 2020
- Monika Henzinger
, Satish Rao, Di Wang:
Local Flow Partitioning for Faster Edge Connectivity. 1-36 - Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Clifford Stein:
Hallucination Helps: Energy Efficient Virtual Circuit Routing. 37-66 - Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Approximate Modularity Revisited. 67-97 - Christoph Berkholz, Jakob Nordström:
Supercritical Space-Width Trade-offs for Resolution. 98-118 - Emanuele Viola:
Sampling Lower Bounds: Boolean Average-Case and Permutations. 119-137 - Jesús A. De Loera, Jamie Haddock, Luis Rademacher:
The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential. 138-169 - Stasys Jukna, Hannes Seiwert:
Approximation Limitations of Pure Dynamic Programming. 170-205 - Benjamin Plaut, Tim Roughgarden:
Communication Complexity of Discrete Fair Division. 206-243
Volume 49, Number 2, 2020
- Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous:
Zero-Knowledge Proof Systems for QMA. 245-283 - Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, Hengjia Wei:
Robust Positioning Patterns with Low Redundancy. 284-317 - Rajesh Hemant Chitnis, Andreas Emil Feldmann, Mohammad Taghi Hajiaghayi, Dániel Marx:
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). 318-364 - Libor Barto, Michael Pinsker:
Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems). 365-393 - Nicholas J. A. Harvey, Jan Vondrák:
An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles. 394-428 - Arnold Filtser, Shay Solomon:
The Greedy Spanner Is Existentially Optimal. 429-447 - Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein:
Finding Cliques in Social Networks: A New Distribution-Free Model. 448-464
Volume 49, Number 3, 2020
- Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson:
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. 465-496 - Yi-Jun Chang, Wenzheng Li, Seth Pettie:
Distributed (Δ+1)-Coloring via Ultrafast Graph Shattering. 497-539 - Paul Dütting, Michal Feldman, Thomas Kesselheim, Brendan Lucier:
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs. 540-582 - Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
On Locality-Sensitive Orderings and Their Applications. 583-600 - Dan Feldman, Melanie Schmidt, Christian Sohler:
Turning Big Data Into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering. 601-657 - Sungjin Im, Benjamin Moseley:
Fair Scheduling via Iterative Quasi-Uniform Sampling. 658-680
Volume 49, Number 4, 2020
- Matthew Jenssen, Peter Keevash, Will Perkins:
Algorithms for #BIS-Hard Problems on Expander Graphs. 681-710 - David G. Harris:
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. 711-746 - Talya Eden, Dana Ron, C. Seshadhri:
On Approximating the Number of k-Cliques in Sublinear Time. 747-771 - Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. 772-810 - William M. Hoza, David Zuckerman:
Simple Optimal Hitting Sets for Small-Success RL. 811-820 - Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Find Your Place: Simple Distributed Algorithms for Community Detection. 821-864
- Valentine Kabanets, Sofya Raskhodnikova, Chaitanya Swamy:
Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017). - Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On the Power of Statistical Zero Knowledge. - Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. - Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward:
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. - Brett Hemenway, Noga Ron-Zewi, Mary Wootters:
Local List Recovery of High-Rate Tensor Codes and Applications. - Huijia Lin, Rafael Pass, Pratik Soni:
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles. - Rasmus Kyng, Peng Zhang:
Hardness Results for Structured Linear Systems. - David Durfee, John Peebles, Richard Peng, Anup B. Rao:
Determinant-Preserving Sparsification of SDDM Matrices. - Shi Li:
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. - Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP.
Volume 49, Number 5, 2020
- Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis:
Strong Connectivity in Directed Graphs under Failures, with Applications. 865-926 - Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, Tao Xiao:
Tight Revenue Gaps Among Simple Mechanisms. 927-958 - Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization without Slowdown. 959-998 - Eshan Chattopadhyay, Vipul Goyal, Xin Li:
Nonmalleable Extractors and Codes, with Their Many Tampered Extensions. 999-1040
- Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas:
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018). - Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski:
Round Compression for Parallel Matching Algorithms. - László Kozma, Thatchaphol Saranurak:
Smooth Heaps and a Dual View of Self-Adjusting Data Structures. - Rishab Goyal, Venkata Koppula, Brent Waters:
Collusion Resistant Traitor Tracing from Learning with Errors. - Mark Braverman, Gil Cohen, Sumegha Garg:
Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. - Cody D. Murray, R. Ryan Williams:
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma. - Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. - Scott Aaronson:
Shadow Tomography of Quantum States. - Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic:
Inapproximability of the Independent Set Polynomial in the Complex Plane. - Daniel Dadush, Sophie Huiberts:
A Friendly Smoothed Analysis of the Simplex Method. - Jeremy T. Fineman:
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability.
Volume 49, Number 6, 2020
- Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak:
Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols. 1041-1082 - Klaus Jansen, Lars Rohwedder:
A Quasi-Polynomial Approximation for the Restricted Assignment Problem. 1083-1108 - Boris Aronov, Esther Ezra, Joshua Zahl:
Constructive Polynomial Partitioning for Algebraic Curves in ℝ3 with Applications. 1109-1127 - Pavel Hubácek, Eylon Yogev:
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. 1128-1172 - Alexander A. Sherstov:
Algorithmic Polynomials. 1173-1231 - Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. 1232-1248 - Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi:
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. 1249-1270 - Boris Aronov, Gali Bar-On, Matthew J. Katz:
Resolving SINR Queries in a Dynamic Setting. 1271-1290 - Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs. 1291-1331 - Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, Barbara M. Terhal:
Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians. 1332-1362 - Ran Duan, Seth Pettie:
Connectivity Oracles for Graphs Subject to Vertex Failures. 1363-1396 - Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos:
Bidimensionality and Kernels. 1397-1422 - Thomas Vidick:
Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate. 1423-1427
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-01-29 02:09 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
