![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
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
, Pablo Pérez-Lantero, David Rappaport, Carlos Seara
, Javier Tejel
, Jorge Urrutia:
Maximum Rectilinear Convex Subsets. 145-170 - Arkadev Chattopadhyay, Yuval Filmus
, Sajin Koroth, Or Meir, Toniann Pitassi:
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
, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
:
List-Decoding with Double Samplers. 301-349 - Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin
:
Dynamic Sampling from Graphical Models. 350-381 - Rajesh Jayaram
, David P. Woodruff:
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
, Pawel Rzazewski
:
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs. 487-508 - Pawel Gawrychowski
, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann
:
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
, Jingru Zhang:
An O(nlog n)-Time Algorithm for the k-Center Problem in Trees. 602-635 - Rohit Gurjar
, Thomas Thierauf, Nisheeth K. Vishnoi:
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
, Oded Lachish
:
On the Power of Relaxed Local Decoding Algorithms. 788-813
Volume 50, Number 3, 2021
- Ruben Becker
, Sebastian Forster
, Andreas Karrenbauer, Christoph Lenzen:
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, Ji Guan, Youming Qiao
, Xiaoming Sun
:
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
, Derek G. Corneil, Michel Habib:
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
, Sebastian Krinninger
, Danupon Nanongkai:
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
, Nikhil R. Devanur, S. Matthew Weinberg
:
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
, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. 1287-1335 - Bhaskar Ray Chaudhury
, Telikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa:
A Little Charity Guarantees Almost Envy-Freeness. 1336-1358 - Manuel Bodirsky
, Florent R. Madelaine, Antoine Mottet
:
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
, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh:
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. 1461-1499
Volume 50, Number 5, 2021
- Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf:
Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations. 1501-1536 - Vipul Goyal, Silas Richelson
, Alon Rosen
, Margarita Vald:
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
, Merav Parter:
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
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
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.