default search action
SIAM Journal on Computing, Volume 34
Volume 34, Number 1, 2004
- Karhan Akcoglu, Petros Drineas
, Ming-Yang Kao:
Fast Universalization of Investment Strategies. 1-22 - Michal Katz, Nir A. Katz, Amos Korman, David Peleg:
Labeling Schemes for Flow and Connectivity. 23-40 - Carme Àlvarez, Maria J. Blesa, Maria J. Serna:
A Characterization of Universal Stability in the Adversarial Queuing Model. 41-66 - Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. 67-88 - Lars Ivansson, Jens Lagergren:
Algorithms for RH Mapping: New Ideas and Improved Analysis. 89-108 - Stefan Hougardy, Annegret Wagler:
Perfectness is an Elusive Graph Property. 109-117 - Daniele Micciancio
Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor. 118-169 - John M. Hitchcock
Small Spans in Scaled Dimension. 170-194 - Ben Morris, Alistair Sinclair:
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. 195-226 - Edith Cohen, Haim Kaplan:
Balanced-Replication Algorithms for Distribution Trees. 227-247 - Yair Bartal, Manor Mendel
Multiembedding of Metric Spaces. 248-259
Volume 34, Number 2, 2004
- Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. 261-276 - Markus Bläser:
A Complete Characterization of the Algebras of Minimal Bilinear Complexity. 277-298 - Benjamin Doerr:
Nonindependent Randomized Rounding and an Application to Digital Halftoning. 299-317 - Rajat Bhattacharjee, Ashish Goel, Zvi Lotker:
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. 318-332 - Tushar Deepak Chandra, Vassos Hadzilacos, Prasad Jayanti, Sam Toueg:
Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus. 333-357 - Gruia Calinescu
Approximation Algorithms for the 0-Extension Problem. 358-372 - Kai-Min Chung
An Optimal Algorithm for the Maximum-Density Segment Problem. 373-387 - Satish Rao, Andréa W. Richa:
New Approximation Techniques for Some Linear Ordering Problems. 388-404 - Mikkel Thorup:
Quick k-Median, k-Center, and Facility Location for Sparse Graphs. 405-432 - S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
Online Scheduling to Minimize Average Stretch. 433-452 - Anupam Gupta, Amit Kumar
Traveling with a Pez Dispenser (or, Routing Issues in MPLS). 453-474 - Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler:
The Simplex Algorithm in Dimension Three. 475-497 - Yasunori Ishihara, Shin Ishii
Temporal Reasoning about Two Concurrent Sequences of Events. 498-513
Volume 34, Number 3, 2005
- Raimund Seidel, Micha Sharir:
Top-Down Analysis of Path Compression. 515-525 - Pankaj K. Agarwal, Micha Sharir:
Pseudo-Line Arrangements: Duality, Algorithms, and Applications. 526-552 - Vida Dujmovic, Pat Morin
Layout of Graphs with Bounded Tree-Width. 553-579 - Artur Czumaj, Christian Sohler
Abstract Combinatorial Programs and Efficient Property Testers. 580-615 - Aris Anagnostopoulos
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input. 616-639 - Nicolò Cesa-Bianchi, Alex Conconi, Claudio Gentile:
A Second-Order Perceptron Algorithm. 640-668 - Ho-Leung Chan, Tak Wah Lam
Nonmigratory Online Deadline Scheduling on Multiprocessors. 669-682 - Huaming Zhang, Xin He:
On Even Triangulations of 2-Connected Embedded Graphs. 683-696 - Bala Kalyanasundaram, Kirk Pruhs:
Fault-Tolerant Scheduling. 697-719 - Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
Classifying the Complexity of Constraints Using Finite Algebras. 720-742 - Yumei Huo, Joseph Y.-T. Leung:
Online Scheduling of Precedence Constrained Tasks. 743-762 - Jochen Könemann, R. Ravi:
Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds. 763-773
Volume 34, Number 4, 2005
- Alon Efrat
The Complexity of the Union of (alpha, beta)-Covered Objects. 775-787 - Martin Skutella, Marc Uetz:
Stochastic Machine Scheduling with Precedence Constraints. 788-802 - Moses Charikar
Improved Combinatorial Algorithms for Facility Location Problems. 803-824 - Derek G. Corneil, Udi Rotics:
On the Relationship Between Clique-Width and Treewidth. 825-847 - Chryssis Georgiou
Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups. 848-862 - Vladlen Koltun, Micha Sharir:
Curve-Sensitive Cuttings. 863-878 - Timothy M. Chan:
Low-Dimensional Linear Programming with Violations. 879-893 - Richard Cole, Ramesh Hariharan:
Dynamic LCA Queries on Trees. 894-923 - Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu:
Orderly Spanning Trees with Applications. 924-945 - Anna Gál, Adi Rosén:
Omega(log n) Lower Bounds on the Amount of Randomness in 2-Private Computation. 946-959 - Michael Kaminski:
A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields. 960-992 - Grzegorz Malewicz:
A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors. 993-1024
Volume 34, Number 5, 2005
- Géraud Sénizergues:
The Bisimulation Problem for Equational Graphs of Finite Out-Degree. 1025-1106 - Jeffrey C. Jackson
Learning Random Log-Depth Decision Trees under Uniform Distribution. 1107-1128 - Irit Dinur
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. 1129-1146 - Eldar Fischer:
The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance. 1147-1158 - Kousha Etessami, Thomas Wilke, Rebecca A. Schuller:
Fair Simulation Relations, Parity Games, and State Space Reduction for Bu"chi Automata. 1159-1175 - Arfst Nickelsen, Till Tantau:
The Complexity of Finding Paths in Graphs with Bounded Independence Number. 1176-1195 - Amos Beimel
Separating the Power of Monotone Span Programs over Different Fields. 1196-1215 - Panagiota Fatourou, Marios Mavronicolas
Efficiency of Oblivious versus Nonoblivious Schedulers for Optimistic, Rate-based Flow Control. 1216-1252 - Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro:
Optimal Two-Stage Algorithms for Group Testing Problems. 1253-1270 - Frank Kwang-Ming Hwang, Yong He, Yang Wang:
Strictly Nonblocking Multirate logd(N, m, p) Networks. 1271-1278
Volume 34, Number 6, 2005
- Mark McCann, Nicholas Pippenger:
SRT Division Algorithms as Dynamical Systems. 1279-1301 - Thomas Erlebach
Polynomial-Time Approximation Schemes for Geometric Intersection Graphs. 1302-1323 - Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer
Quantum Algorithms for Element Distinctness. 1324-1330 - Esther Ezra, Micha Sharir:
Output-Sensitive Construction of the Union of Triangles. 1331-1351 - Edith Hemaspaandra, Lane A. Hemaspaandra
Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries. 1352-1369 - Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
Approximating the Minimum Spanning Tree Weight in Sublinear Time. 1370-1379 - John Hershberger, Subhash Suri, Csaba D. Tóth:
Binary Space Partitions of Orthogonal Subdivisions. 1380-1397 - Seth Pettie, Vijaya Ramachandran:
A Shortest Path Algorithm for Real-Weighted Undirected Graphs. 1398-1431 - Qi Cheng
On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields. 1432-1442 - David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter
Duality Between Prefetching and Queued Writing with Parallel Disks. 1443-1463 - Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier:
Decidable and Undecidable Problems about Quantum Automata. 1464-1473 - Qingmin Shi, Joseph F. JáJá:
Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry. 1474-1492 - Gagan Aggarwal, Qi Cheng
Complexities for Generalized Models of Self-Assembly. 1493-1515 - Reuven Cohen
Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems. 1516-1528
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-26 00:54 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: