default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 39
Volume 39, Number 1, 2009
- Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai:
Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). vii - Dmitry Gavinsky, Julia Kempe
, Oded Regev, Ronald de Wolf:
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. 1-24 - John Watrous:
Zero-Knowledge against Quantum Attacks. 25-58 - Jakob Nordström:
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. 59-121 - Uriel Feige:
On Maximizing Welfare When Utility Functions Are Subadditive. 122-142 - Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira:
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. 143-167 - Anup Rao:
Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources. 168-194 - Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
The Complexity of Computing a Nash Equilibrium. 195-259 - Dimitris Achlioptas, Federico Ricci-Tersenghi:
Random Formulas Have Frozen Variables. 260-280 - Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs with Constant Congestion. 281-301 - Nir Ailon, Bernard Chazelle:
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors. 302-322 - Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. 323-360
Volume 39, Number 2, 2009
- Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
The Online Set Cover Problem. 361-370 - Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:
On Earthmover Distance, Metric Labeling, and 0-Extension. 371-387 - Igor A. Semaev:
Sparse Algebraic Equations over Finite Fields. 388-409 - Andreas Maletti, Jonathan Graehl, Mark Hopkins, Kevin Knight:
The Power of Extended Top-Down Tree Transducers. 410-430 - Artur Czumaj, Andrzej Lingas:
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication. 431-444 - Zvi Lotker, Boaz Patt-Shamir, Adi Rosén:
Distributed Approximate Matching. 445-460 - Sven Koenig, Joseph S. B. Mitchell, Apurva Mudgal, Craig A. Tovey:
A Near-Tight Approximation Algorithm for the Robot Localization Problem. 461-490 - Or Meir:
Combinatorial Construction of Locally Testable Codes. 491-544 - Matthew Andrew, Ashwin Nayak, Rajmohan Rajaraman:
Special Section on Foundations of Computer Science. 545 - Andreas Björklund, Thore Husfeldt, Mikko Koivisto:
Set Partitioning via Inclusion-Exclusion. 546-563 - Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. 564-605 - Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
On Agnostic Learning of Parities, Monomials, and Halfspaces. 606-645 - Roman Vershynin:
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. 646-678 - Nicholas J. A. Harvey:
Algebraic Algorithms for Matching and Matroid Problems. 679-702 - Timothy M. Chan, Mihai Patrascu:
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time. 703-729 - Mihai Patrascu, Mikkel Thorup:
Higher Lower Bounds for Near-Neighbor and Further Rich Problems. 730-741 - Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise. 742-765 - David Arthur, Sergei Vassilvitskii:
Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method. 766-782
Volume 39, Number 3, 2009
- Kevin L. Chang, Ravi Kannan:
Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions. 783-812 - Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. 813-842 - Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. 843-873 - Phong Q. Nguyen, Damien Stehlé:
An LLL Algorithm with Quadratic Complexity. 874-903 - Artur Czumaj, Christian Sohler:
Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. 904-922 - Ke Chen:
On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. 923-947 - Shengyu Zhang:
Tight Bounds for Randomized and Quantum Local Search. 948-977 - Eric Allender, Vladlen Koltun, Maxim Sviridenko:
Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007). 978 - Martin Fürer:
Faster Integer Multiplication. 979-1005 - Ronen Shaltiel, Christopher Umans:
Low-End Uniform Hardness versus Randomness Tradeoffs for AM. 1006-1037 - Rahul Santhanam:
Circuit Lower Bounds for Merlin--Arthur Classes. 1038-1061 - Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh:
Survivable Network Design with Degree or Order Constraints. 1062-1087 - Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett:
Playing Games with Approximation Algorithms. 1088-1106 - Anna Pagh, Rasmus Pagh, Milan Ruzic:
Linear Probing with Constant Independence. 1107-1120 - Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Zero-Knowledge Proofs from Secure Multiparty Computation. 1121-1152 - Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, Salil P. Vadhan:
Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function. 1153-1218
Volume 39, Number 4, 2009
- Mohammad Ali Abam, Mark de Berg, Bettina Speckmann:
Kinetic kd-Trees and Longest-Side kd-Trees. 1219-1232 - Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii:
The Hiring Problem and Lake Wobegon Strategies. 1233-1255 - Nikhil Bansal, Alberto Caprara, Maxim Sviridenko:
A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. 1256-1278 - Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. 1279-1293 - Nikhil Bansal, Kirk Pruhs, Clifford Stein:
Speed Scaling for Weighted Flow Time. 1294-1308 - Graham Cormode, Srikanta Tirthapura, Bojian Xu:
Time-decaying Sketches for Robust Aggregation of Sensor Data. 1309-1339 - Ilias Diakonikolas, Mihalis Yannakakis:
Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems. 1340-1371 - Liad Blumrosen, Noam Nisan:
On the Computational Power of Demand Queries. 1372-1391 - Klaus Jansen:
Parameterized Approximation Scheme for the Multiple Knapsack Problem. 1392-1412 - Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan:
Additive Guarantees for Degree-Bounded Directed Network Design. 1413-1431 - Bin Ma, Xiaoming Sun:
More Efficient Algorithms for Closest String and Substring Problems. 1432-1443 - Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
On the Cost of Interchange Rearrangement in Strings. 1444-1461 - Sergey Bravyi, Barbara M. Terhal:
Complexity of Stoquastic Frustration-Free Hamiltonians. 1462-1485 - Wim Martens, Frank Neven, Thomas Schwentick:
Complexity of Decision Problems for XML Schemas and Chain Regular Expressions. 1486-1530 - Libor Barto, Marcin Kozik:
Congruence Distributivity Implies Bounded Width. 1531-1542 - Adam Kirsch, Michael Mitzenmacher, Udi Wieder:
More Robust Hashing: Cuckoo Hashing with a Stash. 1543-1561 - Oded Regev, Ben Toner:
Simulating Quantum Correlations with Finite Communication. 1562-1580 - Rebecca Schulman, Erik Winfree:
Programmable Control of Nucleation for Algorithmic Self-Assembly. 1581-1616 - Claire Kenyon, Yuval Rabani, Alistair Sinclair:
Low Distortion Maps Between Point Sets. 1617-1636
Volume 39, Number 4, 2010
- Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. 1637-1665
Volume 39, Number 5, 2010
- Danny Harnik, Moni Naor:
On the Compressibility of NP Instances and Cryptographic Applications. 1667-1713 - Markus Kirschmer, John Voight:
Algorithmic Enumeration of Ideal Classes for Quaternion Orders. 1714-1747 - Sanjeev Arora, Elad Hazan, Satyen Kale:
O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n2) Time. 1748-1771 - Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design. 1772-1798 - Ho-Lin Chen, Tim Roughgarden, Gregory Valiant:
Designing Network Protocols for Good Equilibria. 1799-1832 - Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC0. 1833-1855 - Satish Rao, Shuheng Zhou:
Edge Disjoint Paths in Moderately Connected Graphs. 1856-1887 - Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
Querying Approximate Shortest Paths in Anisotropic Regions. 1888-1918 - Amit Chakrabarti, Oded Regev:
An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. 1919-1940 - Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Intractability of Clique-Width Parameterizations. 1941-1956 - Artur Czumaj, Piotr Krysta, Berthold Vöcking:
Selfish Traffic Allocation for Server Farms. 1957-1987 - Tali Kaufman, Simon Litsyn, Ning Xie:
Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2). 1988-2003 - Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. 2004-2047 - Edith Cohen, Haim Kaplan, Tova Milo:
Labeling Dynamic XML Trees. 2048-2074 - Timothy M. Chan:
More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. 2075-2089 - Eyal Kushilevitz, Yehuda Lindell, Tal Rabin:
Information-Theoretically Secure Protocols and Security under Composition. 2090-2112
Volume 39, Number 6, 2010
- Vladimir Braverman, Rafail Ostrovsky:
Effective Computations on Sliding Windows. 2113-2131 - Iyad A. Kanj, Ljubomir Perkovic, Ge Xia:
On Spanners and Lightweight Spanners of Geometric Graphs. 2132-2161 - Gianluca De Marco:
Distributed Broadcast in Unknown Radio Networks. 2162-2175 - Elchanan Mossel, Sébastien Roch:
Submodularity of Influence in Social Networks: From Local to Global. 2176-2188 - Deeparnab Chakrabarty, Gagan Goel:
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. 2189-2211 - Jaroslaw Byrka, Karen I. Aardal:
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. 2212-2231 - Flavio Chierichetti, Andrea Vattani:
The Local Nature of List Colorings for Graphs of High Girth. 2232-2250 - Eldar Fischer, Frédéric Magniez, Michel de Rougemont:
Approximate Satisfiability and Equivalence. 2251-2281 - Javier Esparza, Stefan Kiefer, Michael Luttenberger:
Computing the Least Fixed Point of Positive Polynomial Systems. 2282-2335 - Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht:
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions. 2336-2362 - Liam Roditty:
On the k Shortest Simple Paths Problem in Weighted Directed Graphs. 2363-2376 - Cristopher Moore, Alexander Russell, Piotr Sniady:
On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism. 2377-2396 - James R. Lee, Christopher Umans:
Special Section On Foundations of Computer Science. 2397 - Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance. 2398-2429 - Per Austrin:
Towards Sharp Inapproximability for Any 2-CSP. 2430-2463 - Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials. 2464-2486 - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings. 2487-2512 - Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang:
Any AND-OR Formula of Size N Can Be Evaluated in Time N1/2+o(1) on a Quantum Computer. 2513-2530 - Kousha Etessami, Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points. 2531-2597 - Parikshit Gopalan, Subhash Khot, Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. 2598-2621 - Philipp Hertel, Toniann Pitassi:
The PSPACE-Completeness of Black-White Pebbling. 2622-2682
Volume 39, Number 7, 2010
- Mary Cryan, Martin E. Dyer, Dana Randall:
Approximately Counting Integral Flows and Cell-Bounded Contingency Tables. 2683-2703 - Boris Aronov, Micha Sharir:
Approximate Halfspace Range Counting. 2704-2725 - Wojciech M. Golab, Danny Hendler, Philipp Woelfel:
An O(1) RMRs Leader Election Algorithm. 2726-2760 - Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. 2761-2822 - Amin Coja-Oghlan:
A Better Algorithm for Random k-SAT. 2823-2864 - Surender Baswana, Telikepalli Kavitha:
Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs. 2865-2896 - Michael E. Saks, C. Seshadhri:
Local Monotonicity Reconstruction. 2897-2926 - Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
An Efficient Algorithm for Partial Order Production. 2927-2940 - Akinori Kawachi, Tomoyuki Yamakami:
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. 2941-2969 - Arash Asadpour, Amin Saberi:
An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods. 2970-2989 - Marc J. van Kreveld, Maarten Löffler, Joseph S. B. Mitchell:
Preprocessing Imprecise Points and Splitting Triangulations. 2990-3000 - Zeev Nutov:
Approximating Steiner Networks with Node-Weights. 3001-3022 - Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, Ross Willard:
Tractability and Learnability Arising from Algebras with Few Subpowers. 3023-3037 - Julián Mestre:
Adaptive Local Ratio. 3038-3057 - Alon Rosen, Gil Segev:
Chosen-Ciphertext Security via Correlated Products. 3058-3088 - Itai Arad, Zeph Landau:
Quantum Computation and the Evaluation of Tensor Networks. 3089-3121 - Ronen Shaltiel, Emanuele Viola:
Hardness Amplification Proofs Require Majority. 3122-3154 - Eldar Fischer, Arie Matsliah, Asaf Shapira:
Approximate Hypergraph Partitioning and Applications. 3155-3185 - Pierre McKenzie, Michael Thomas, Heribert Vollmer:
Extensional Uniformity for Boolean Circuits. 3186-3206 - Julia Kempe, Oded Regev, Ben Toner:
Unique Games with Entangled Provers Are Easy. 3207-3229 - Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. 3230-3247 - Boris Aronov, Esther Ezra, Micha Sharir:
Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes. 3248-3282 - Haim Kaplan, Natan Rubin, Micha Sharir:
Line Transversals of Convex Polyhedra in R3. 3283-3310 - Nikhil Bansal, Kirk Pruhs:
Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service. 3311-3335 - Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs. 3336-3402 - Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty:
Fault Tolerant Spanners for General Graphs. 3403-3423 - Endre Boros, Khaled M. Elbassioni, Kazuhisa Makino:
Left-to-Right Multiplication for Monotone Boolean Dualization. 3424-3439
Volume 39, Number 8, 2010
- Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. 3441-3462 - Anna Gál, Parikshit Gopalan:
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. 3463-3479 - Robert M. Hierons:
Reaching and Distinguishing States of Distributed Systems. 3480-3500 - Yuval Rabani, Amir Shpilka:
Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. 3501-3520 - David Doty:
Randomized Self-Assembly for Exact Shapes. 3521-3552 - Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy. 3553-3570 - Klaus Jansen, Ralf Thöle:
Approximation Algorithms for Scheduling Parallel Jobs. 3571-3615 - Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer:
Strict Cost Sharing Schemes for Steiner Forest. 3616-3632 - Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson:
A General Approach for Incremental Approximation and Hierarchical Clustering. 3633-3669 - David Duris:
Extension Preservation Theorems on Classes of Acyclic Finite Structures. 3670-3681 - Manuel Bodirsky, Hubie Chen:
Quantified Equality Constraints. 3682-3699 - Simon Fischer, Harald Räcke, Berthold Vöcking:
Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. 3700-3735 - Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. 3736-3751 - Partha Dutta, Rachid Guerraoui, Ron R. Levy, Marko Vukolic:
Fast Access to Distributed Atomic Memory. 3752-3783 - Éric Colin de Verdière, Jeff Erickson:
Tightening Nonsimple Paths and Cycles on Surfaces. 3784-3813 - David Eppstein, Michael T. Goodrich, Darren Strash:
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings. 3814-3829 - Maxim Gurevich, Idit Keidar:
Correctness of Gossip-Based Membership under Message Loss. 3830-3859 - Julia Lipman, Quentin F. Stout:
Analysis of Delays Caused by Local Synchronization. 3860-3884 - Hagit Attiya, Keren Censor-Hillel:
Lower Bounds for Randomized Consensus under a Weak Adversary. 3885-3904
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-12-27 21:27 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:
