zbMATH — the first resource for mathematics

Proceedings of the 28th annual ACM symposium on the theory of computing, STOC ’96. Philadelphia, PA, USA, May 22–24, 1996. (English) Zbl 0908.00030
New York, NY: ACM, x, 661 p. (1996).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding symposium (27th, 1995) has been reviewed (see Zbl 0908.00026).
Indexed articles:
Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail, The linear-array conjecture in communication complexity is false, 1-10 [Zbl 0932.94042]
Håstad, Johan, Testing of the long code and hardness for clique, 11-19 [Zbl 0922.68066]
Alon, Noga; Matias, Yossi; Szegedy, Mario, The space complexity of approximating the frequency moments, 20-29 [Zbl 0922.68057]
Chaudhuri, Shiva; Radhakrishnan, Jaikumar, Deterministic restrictions in circuit complexity, 30-36 [Zbl 0932.94041]
Cheriyan, Joseph; Thurimella, Ramakrishna, Fast algorithms for \(k\)-shredders and \(k\)-node connectivity augmentation. (Extended abstract), 37-46 [Zbl 0924.68100]
Benczúr, András A.; Karger, David R., Approximating \(s\)-\(t\) minimum cuts in \(\widetilde O(n^2)\) time, 47-55 [Zbl 0924.68150]
Karger, David R., Minimum cuts in near-linear time, 56-63 [Zbl 0922.68089]
Nagamochi, Hiroshi; Ibaraki, Toshihide, Deterministic \(\widetilde O(nm)\) time edge-splitting in undirected graphs, 64-73 [Zbl 0917.90280]
Naor, Moni, Evaluation may be easier than generation. (Extended abstract), 74-83 [Zbl 0936.68083]
Ogihara, Mitsunori, The PL hierachy collapses, 84-88 [Zbl 0922.68054]
Afek, Yehuda; Mansour, Yishay; Ostfeld, Zvi, Convergence complexity of optimistic rate based flow control algorithms. (Extended abstract), 89-98 [Zbl 0915.90102]
Ajtai, M., Generating hard instances of lattice problems. (Extended abstract), 99-108 [Zbl 0921.11071]
Milenkovic, Victor J., Translational polygon containment and minimal enclosure using linear programming based restriction, 109-118 [Zbl 0922.68129]
Bern, Marshall; Sahai, Amit, Pushing disks together. The continuous-motion case, 119-125 [Zbl 0917.52001]
Bergadano, F.; Catalano, D.; Varricchio, S., Learning Sat-\(k\)-DNF formulas from membership queries, 126-130 [Zbl 0924.68168]
Bshouty, Nader H., Towards the learnability of DNF formulae, 131-140 [Zbl 0922.68101]
Cesa-Bianchi, Nicolò; Dichterman, Eli; Fischer, Paul; Simon, Hans Ulrich, Noise-tolerant learning near the information-theoretic bound, 141-150 [Zbl 0922.68102]
Bshouty, Nader H.; Goldman, Sally A.; Mathias, H. David; Suri, Subhash; Tamaki, Hisao, Noise-tolerant distribution-free learning of general geometric concepts, 151-160 [Zbl 0936.68084]
Allender, Eric; Beals, Robert; Ogihara, Mitsunori, The comlexity of matrix rank and feasible systems of linear equations. (Extended abstract), 161-167 [Zbl 0937.65150]
Basu, S.; Pollack, R.; Roy, M.-F., Computing roadmaps of semi-algebraic sets. (Extended abstract), 168-173 [Zbl 0917.14028]
Clegg, Matthew; Edmonds, Jeffery; Impagliazzo, Russell, Using the Groebner basis algorithm to find proofs of unsatisfiability, 174-183 [Zbl 0938.68825]
Kapur, Deepak; Saxena, Tushar, Sparsity considerations in Dixon resultants, 184-191 [Zbl 0914.65055]
Vengroff, Darren Erik; Vitter, Jeffrey Scott, Efficient 3-D range searching in external memory, 192-201 [Zbl 0922.68042]
Kaplan, Haim; Tarjan, Robert E., Purely functional representations of catenable sorted lists, 202-211 [Zbl 0922.68043]
Grover, Lov K., A fast quantum mechanical algorithm for database search, 212-219 [Zbl 0922.68044]
Bonet, Maria; Phillips, Cynthia; Warnow, Tandy J.; Yooseph, Shibu, Constructing evolutionary trees in the presence of polymorphic characters, 220-229 [Zbl 0936.68024]
Farach, Martin; Kannan, Sampath, Efficient algorithms for inverting evolution, 230-236 [Zbl 0911.92020]
Aspnes, James; Waarts, Orli, Modular competitiveness for distributed algorithms, 237-246 [Zbl 0922.68070]
Goodrich, Michael T., Communication-efficient parallel sorting. (Preliminary version), 247-256 [Zbl 0924.68062]
Andrews, Matthew; Leighton, Tom; Metaxas, P. Takis; Zhang, Lisa, Automatic methods for hiding latency in high bandwidth networks. (Extended abstract), 257-265 [Zbl 0924.68015]
Ma, Yuan, An \(O(n\log n)\)-size fault-tolerant sorting network. (Extended abstract), 266-275 [Zbl 0924.68011]
Ta-Shma, Amnon, On extracting randomness from weak random sources. (Extended abstract), 276-285 [Zbl 0924.68210]
Zuckerman, David, Randomness-optimal sampling, extractors, and constructive leader election, 286-295 [Zbl 0922.68143]
Wilson, David Bruce, Generating random spanning trees more quickly than the cover time, 296-303 [Zbl 0946.60070]
Dimitriou, Tassos; Impagliazzo, Russell, Towards an analysis of local optimization algorithms, 304-313 [Zbl 0915.65065]
Feige, Uriel, A threshold of \(\ln n\) for approximating set cover, 314-318 [Zbl 0922.68067]
McCormick, S. Thomas, Fast algorithms for parametric scheduling come from extensions to parametric maximum flow, 319-328 [Zbl 0936.68013]
Khanna, Sanjeev; Motwani, Rajeev, Towards and syntactic characterization of PTAS, 329-337 [Zbl 0922.68058]
Klein, Philip; Lu, Hsueh-I, Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING, 338-347 [Zbl 0936.68072]
Broder, Andrei; Upfal, Eli, Dynamic reflection routing on arrays, 348-355 [Zbl 0924.68016]
Cypher, Robert; Meyer auf der Heide, Friedhelm; Scheideler, Christian; Vöcking, Berthold, Universal algorithms for store-and-forward and wormhole routing, 356-365 [Zbl 0922.68013]
Rabani, Yuval; Tardos, Éva, Distributed packet switching in arbitrary networks, 366-375 [Zbl 0936.68010]
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P., Adversarial queueing theory, 376-384 [Zbl 0934.60079]
Friedman, Joel, Computing Betti numbers via combinatorial Laplacians, 386-391 [Zbl 0917.57019]
Mohar, Bojan, Embedding graphs in an arbitrary surface in linear time, 392-397 [Zbl 0917.05024]
Dey, Tamal K.; Guha, Sumanta, Algorithms for manifolds and simplicial complexes in Euclidean 3-space. (Preliminary version), 398-405 [Zbl 0913.57012]
Basu, Saugata, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, 408-415 [Zbl 0917.14029]
Kellerer, Hans; Tautenhahn, Thomas; Woeginger, Gerhard J., Approximability and nonapproximability results for minimizing total flow time on a single machine, 418-426 [Zbl 0915.90151]
Karloff, Howard, How good is the Goemans-Williamson MAX CUT algorithm?, 427-434 [Zbl 0922.68068]
Slavík, Petr, A tight analysis of the greedy algorithm for set cover, 435-439 [Zbl 0942.68773]
Blum, Avrim; Ravi, R.; Vempala, Santosh, A constant-factor approximation algorithm for the \(k\)-MST problem. (Extended abstract), 442-448 [Zbl 0924.68151]
Berger, Bonnie; Kleinberg, Jon; Leighton, Tom, Reconstructing a three-dimensional model with arbitrary errors, 449-458 [Zbl 0922.68072]
Kearns, Michael; Mansour, Yishay, On the boosting ability of top-down decision tree learning algorithms, 459-466 [Zbl 0915.68142]
Angluin, Dana; Westbrook, Jeffery; Zhu, Wenhong, Robot navigation with range queries, 469-478 [Zbl 0925.93673]
Beaver, Donald, Correlated pseudorandomness and the complexity of private computations, 479-488 [Zbl 0917.94012]
Dwork, Cynthia; Lotspiech, Jeffrey; Naor, Moni, Digital signets: Self-enforcing protection of digital information (preliminary version), 489-498 [Zbl 0917.94013]
Frankel, Yair; Gemmell, Peter; Yung, Moti, Witness-based cryptographic program checking and robust function sharing, 499-508 [Zbl 0932.94031]
Linial, Nathan; Sasson, Ori, Non-expansive hashing, 509-518 [Zbl 0922.68047]
Awerbuch, Baruch; Azar, Yossi; Fiat, Amos; Leighton, Tom, Making commitments in the face of uncertainty: How to pick a winner almost every time. (Extended abstract), 519-530 [Zbl 0922.68019]
Bartal, Yair; Fiat, Amos; Leonardi, Stefano, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, 531-540 [Zbl 0936.68073]
Kushilevitz, Eyal; Ostrovsky, Rafail; Rosén, Adi, Characterizing linear size circuits in terms of privacy, 541-550 [Zbl 0922.68059]
Hromkovic, J.; Schnitger, G., Nondeterministic communication with a limited number of advice bits, 551-560 [Zbl 0922.68060]
Newman, Ilan; Szegedy, Mario, Public vs. private coin flips in one round communication games. (Extended abstract), 561-570 [Zbl 0936.68050]
Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin, Efficiently four-coloring planar graphs, 571-575 [Zbl 0917.05030]
Spielman, Daniel A., Faster isomorphism testing of strongly regular graphs, 576-584 [Zbl 0915.05104]
Aggarwal, Alok; Kleinberg, Jon; Williamson, David P., Node-disjoint paths on the mesh and a new trade-off in VLSI layout, 585-594 [Zbl 0936.68117]
Fu, Xudong, Modular coloring formulas are hard for cutting planes proofs, 595-602 [Zbl 0922.68112]
Babai, László; Gál, Anna; Kollár, János; Rónyai, Lajos; Szabó, Tibor; Wigderson, Avi, Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs, 603-611 [Zbl 0915.05076]
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman, A lower bound for randomized algebraic decision trees, 612-619 [Zbl 0922.68090]
Evans, William; Pippenger, Nicholas, Lower bounds for noisy Boolean decision trees., 620-623 [Zbl 1125.94349]
Beaver, Donald, Adaptive zero knowledge and computational equivocation. (Extended abstract), 629-638 [Zbl 0936.68037]
Canetti, Ran; Feige, Uri; Goldreich, Oded; Naor, Moni, Adaptively secure multi-party computation, 639-646 [Zbl 0922.68048]
Okamoto, Tatsuaki, On relationships between statistical zero-knowledge proofs, 649-658 [Zbl 0922.68049]

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