default search action
SIAM Journal on Computing, Volume 35
Volume 35, Number 1, 2005
- Eli Ben-Sasson, Prahladh Harsha
, Sofya Raskhodnikova:
Some 3CNF Properties Are Hard to Test. 1-21 - Michael Lindenbaum, Hanan Samet, Gísli R. Hjaltason:
A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases. 22-58 - Dieter van Melkebeek, Rahul Santhanam:
Holographic Proofs and Derandmization. 59-90 - Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. 91-109 - Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. 110-119 - Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, David Peleg:
Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. 120-131 - Tugkan Batu
The Complexity of Approximating the Entropy. 132-150 - Jie Gao, Li Zhang:
Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications. 151-169 - Greg Kuperberg:
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. 170-188 - Refael Hassin, Asaf Levin
A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem. 189-200 - Kazuyuki Amano, Akira Maruoka:
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates. 201-216 - Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan
Bounds on the Efficiency of Generic Cryptographic Constructions. 217-246 - Guy Kortsarz, Zeev Nutov:
Approximating k-node Connected Subgraphs via Critical Graphs. 247-257
Volume 35, Number 2, 2005
- Petr Hlinený
A Parametrized Algorithm for Matroid Branch-Width. 259-277 - Susanne Albers, Markus Schmidt:
On the Performance of Greedy Algorithms in Packet Buffering. 278-304 - Costas Busch, Srikanta Tirthapura
Analysis of Link Reversal Routing Algorithms. 305-326 - Ketan Dalal, Luc Devroye, Ebrahim Malalla
Two-Way Chaining with Reassignment. 327-340 - Michael A. Bender, Erik D. Demaine, Martin Farach-Colton
Cache-Oblivious B-Trees. 341-358 - Gyung-Ok Lee, Kwang-Moo Choe:
A Powerful LL(k) Covering Transformation. 359-377 - Roberto Grossi, Jeffrey Scott Vitter
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. 378-407 - Joel Friedman
Recognizing More Unsatisfiable Random k-SAT Instances Efficiently. 408-430 - Leah Epstein, Rob van Stee:
Optimal Online Algorithms for Multidimensional Packing Problems. 431-448 - April Rasala Lehman, Gordon T. Wilfong:
Strictly Nonblocking WDM Cross-connects. 449-485 - Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
Strong Spatial Mixing with Fewer Colors for Lattice Graphs. 486-517
Volume 35, Number 3, 2005
- Klaus Jansen, Lorant Porkolab:
General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time. 519-530 - Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia
Optimal Covering Tours with Turn Costs. 531-566 - Darin Goldstein, Kojiro Kobayashi:
On the Complexity of Network Synchronization. 567-589 - Ernst-Erich Doberkat:
Stochastic Relations: Congruences, Bisimulations and the Hennessy--Milner Theorem. 590-626 - Bernard Chazelle, Ding Liu, Avner Magen:
Sublinear Geometric Algorithms. 627-646 - Bjørn Kjos-Hanssen, André Nies
Lowness for the Class of Schnorr Random Reals. 647-657 - Minming Li
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. 658-671 - Michael Elkin, Guy Kortsarz:
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. 672-689 - Dirk L. Vertigan:
The Computational Complexity of Tutte Invariants for Planar Graphs. 690-712 - Chandra Chekuri, Sanjeev Khanna:
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. 713-728 - Weiping Shi, Chen Su:
The Rectilinear Steiner Arborescence Problem Is NP-Complete. 729-740 - Meghanad D. Wagh, Osman Guzide:
Mapping Cycles and Trees on Wrap-Around Butterfly Graphs. 741-765 - Hung Quang Ngo:
WDM Switching Networks, Rearrangeable and Nonblocking [w, f]-connectors. 766-785
Volume 35, Number 4, 2006
- László Babai
Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004). - Noga Alon, Assaf Naor:
Approximating the Cut-Norm via Grothendieck's Inequality. 787-803 - Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments. 804-824 - Daniel Bienstock, Garud Iyengar:
Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations. 825-854 - René Beier, Berthold Vöcking:
Typical Properties of Winners and Losers in Discrete Optimization. 855-881 - Jonathan A. Kelner:
Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus. 882-902 - Alexander Healy, Salil P. Vadhan, Emanuele Viola:
Using Nondeterminism to Amplify Hardness. 903-931 - Mihai Patrascu, Erik D. Demaine:
Logarithmic Lower Bounds in the Cell-Probe Model. 932-963 - Uriel Feige:
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. 964-984 - László Lovász, Santosh S. Vempala:
Hit-and-Run from a Corner. 985-1005
Volume 35, Number 5, 2006
- Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat:
Function Matching. 1007-1022 - Sean Curran, Orlando Lee, Xingxing Yu:
Finding Four Independent Trees . 1023-1058 - Holger Petersen, John Michael Robson:
Efficient Simulations by Queue Machines. 1059-1069 - Julia Kempe
The Complexity of the Local Hamiltonian Problem. 1070-1097 - Jesper Jansson
Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. 1098-1121 - Karl-Heinz Niggl, Henning Wunderlich:
Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs. 1122-1147 - Sariel Har-Peled
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications. 1148-1184 - Omer Reingold, Ronen Shaltiel, Avi Wigderson:
Extracting Randomness via Repeated Condensing. 1185-1209 - Markus Lohrey:
Word Problems and Membership Problems on Compressed Words. 1210-1240 - Maurice Queyranne, Andreas S. Schulz:
Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems. 1241-1253 - Moni Naor, Benny Pinkas:
Oblivious Polynomial Evaluation. 1254-1281
Volume 35, Number 6, 2006
- Klaus Weihrauch, Ning Zhong:
An Algorithm for Computing Fundamental Solutions. 1283-1294 - Serge Abiteboul, Stephen Alstrup, Haim Kaplan, Tova Milo, Theis Rauhe:
Compact Labeling Scheme for Ancestor Queries. 1295-1309 - Christoph Dürr, Mark Heiligman, Peter Høyer
Quantum Query Complexity of Some Graph Problems. 1310-1328 - Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The Approximability of Three-valued MAX CSP. 1329-1349 - Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking:
Balanced Allocations: The Heavily Loaded Case. 1350-1385 - Floris Geerts
Linearization and Completeness Results for Terminating Transitive Closure Queries on Spatial Databases. 1386-1439 - Hua-Huai Chern, Hsien-Kuei Hwang
Partial Match Queries in Random k-d Trees. 1440-1466 - Eric Allender, Harry Buhrman, Michal Koucký
Power from Random Strings. 1467-1493 - Christian Worm Mortensen:
Fully Dynamic Orthogonal Range Reporting on RAM. 1494-1525
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-14 20:49 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: