default search action
SIAM Journal on Computing, Volume 42
Volume 42, Number 1, 2013
- Daniel A. Spielman
, Shang-Hua Teng:
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. 1-26 - Siu On Chan, Michael Molloy:
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. 27-60 - Amit Chakrabarti
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. 61-83 - Victor Chen, Elena Grigorescu, Ronald de Wolf:
Error-Correcting Data Structures. 84-111 - Albert Atserias, Elitza N. Maneva
Sherali-Adams Relaxations and Indistinguishability in Counting Logics. 112-137 - Sariel Har-Peled
Approximate Nearest Neighbor Search for Low-Dimensional Queries. 138-159 - Baruch Awerbuch, Yossi Azar, Amir Epstein:
The Price of Routing Unsplittable Flow. 160-177 - José A. Soto:
Matroid Secretary Problem in the Random-Assignment Model. 178-211 - Elad Verbin, Qin Zhang
The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model. 212-229 - Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior. 230-264 - Jan Vondrák:
Symmetry and Approximability of Submodular Maximization Problems. 265-304 - Satyen Kale, Yuval Peres, C. Seshadhri:
Noise Tolerance of Expanders and Sublinear Expansion Reconstruction. 305-323 - Heng Guo, Pinyan Lu
The Complexity of Symmetric Boolean Parity Holant Problems. 324-356 - Jon Lee
Matroid Matching: The Power of Local Search. 357-379 - Or Meir:
IP = PSPACE Using Error-Correcting Codes. 380-403
Volume 42, Number 2, 2013
- Hsien-Kuei Hwang
Threshold Phenomena in k-Dominant Skylines of Random Samples. 405-441 - Pankaj K. Agarwal, Sariel Har-Peled
Embeddings of Surfaces, Curves, and Moving Points in Euclidean Space. 442-458 - Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano
Nearly Tight Bounds for Testing Function Isomorphism. 459-493 - Jens M. Schmidt
Contractions, Removals, and Certifying 3-Connectivity in Linear Time. 494-535 - Elad Haramaty, Amir Shpilka
Optimal Testing of Multivariate Polynomials over Small Prime Fields. 536-562 - Guy Bresler, Elchanan Mossel
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. 563-578 - Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang
A Harmonic Algorithm for the 3D Strip Packing Problem. 579-592 - Rolando D. Somma, Sergio Boixo:
Spectral Gap Amplification. 593-610 - Ayelet Butman, Peter Clifford, Raphaël Clifford
Pattern Matching under Polynomial Transformation. 611-633 - Bernadette Charron-Bost, Antoine Gaillard, Jennifer L. Welch, Josef Widder
Link Reversal Routing with Binary Link Labels: Work Complexity. 634-661 - Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard:
Bounded-Curvature Shortest Paths through a Sequence of Points Using Convex Optimization. 662-684 - Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi
Fast Integer Multiplication Using Modular Arithmetic. 685-699 - Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. 700-731
Volume 42, Number 3, 2013
- Ho Yee Cheung, Lap Chi Lau, Kai Man Leung:
Graph Connectivities, Network Coding, and Expander Graphs. 733-751 - Subhash Khot, Dana Moshkovitz:
NP-Hardness of Approximately Solving Linear Equations over Reals. 752-791 - Derek G. Corneil, Barnaby Dalton, Michel Habib
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. 792-807 - Fabrizio Grandoni
Set Covering with Our Eyes Closed. 808-830 - Virginia Vassilevska Williams, Ryan Williams
Finding, Minimizing, and Counting Weighted Subgraphs. 831-854 - Ilan Newman, Yuri Rabinovich:
On Multiplicative Lambda-Approximations and Some Geometric Applications. 855-883 - Stefan Göller, Markus Lohrey:
Branching-Time Model Checking of One-Counter Processes and Timed Automata. 884-923 - Jin-Yi Cai, Xi Chen, Pinyan Lu
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. 924-1029 - L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder:
Balls and Bins: Smaller Hash Families and Faster Evaluation. 1030-1050 - Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman:
Pseudorandom Generators for Combinatorial Shapes. 1051-1076 - Hsien-Chih Chang, Hsueh-I Lu:
Computing the Girth of a Planar Graph in Linear Time. 1077-1094 - Ilan Newman, Christian Sohler
Every Property of Hyperfinite Graphs Is Testable. 1095-1112 - Viresh Patel:
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus. 1113-1131 - Leslie Ann Goldberg, Mark Jerrum:
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. 1132-1157 - Danny Z. Chen, John Hershberger, Haitao Wang:
Computing Shortest Paths amid Convex Pseudodisks. 1158-1184 - Lap Chi Lau, Chun Kong Yung:
Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities. 1185-1200 - Benjamin A. Burton
Locating Regions in a Sequence under Density Constraints. 1201-1215
- Chris Peikert, Robert Kleinberg, Aravind Srinivasan, Alan M. Frieze
Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010). 1216-1217 - Ryan Williams
Improving Exhaustive Search Implies Superpolynomial Lower Bounds. 1218-1244 - Martin E. Dyer
An Effective Dichotomy for the Counting Constraint Satisfaction Problem. 1245-1274 - Raghu Meka, David Zuckerman:
Pseudorandom Generators for Polynomial Threshold Functions. 1275-1301 - Swastik Kopparty, Shubhangi Saraf:
Local List-Decoding and Testing of Random Linear Codes from High Error. 1302-1326 - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
How to Compress Interactive Communication. 1327-1363 - Daniele Micciancio
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations. 1364-1391 - Ashish Goel, Michael Kapralov
Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs. 1392-1404 - Iftach Haitner, Omer Reingold, Salil P. Vadhan:
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions. 1405-1430
Volume 42, Number 4, 2013
- Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
The All-or-Nothing Multicommodity Flow Problem. 1467-1493 - Anupam Gupta, Moritz Hardt, Aaron Roth
Privately Releasing Conjunctions and the Statistical Query Barrier. 1494-1520 - Paolo Ferragina
On the Bit-Complexity of Lempel-Ziv Compression. 1521-1541 - Sergio Cabello, Erin W. Chambers
Multiple-Source Shortest Paths in Embedded Graphs. 1542-1571 - George Christodoulou
A Deterministic Truthful PTAS for Scheduling Related Machines. 1572-1595 - Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina:
Asymmetric Traveling Salesman Path and Directed Latency Problems. 1596-1619 - Ge Xia:
The Stretch Factor of the Delaunay Triangulation Is Less than 1.998. 1620-1659 - Haim Kaplan, Robert Endre Tarjan, Uri Zwick
Soft Heaps Simplified. 1660-1673 - Rajesh Hemant Chitnis
Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. 1674-1696 - Martin Tancer
Nerves of Good Covers Are Algorithmically Unrecognizable. 1697-1719 - Prosenjit Bose
Robust Geometric Spanners. 1720-1736 - Albert Atserias, Martin Grohe
Size Bounds and Query Plans for Relational Joins. 1737-1767 - Simone Linz
Counting Trees in a Phylogenetic Network Is \#P-Complete. 1768-1776
Volume 42, Number 5, 2013
- Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Prabhakar Raghavan:
Models for the Compressible Web. 1777-1802 - Sergio Cabello
Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard. 1803-1829 - Anne Driemel
Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts. 1830-1866 - Pankaj K. Agarwal, Boris Aronov
Computing Correlation between Piecewise-Linear Functions. 1867-1887 - Mahdi Cheraghchi
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. 1888-1914 - David A. Cohen, Martin C. Cooper
An Algebraic Theory of Complexity for Discrete Optimization. 1915-1939 - Ting Deng, Wenfei Fan
On the Complexity of Package Recommendation Problems. 1940-1986 - Thomas Decker, Gábor Ivanyos
Hidden Symmetry Subgroup Problems. 1987-2007 - Benny Applebaum:
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions. 2008-2037
Volume 42, Number 6, 2013
- Pankaj K. Agarwal, Jirí Matousek, Micha Sharir:
On Range Searching with Semialgebraic Sets. II. 2039-2062 - Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng:
Reducibility among Fractional Stability Problems. 2063-2113 - Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in. 2114-2131 - Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
Deterministic Algorithms for the Lovász Local Lemma. 2132-2155 - Nikolaos Fountoulakis
On the Insertion Time of Cuckoo Hashing. 2156-2181 - Shachar Lovett
A Space Lower Bound for Dynamic Approximate Membership Data Structures. 2182-2196 - Fedor V. Fomin
Subexponential Parameterized Algorithm for Minimum Fill-In. 2197-2216 - Lap Chi Lau, Mohit Singh:
Additive Approximation for Bounded Degree Survivable Network Design. 2217-2242 - Giuseppe Di Battista
On the Queue Number of Planar Graphs. 2243-2285
- Maria-Florina Balcan, Mark Braverman, Daniel A. Spielman:
Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). 2286 - Shahar Dobzinski, Shaddin Dughmi:
On the Power of Randomization in Algorithmic Mechanism Design. 2287-2304 - Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. 2305-2328 - Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. 2329-2374 - Ryan O'Donnell, Karl Wimmer:
KKL, Kruskal-Katona, and Monotone Nets. 2375-2399 - Ankur Moitra:
Vertex Sparsification and Oblivious Reductions. 2400-2423 - Tanmoy Chakraborty, Zhiyi Huang
Dynamic and Nonuniform Pricing Strategies for Revenue Maximization. 2424-2451 - Irit Dinur
Composition of Low-Error 2-Query PCPs Using Decodable PCPs. 2452-2486 - Iftach Haitner:
A Parallel Repetition Theorem for Any Interactive Argument. 2487-2501
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-02-20 19:35 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: