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