default search action
SIAM Journal on Computing, Volume 50
Volume 50, Number 1, 2021
- Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
:
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals. 1-31 - Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan:
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations. 32-67 - Benny Applebaum, Zvika Brakerski, Rotem Tsabary:
Perfect Secure Computation in Two Rounds. 68-97 - Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan:
Structure Versus Hardness Through the Obfuscation Lens. 98-144 - Hernán González-Aguilar, David Orden
Maximum Rectilinear Convex Subsets. 145-170 - Arkadev Chattopadhyay, Yuval Filmus
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. 171-210 - Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen:
The Complexity of Contracts. 211-254
Volume 50, Number 2, 2021
- Moran Feldman, Ola Svensson, Rico Zenklusen:
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems. 255-300 - Irit Dinur
List-Decoding with Double Samplers. 301-349 - Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin
Dynamic Sampling from Graphical Models. 350-381 - Rajesh Jayaram
Perfect Lp Sampling in a Data Stream. 382-439 - Harold N. Gabow, Piotr Sankowski:
Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors. 440-486 - Karolina Okrasa
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs. 487-508 - Pawel Gawrychowski
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time. 509-554 - Harold N. Gabow, Piotr Sankowski:
Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths. 555-601 - Haitao Wang
An O(nlog n)-Time Algorithm for the k-Center Problem in Trees. 602-635 - Rohit Gurjar
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. 636-661 - Greg Bodwin:
New Results on Linear Size Distance Preservers. 662-673 - Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang
The Communication Complexity of Set Intersection and Multiple Equality Testing. 674-717 - Magnús M. Halldórsson, Tigran Tonoyan
Effective Wireless Scheduling via Hypergraph Sketches. 718-759 - Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Joshua Zahl
Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications. 760-787 - Tom Gur
On the Power of Relaxed Local Decoding Algorithms. 788-813
Volume 50, Number 3, 2021
- Ruben Becker
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. 815-856 - Amit Sahai, Brent Waters:
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. 857-908 - Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee:
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing. 909-923 - Xiaohui Bei, Shiteng Chen
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces. 924-971 - Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram:
Quantum Hardness of Learning Shallow Classical Circuits. 972-1013 - David Eppstein, Vijay V. Vazirani:
NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs. 1014-1033 - Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran:
Spectral Analysis of Matrix Scaling and Operator Scaling. 1034-1102 - Keren Censor-Hillel, Michal Dory:
Distributed Spanner Approximation. 1103-1147 - Jérémie Dusart
Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. 1148-1153
- Alexandr Andoni, Keren Censor-Hillel, Jing Chen, Debmalya Panigrahi:
Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016). - Shahar Dobzinski:
Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders. - Leqi Zhu:
A Tight Space Bound for Consensus. - Gil Cohen:
Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs. - Shaddin Dughmi, Haifeng Xu:
Algorithmic Bayesian Persuasion. - Monika Henzinger
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths. - Nikhil Bansal, Aravind Srinivasan, Ola Svensson:
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. - Yang Cai
A Duality-Based Unified Approach to Bayesian Mechanism Design. - Elaine Levey, Thomas Rothvoß:
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies. - Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf:
Bipartite Perfect Matching is in Quasi-NC. - Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Communication and External Information. - Omer Reingold, Guy N. Rothblum, Ron D. Rothblum:
Constant-Round Interactive Proofs for Delegating Computation. - Sepehr Assadi, Sanjeev Khanna, Yang Li:
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. - Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan R. Ullman:
Algorithmic Stability for Adaptive Data Analysis. - Aleksandrs Belovs, Eric Blais:
A Polynomial Lower Bound for Testing Monotonicity.
Volume 50, Number 4, 2021
- Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein:
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities. 1155-1199 - Siu-Wing Cheng, Man-Kit Lau:
Adaptive Planar Point Location. 1200-1247 - Shachar Lovett
Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. 1248-1262 - Marcin Kozik
Solving CSPs Using Weak Local Consistency. 1263-1286 - Yi Li
Tight Bounds for the Subspace Sketch Problem with Applications. 1287-1335 - Bhaskar Ray Chaudhury
A Little Charity Guarantees Almost Envy-Freeness. 1336-1358 - Manuel Bodirsky
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP. 1359-1409 - Johannes Bausch, Felix Leditzky
Error Thresholds for Arbitrary Pauli Noise. 1410-1460 - Nutan Limaye, Karteek Sreenivasaiah
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. 1461-1499
Volume 50, Number 5, 2021
- Gilad Asharov
Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations. 1501-1536 - Vipul Goyal, Silas Richelson
An Algebraic Approach to Nonmalleability. 1537-1579 - René Sitters
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems. 1580-1602 - Artur Czumaj, Peter Davies
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC. 1603-1626 - Mina Dalirrooyfard, Thuy-Duong Vuong, Virginia Vassilevska Williams:
Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles. 1627-1662
Volume 50, Number 6, 2021
- Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. 1663-1700 - Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Kuan Yang:
Counting Solutions to Random CNF Formulas. 1701-1738 - Miriam Backens
A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation. 1739-1799 - Minglong Qin, Penghui Yao:
Nonlocal Games with Noisy Maximally Entangled States are Decidable. 1800-1891 - Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan:
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. 1892-1922
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 2025-01-06 21:32 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: