25. STOC 1993: San Diego, California, USA

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

Last update Wed May 22 16:42:02 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page