27. STOC 1995: Las Vegas, NV, USA

• Samir Khuller, Balaji Raghavachari:
  Improved approximation algorithms for uniform connectivity problems. 1-10
  
• David R. Karger:
  A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. 11-17
  
• David R. Karger, Serge A. Plotkin:
  Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. 18-25
  
• Jon M. Kleinberg, Éva Tardos:
  Approximations for the disjoint paths problem in high-diameter planar networks. 26-35
  
• Matthew K. Franklin, Moti Yung:
  Secure hypergraphs: privacy from partial broadcast (Extended Abstract). 36-44
  
• Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
  Incremental cryptography and application to virus protection. 45-56
  
• Mihir Bellare, Phillip Rogaway:
  Provably secure session key distribution: the three party case. 57-66
  
• Andrew Chi-Chih Yao:
  Security of quantum protocols against coherent measurements. 67-75
  
• László Lovász, Peter Winkler:
  Efficient stopping rules for Markov chains. 76-82
  
• Yuval Rabani, Yuri Rabinovich, Alistair Sinclair:
  A computational view of population genetics. 83-92
  
• Haim Kaplan, Robert Endre Tarjan:
  Persistent lists with catenation via recursive slow-down. 93-102
  
• Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson:
  On data structures and asymmetric communication complexity. 103-111
  
• Persi Diaconis, Laurent Saloff-Coste:
  What do we know about the Metropolis algorithm? 112-129
  
• Stephen Ponzio:
  A lower bound for integer multiplication with read-once branching programs. 130-139
  
• Noam Nisan, Amnon Ta-Shma:
  Symmetric logspace is closed under complement. 140-146
  
• Jeff Edmonds, Chung Keung Poon:
  A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model. 147-156
  
• William E. Hart, Sorin Istrail:
  Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal (Extended Abstract). 157-168
  
• S. Rao Kosaraju, Arthur L. Delcher:
  Large-scale assembly of DNA strings and space-efficient construction of suffix trees. 169-177
  
• Sridhar Hannenhalli, Pavel A. Pevzner:
  Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. 178-189
  
• Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay V. Raghavan, Dawn Wilkins:
  How many queries are needed to learn? 190-199
  
• Marek Karpinski, Angus Macintyre:
  Polynomial bounds for VC dimension of sigmoidal neural networks. 200-208
  
• Jyrki Kivinen, Manfred K. Warmuth:
  Additive versus exponentiated gradient updates for linear prediction. 209-218
  
• Nader H. Bshouty, Christino Tamon:
  On the Fourier spectrum of monotone functions (Extended Abstract). 219-228
  
• Prabhakar Raghavan, Eli Upfal:
  Stochastic contention resolution with short delays. 229-237
  
• Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Eilstrup Rasmussen:
  Parallel randomized load balancing (Preliminary Version). 238-247
  
• Mor Harchol-Balter, David Wolfe:
  Bounding delays in packet-routing networks. 248-257
  
• Yishay Mansour, Boaz Patt-Shamir:
  Many-to-one packet routing on grids (Extended Abstract). 258-267
  
• Aravind Srinivasan:
  Improved approximations of packing and covering problems. 268-276
  
• Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala:
  Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. 277-283
  
• Sanjeev Arora, David R. Karger, Marek Karpinski:
  Polynomial time approximation schemes for dense instances of NP-hard problems. 284-293
  
• Avrim Blum, Prasad Chalasani, Santosh Vempala:
  A constant-factor approximation for the k-MST problem in the plane. 294-302
  
• Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
  The relative complexity of NP search problems. 303-314
  
• Erich Grädel, Klaus Meer:
  Descriptive complexity theory over the real numbers. 315-324
  
• Jie Wang:
  Average-case completeness of a word problem for groups. 325-334
  
• Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther:
  On real Turing machines that toss coins. 335-342
  
• Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki:
  Motion planning for a steering-constrained robot through moderate obstacles. 343-352
  
• Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan:
  Randomized query processing in robot path planning (Extended Abstract). 353-362
  
• Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis:
  Distinguishing tests for nondeterministic and probabilistic machines. 363-372
  
• Thomas A. Henzinger, Peter W. Kopke, Anuj Puri, Pravin Varaiya:
  What's decidable about hybrid automata? 373-382
  
• William R. Pulleyblank:
  Two Steiner tree packing problems (Extended Abstract). 383-387
  
• Daniel A. Spielman:
  Linear-time encodable and decodable error-correcting codes. 388-397
  
• Erich Kaltofen, Victor Shoup:
  Subquadratic-time factoring of polynomials over finite fields. 398-406
  
• Funda Ergün:
  Testing multivariate linear functions: overcoming the generator bottleneck. 407-416
  
• Arne Andersson, Johan Håstad, Ola Petersson:
  A tight lower bound for searching a sorted array. 417-426
  
• Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman:
  Sorting in linear time? 427-436
  
• Nabil Kahale, Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi:
  Lower bounds for sorting networks. 437-446
  
• Ran Raz:
  A parallel repetition theorem. 447-456
  
• Uriel Feige, Joe Kilian:
  Impossibility results for recycling random bits in two-prover proof systems. 457-468
  
• William Aiello, Mihir Bellare, Ramarathnam Venkatesan:
  Knowledge on the average-perfect, statistical and logarithmic. 469-478
  
• Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
  Explicit dispersers with polylog degree. 479-488
  
• Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel H. M. Smid:
  Euclidean spanners: short, thin, and lanky. 489-498
  
• Zvi Galil, Xiangdong Yu:
  Short length versions of Menger's theorem (Extended Abstract). 499-508
  
• Yefim Dinitz, Zeev Nutov:
  A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. 509-518
  
• Monika Rauch Henzinger, Valerie King:
  Randomized dynamic graph algorithms with polylogarithmic time per operation. 519-527
  
• Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg:
  Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract). 528-537
  
• Yehuda Afek, Dalia Dauber, Dan Touitou:
  Wait-free made fast (Extended Abstract). 538-547
  
• Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
  Tight analyses of two local load balancing algorithms. 548-558
  
• Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén:
  Log-space polynomial end-to-end communication. 559-568
  
• Mikael Goldmann, Johan Håstad:
  Monotone circuits for connectivity have depth (log n)^2-o(1) (Extended Abstract). 569-574
  
• Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
  Lower bounds for cutting planes proofs with small coefficients. 575-584
  
• Robert Beals, Tetsuro Nishino, Keisuke Tanaka:
  More on the complexity of negation-limited circuits. 585-595
  
• Ilan Kremer, Noam Nisan, Dana Ron:
  On randomized one-round communication complexity. 596-605
  
• Ran Canetti, Sandy Irani:
  Bounding the power of preemption in randomized scheduling. 606-615
  
• Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber:
  Bandwidth allocation with preemption. 616-625
  
• Amos Fiat, Anna R. Karlin:
  Randomized and multipointer paging with locality of reference. 626-634
  
• Uriel Feige:
  Randomized graph products, chromatic numbers, and Lovasz theta-function. 635-640
  
• Al Borchers, Ding-Zhu Du:
  The k-Steiner ratio in graphs. 641-649
  
• Thomas Raschle, Klaus Simon:
  Recognition of graphs with threshold dimension two. 650-661
  
• David Eppstein:
  Geometric lower bounds for parametric matroid optimization. 662-671
  
• Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos:
  Computing faces in segment and simplex arrangements (Preliminary Version). 672-682
  
• Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington:
  A Delaunay based numerical method for three dimensions: generation, formulation, and partition. 683-692
  
• Paolo Ferragina, Roberto Grossi:
  A fully-dynamic data structure for external substring search (Extended Abstract). 693-702
  
• Martin Farach, Mikkel Thorup:
  String matching in Lempel-Ziv compressed strings. 703-712
  
• Artur Czumaj, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Plandowski:
  Work-time-optimal parallel algorithms for string problems. 713-722
  
• Noam Nisan, Avi Wigderson:
  On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern. 723-732
  
• Bernard Chazelle:
  Lower bounds for off-line range searching. 733-740
  
• Victor Y. Pan:
  Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. 741-750
  
• John H. Reif:
  Work efficient parallel solution of Toeplitz systems and polynomial GCD. 751-761
  

Last update Tue May 21 00:46:31 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page