Proceedings of the 25th annual ACM symposium on theory of computing, STOC ’93. San Diego, CA, USA, May 16–18, 1993. (English) Zbl 1285.68003

New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-591-7). 812 p. (1993).

Show indexed articles as search result.

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

MSC:

68-06	Proceedings, conferences, collections, etc. pertaining to computer science
68Qxx	Theory of computing
00B25	Proceedings of conferences of miscellaneous specific interest

Citations:

Zbl 0836.00044