25. STOC 1993
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993.
ACM 1993 BibTeX
@proceedings{DBLP:conf/stoc/STOC25,
title = {Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory
of Computing, 1993},
booktitle = {STOC},
publisher = {ACM},
year = {1993},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
- Arthur W. Chou, Ker-I Ko:
Some complexity issues on the simply connected regions of the two-dimensional plane.
1-10
Electronic Edition (ACM DL) BibTeX
- Ethan Bernstein, Umesh V. Vazirani:
Quantum complexity theory.
11-20
Electronic Edition (ACM DL) BibTeX
- Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, Wojciech H. Zurek:
Thermodynamics of computation and information distance.
21-30
Electronic Edition (ACM DL) BibTeX
- Juan A. Garay, Yoram Moses:
Fully polynomial Byzantine agreement in t+1 rounds.
31-41
Electronic Edition (ACM DL) BibTeX
- Ran Canetti, Tal Rabin:
Fast asynchronous Byzantine agreement with optimal resilience.
42-51
Electronic Edition (ACM DL) BibTeX
- Michael Ben-Or, Ran Canetti, Oded Goldreich:
Asynchronous secure computation.
52-61
Electronic Edition (ACM DL) BibTeX
- Tao Jiang, Ming Li:
k one-way heads cannot do string-matching.
62-70
Electronic Edition (ACM DL) BibTeX
- Brenda S. Baker:
A theory of parameterized pattern matching: algorithms and applications.
71-80
Electronic Edition (ACM DL) BibTeX
- Ramana M. Idury, Alejandro A. Schäffer:
Multiple matching of rectangular patterns.
81-90
Electronic Edition (ACM DL) BibTeX
- Elizabeth Borowsky, Eli Gafni:
Generalized FLP impossibility result for t-resilient asynchronous computations.
91-100
Electronic Edition (ACM DL) BibTeX
- Michael E. Saks, Fotios Zaharoglou:
Wait-free k-set agreement is impossible: the topology of public knowledge.
101-110
Electronic Edition (ACM DL) BibTeX
- Maurice Herlihy, Nir Shavit:
The asynchronous computability theorem for t-resilient tasks.
111-120
Electronic Edition (ACM DL) BibTeX
- Christos H. Papadimitriou, Mihalis Yannakakis:
Linear programming without the matrix.
121-129
Electronic Edition (ACM DL) BibTeX
- Ryan S. Borgstrom, S. Rao Kosaraju:
Comparison-based search in the presence of errors.
130-136
Electronic Edition (ACM DL) BibTeX
- Martin Farach, Sampath Kannan, Tandy Warnow:
A robust model for finding optimal evolutionary trees.
137-145
Electronic Edition (ACM DL) BibTeX
- Stefan Felsner, Lorenz Wernisch:
Maximum k-chains in planar point sets: combinatorial structure and algorithms.
146-153
Electronic Edition (ACM DL) BibTeX
- Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman:
Lower bounds for randomized mutual exclusion.
154-163
Electronic Edition (ACM DL) BibTeX
- Baruch Awerbuch, Yair Bartal, Amos Fiat:
Competitive distributed file allocation.
164-173
Electronic Edition (ACM DL) BibTeX
- Cynthia Dwork, Maurice Herlihy, Orli Waarts:
Contention in shared memory algorithms.
174-183
Electronic Edition (ACM DL) BibTeX
- Moni Naor, Larry J. Stockmeyer:
What can be computed locally?
184-193
Electronic Edition (ACM DL) BibTeX
- Robert F. Cohen, Giuseppe Di Battista, Arkady Kanevsky, Roberto Tamassia:
Reinventing the wheel: an optimal data structure for connectivity queries.
194-200
Electronic Edition (ACM DL) BibTeX
- Mario Szegedy, Sundar Vishwanathan:
Locality based graph coloring.
201-207
Electronic Edition (ACM DL) BibTeX
- David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer:
Separator based sparsification for dynamic planar graph algorithms.
208-217
Electronic Edition (ACM DL) BibTeX
- Leslie Ann Goldberg:
Polynomial space polynomial delay algorithms for listing families of graphs.
218-225
Electronic Edition (ACM DL) BibTeX
- Hans L. Bodlaender:
A linear time algorithm for finding tree-decompositions of small treewidth.
226-234
Electronic Edition (ACM DL) BibTeX
- Noam Nisan, David Zuckerman:
More deterministic simulation in logspace.
235-244
Electronic Edition (ACM DL) BibTeX
- Avi Wigderson, David Zuckerman:
Expanders that beat the eigenvalue bound: explicit construction and applications.
245-251
Electronic Edition (ACM DL) BibTeX
- Ravi B. Boppana, Babu O. Narayanan:
The biased coin problem.
252-257
Electronic Edition (ACM DL) BibTeX
- Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient construction of a small hitting set for combinatorial rectangles in high dimension.
258-267
Electronic Edition (ACM DL) BibTeX
- Daphne Koller, Nimrod Megiddo:
Constructing small sample spaces satisfying given constraints.
268-277
Electronic Edition (ACM DL) BibTeX
- Richard M. Karp:
Mapping the genome: some combinatorial problems arising in molecular biology.
278-285
Electronic Edition (ACM DL) BibTeX
- Carsten Lund, Mihalis Yannakakis:
On the hardness of approximating minimization problems.
286-293
Electronic Edition (ACM DL) BibTeX
- Mihir Bellare, Shafi Goldwasser, Carsten Lund, A. Russeli:
Efficient probabilistically checkable proofs and applications to approximations.
294-304
Electronic Edition (ACM DL) BibTeX
- Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor:
Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions.
305-314
Electronic Edition (ACM DL) BibTeX
- Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie:
Efficient learning of typical finite automata from random walks.
315-324
Electronic Edition (ACM DL) BibTeX
- Angus Macintyre, Eduardo D. Sontag:
Finiteness results for sigmoidal "neural" networks.
325-334
Electronic Edition (ACM DL) BibTeX
- Wolfgang Maass:
Bounds for the computational power and learning complexity of analog neural nets.
335-344
Electronic Edition (ACM DL) BibTeX
- Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, Donald A. Varvel:
Proportionate progress: a notion of fairness in resource allocation.
345-354
Electronic Edition (ACM DL) BibTeX
- Nicholas Pippenger:
Self-routing superconcentrators.
355-361
Electronic Edition (ACM DL) BibTeX
- Robert D. Blumofe, Charles E. Leiserson:
Space-efficient scheduling of multithreaded computations.
362-371
Electronic Edition (ACM DL) BibTeX
- Michael Kharitonov:
Cryptographic hardness of distribution-specific learning.
372-381
Electronic Edition (ACM DL) BibTeX
- Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, Manfred K. Warmuth:
How to use expert advice.
382-391
Electronic Edition (ACM DL) BibTeX
- Michael J. Kearns:
Efficient noise-tolerant learning from statistical queries.
392-401
Electronic Edition (ACM DL) BibTeX
- Steven Phillips, Jeffery Westbrook:
Online load balancing and network flow.
402-411
Electronic Edition (ACM DL) BibTeX
- Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber:
Markov chains, computer proofs, and average-case analysis of best fit bin packing.
412-421
Electronic Edition (ACM DL) BibTeX
- Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan:
On-line algorithms for cache sharing.
422-430
Electronic Edition (ACM DL) BibTeX
- Giuseppe Di Battista, Luca Vismara:
Angles of planar triangular graphs.
431-437
Electronic Edition (ACM DL) BibTeX
- R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III:
Many birds with one stone: multi-objective approximation algorithms.
438-447
Electronic Edition (ACM DL) BibTeX
- Michael Luby, Noam Nisan:
A parallel approximation algorithm for positive linear programming.
448-457
Electronic Edition (ACM DL) BibTeX
- Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan:
Randomness-optimal unique element isolation, with applications to perfect matching and related problems.
458-467
Electronic Edition (ACM DL) BibTeX
- Rudolf Fleischer:
Decision trees: old and new results.
468-477
Electronic Edition (ACM DL) BibTeX
- Jirí Matousek, Otfried Schwarzkopf:
A deterministic algorithm for the three-dimensional diameter problem.
478-484
Electronic Edition (ACM DL) BibTeX
- John Hershberger, Subhash Suri:
Matrix searching with the shortest path metric.
485-494
Electronic Edition (ACM DL) BibTeX
- Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, Emo Welzl:
Improved bounds on weak epsilon-nets for convex sets.
495-504
Electronic Edition (ACM DL) BibTeX
- Mark de Berg, Jirí Matousek, Otfried Schwarzkopf:
Piecewise linear paths among convex obstacles.
505-514
Electronic Edition (ACM DL) BibTeX
- Eric Allender, Jia Jiao:
Depth reduction for noncommutative arithmetic circuits.
515-522
Electronic Edition (ACM DL) BibTeX
- Pavel Pudlák, Vojtech Rödl:
Modified ranks of tensors and the size of circuits.
523-531
Electronic Edition (ACM DL) BibTeX
- Mauricio Karchmer, Avi Wigderson:
Characterizing non-deterministic circuit size.
532-540
Electronic Edition (ACM DL) BibTeX
- Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-depth trade-offs for threshold circuits.
541-550
Electronic Edition (ACM DL) BibTeX
- Mikael Goldmann, Marek Karpinski:
Simulating threshold circuits by majority circuits.
551-560
Electronic Edition (ACM DL) BibTeX
- Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman:
Multi-scale self-simulation: a technique for reconfiguring arrays with faults.
561-572
Electronic Edition (ACM DL) BibTeX
- Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal:
How much can hardware help routing?
573-582
Electronic Edition (ACM DL) BibTeX
- Noga Alon, Fan R. K. Chung, Ronald L. Graham:
Routing permutations on graphs via matchings.
583-591
Electronic Edition (ACM DL) BibTeX
- Rajeev Alur, Thomas A. Henzinger, Moshe Y. Vardi:
Parametric real-time reasoning.
592-601
Electronic Edition (ACM DL) BibTeX
- Neil D. Jones:
Constant time factors do matter.
602-611
Electronic Edition (ACM DL) BibTeX
- Tomás Feder, Moshe Y. Vardi:
Monotone monadic SNP and constraint satisfaction.
612-622
Electronic Edition (ACM DL) BibTeX
- James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, Orli Waarts:
On-line load balancing with applications to machine scheduling and virtual circuit routing.
623-631
Electronic Edition (ACM DL) BibTeX
- William Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao:
Approximate load balancing on dynamic and asynchronous networks.
632-641
Electronic Edition (ACM DL) BibTeX
- Anja Feldmann, Ming-Yang Kao, Jiri Sgall, Shang-Hua Teng:
Optimal online scheduling of parallel jobs with dependencies.
642-651
Electronic Edition (ACM DL) BibTeX
- Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese:
Time optimal self-stabilizing synchronization.
652-661
Electronic Edition (ACM DL) BibTeX
- Jason Cooper, Nathan Linial:
Fast perfection-information leader-election protocol with linear immunity.
662-671
Electronic Edition (ACM DL) BibTeX
- Charles Rackoff, Daniel R. Simon:
Cryptographic defense against traffic analysis.
672-681
Electronic Edition (ACM DL) BibTeX
- Philip N. Klein, Serge A. Plotkin, Satish Rao:
Excluded minors, network decomposition, and multicommodity flow.
682-690
Electronic Edition (ACM DL) BibTeX
- Serge A. Plotkin, Éva Tardos:
Improved bounds on the max-flow min-cut ratio for multicommodity flows.
691-697
Electronic Edition (ACM DL) BibTeX
- Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
Approximate max-flow min-(multi)cut theorems and their applications.
698-707
Electronic Edition (ACM DL) BibTeX
- David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani:
A primal-dual approximation algorithm for generalized Steiner network problems.
708-717
Electronic Edition (ACM DL) BibTeX
- Jeff Edmonds:
Time-space trade-offs for undirected st-connectivity on a JAG.
718-727
Electronic Edition (ACM DL) BibTeX
- Greg Barnes, Uriel Feige:
Short random walks on graphs.
728-737
Electronic Edition (ACM DL) BibTeX
- Claire Kenyon, Dana Randall, Alistair Sinclair:
Matchings in lattice graphs.
738-746
Electronic Edition (ACM DL) BibTeX
- Leonard J. Schulman:
Deterministic coding for interactive communication.
747-756
Electronic Edition (ACM DL) BibTeX
- David R. Karger, Clifford Stein:
An O~(n2) algorithm for minimum cuts.
757-765
Electronic Edition (ACM DL) BibTeX
- James K. Park, Cynthia A. Phillips:
Finding minimum-quotient cuts in planar graphs.
766-775
Electronic Edition (ACM DL) BibTeX
- Cynthia A. Phillips:
The network inhibition problem.
776-785
Electronic Edition (ACM DL) BibTeX
- Sigal Ar, Manuel Blum, Bruno Codenotti, Peter Gemmell:
Checking approximate computations over the reals.
786-795
Electronic Edition (ACM DL) BibTeX
- Adi Shamir:
On the generation of multivariate polynomials which are hard to factor.
796-804
Electronic Edition (ACM DL) BibTeX
- Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski:
Counting curves and their projections.
805-812
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:43:11 2009
by Michael Ley (ley@uni-trier.de)
