Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Die bibliographische Datenbank LEABib

Suchen • Liste der Journale • Liste der Serien • Liste der Konferenzen • Ausgewählte Publikationen	Hilfe

Suche: Booktitle=Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986)

• Bounded-width polynomial-size branching programs recognize exactly those languages in NC^1
  D.A. Barrington
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 1-5
• Almost optimal lower bounds for small depth circuits
  J. Håstad
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 6-20
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
  J.-Y. Cai
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 21-29
• Two lower bounds for branching programs
  M. Ajtai, L. Babai, P. Hajnal, J. Komlós, P. Pudlak, V. Rodl, E. Szemerédi, G. Turan
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 30-38
• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
  Z. Galil, R. Kannan, E. Szemerédi
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 39-49
• How hard is it to marry at random? (On the approximation of the permanent)
  A.Z. Broder
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 50-58
• Private coins versus public coins in interactive proof systems
  S. Goldwasser, M. Sipser
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 59-68
• The complexity of optimization problems
  M.W. Krentel
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 69-76
• A provably efficient algorithm for dynamic storage allocation
  E.G., Jr. Coffman, F.T. Leighton
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 77-90
• Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms
  F.T. Leighton, P. Shor
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 91-103
• Four pages are necessary and sufficient for planar graphs
  M. Yannakakis
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 104-108
• Making data structures persistent
  J.R. Driscoll, N. Sarnak, D.D. Sleator, R.E. Tarjan
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 109-121
• Rotation distance, triangulations, and hyperbolic geometry
  D.D. Sleator, R.E. Tarjan, W.P. Thurston
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 122-135
• A new approach to the maximum flow problem
  A.V. Goldberg, R.E. Tarjan
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 136-146
• Fast algorithms for convex quadratic programming and multicommodity flows
  S. Kapoor, P.M. Vaidya
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 147-159
• Parallel hashing - An efficient implementation of shared memory
  A.R. Karlin, E. Upfal
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 160-168
• Limits on the power of concurrent-write parallel machines
  P. Beame
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 169-176
• New lower bounds for parallel computation
  M. Li, Y. Yesha
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 177-187
• Deterministic selection in O(\log\log N) parallel time
  M. Ajtai, J. Komlós, W.L. Steiger, E. Szemerédi
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 188-195
• Linear programming with two variables per inequality in poly-log time
  G.S. Lueker, N. Megiddo, V. Ramachandran
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 196-205
• Deterministic coin tossing and accelerating cascades: Micro and macro techniques for designing parallel algorithms
  R. Cole, U. Vishkin
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 206-219
• Introducing efficient parallelism into approximate string matching and a new serial algorithm
  G.M. Landau, U. Vishkin
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 220-230
• Parallel evaluation of division-free arithmetic expressions
  S.R. Kosaraju
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 231-239
• Explicit expanders and the Ramanujan conjectures
  A. Lubotzky, R. Phillips, P. Sarnak
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 240-246
• Non-blocking networks
  P. Feldman, J. Friedman, N. Pippenger
  Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC'86 (Berkeley, CA, May 28-30, 1986), 1986, pp. 247-254