default search action
SIAM Journal on Computing, Volume 47
Volume 47, Number 1, 2018
- Sunil Arya, Guilherme Dias da Fonseca
, David M. Mount
Approximate Polytope Membership Queries. 1-51 - Benny Applebaum, Shachar Lovett
Algebraic Attacks against Random Local Functions and Their Countermeasures. 52-79 - Surender Baswana, Keerti Choudhary
Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal. 80-95 - Amit Daniely, Michael Schapira, Gal Shahaf:
Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik-Chervonenkis Dimension. 96-120 - Yiannis Giannakopoulos
Duality and Optimality of Auctions for Uniform Distributions. 121-165 - Nicolas Bousquet
Multicut Is FPT. 166-207 - Hamed Hatami, Kaave Hosseini
Structure of Protocols for XOR Functions. 208-217 - Artur Czumaj, Peter Davies
Deterministic Communication in Radio Networks. 218-240 - Mika Göös, Rahul Jain
Extension Complexity of Independent Set Polytopes. 241-269 - Mohit Singh, László A. Végh
Approximating Minimum Cost Connectivity Orientation and Augmentation. 270-293
Volume 47, Number 2, 2018
- Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
Erasure-Resilient Property Testing. 295-329 - Moran Feldman
The Submodular Secretary Problem Goes Linear. 330-366 - Alexander A. Sherstov:
Compressing Interactive Communication Under Product Distributions. 367-419 - Wojciech M. Golab, Xiaozhou (Steve) Li, Alejandro López-Ortiz, Naomi Nishimura:
Computing k-Atomicity in Polynomial Time. 420-455 - Georg Gottlob, Enrico Malizia
Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic. 456-492 - Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. 493-523 - Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett
Non-Malleable Codes from Additive Combinatorics. 524-546 - Mikhail Belkin, Luis Rademacher
Eigenvectors of Orthogonally Decomposable Functions. 547-615
Volume 47, Number 3, 2018
- Surender Baswana, Manoj Gupta
Fully Dynamic Maximal Matching in O(log n) Update Time (Corrected Version). 617-650 - Zhiyi Huang
Making the Most of Your Samples. 651-674 - Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. 675-702 - Maria-Florina Balcan, Nicholas J. A. Harvey:
Submodular Functions: Learnability, Structure, and Optimization. 703-754 - Roee David, Uriel Feige:
Random Walks with the Minimum Degree Local Rule Have O(n2) Cover Time. 755-768 - Florent R. Madelaine
On the Complexity of the Model Checking Problem. 769-797 - Jiabao Lin, Hanpin Wang:
The Complexity of Boolean Holant Problems with Nonnegative Weights. 798-828 - Michael Elkin, Arnold Filtser
Prioritized Metric Structures and Embedding. 829-858 - Sayan Bhattacharya, Monika Henzinger
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. 859-887
- Costis Daskalakis, Yael Kalai, Sandy Irani:
Special Section on the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015). 888-889 - Alexandr Andoni, Robert Krauthgamer
Sketching and Embedding are Equivalent for Norms. 890-916 - Aviad Rubinstein:
Inapproximability of Nash Equilibrium. 917-959 - Siddharth Barman:
Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem. 960-981 - Scott Aaronson, Andris Ambainis:
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. 982-1038 - Nikhil Bansal, Anupam Gupta, Guru Guruganesh:
On the Lovász Theta Function for Independent Sets in Sparse Graphs. 1039-1055 - Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam:
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. 1056-1086 - Arturs Backurs, Piotr Indyk:
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). 1087-1097 - Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu:
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. 1098-1122 - Nir Bitansky, Ran Canetti, Sanjam Garg
Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings. 1123-1210 - Richard Cole, Vasilis Gkatzelis:
Approximating the Nash Social Welfare with Indivisible Items. 1211-1236 - Ben Cousins, Santosh S. Vempala:
Gaussian Cooling and O*(n3) Algorithms for Volume and Gaussian Volume. 1237-1273
Volume 47, Number 4, 2018
- Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, Vahid Liaghat:
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems. 1275-1293 - Vitaly Feldman, Will Perkins
On the Complexity of Random Satisfiability Problems with Planted Solutions. 1294-1338 - Eric Allender
Minimum Circuit Size, Graph Isomorphism, and Related Problems. 1339-1372 - Clément L. Canonne
Sampling Correctors. 1373-1423 - Fu Li, Iddo Tzameret, Zhengyu Wang:
Characterizing Propositional Proofs as Noncommutative Formulas. 1424-1462 - Niv Buchbinder
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem. 1463-1482 - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs. 1483-1504 - Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. 1505-1528 - T.-H. Hubert Chan, Fei Chen, Xiaowei Wu
Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming. 1529-1546 - Venkata Gandikota
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. 1547-1584 - Haim Kaplan, Wolfgang Mulzer
Spanners for Directed Transmission Graphs. 1585-1609 - Chandra Chekuri, Anastasios Sidiropoulos:
Approximation Algorithms for Euler Genus and Related Problems. 1610-1643 - Sagnik Mukhopadhyay
Separation Between Deterministic and Randomized Query Complexity. 1644-1666 - Andreas Emil Feldmann
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. 1667-1704 - T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang
A PTAS for the Steiner Forest Problem in Doubling Metrics. 1705-1734
Volume 47, Number 5, 2018
- Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young
Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. 1735-1754 - Nikhil Bansal, Shashwat Garg, Jesper Nederlof
Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. 1755-1777 - Mika Göös, Toniann Pitassi:
Communication Lower Bounds via Critical Block Sensitivity. 1778-1806
- Adam Smith, Jochen Könemann:
Special Section on the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014). 1807-1808 - Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. 1809-1857 - Ruta Mehta:
Constant Rank Two-Player Games are PPAD-hard. 1858-1887 - Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting Codes and the Price of Approximate Differential Privacy. 1888-1938 - Thomas Kesselheim, Klaus Radke, Andreas Tönnis
Primal Beats Dual on Online Packing LPs in the Random-Order Model. 1939-1964 - R. Ryan Williams
Faster All-Pairs Shortest Paths via Circuit Complexity. 1965-1985 - Benjamin Rossman:
Formulas versus Circuits for Small Distance Connectivity. 1986-2028
Volume 47, Number 6, 2018
- Vladimir Kolmogorov:
Commutativity in the Algorithmic Lovász Local Lemma. 2029-2056 - Lin Chen
An O(log m)-Competitive Algorithm for Online Machine Minimization. 2057-2077 - Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir:
Near-Optimal Distributed Maximum Flow. 2078-2117 - Chandra Chekuri, Chao Xu:
Minimum Cuts and Sparsification in Hypergraphs. 2118-2156 - Aloni Cohen, Justin Holmgren
Watermarking Cryptographic Capabilities. 2157-2202 - Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. 2203-2236
- Cristopher Moore, Santosh S. Vempala:
Special Section on the Fifty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015). 2237 - Subhash Khot, Dor Minzer, Muli Safra
On Monotonicity Testing and Boolean Isoperimetric-type Theorems. 2238-2276 - Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette:
Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness. 2277-2314 - Yin Tat Lee, He Sun:
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. 2315-2336 - Timothy M. Chan, Yakov Nekrich
Towards an Optimal Method for Dynamic Planar Point Location. 2337-2361 - Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. 2362-2434 - Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. 2435-2450 - Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the Discrete Fourier Transform. 2451-2487 - Adam W. Marcus, Daniel A. Spielman
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. 2488-2509 - Mikkel Thorup
Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8. 2510-2526 - Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser. 2527-2555
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 2024-11-22 19: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: