## Gary L. Miller

*Proceedings of the 28th Annual ACM Symposium on Theory of Computing*

STOC, 1996.

@proceedings{STOC-1996, address = "Philadelphia, Pennsylvania, USA", editor = "Gary L. Miller", isbn = "0-89791-785-5", publisher = "{ACM}", title = "{Proceedings of the 28th Annual ACM Symposium on Theory of Computing}", year = 1996, }

### Contents (74 items)

- STOC-1996-KushilevitzLO #communication #complexity
- The Linear-Array Conjecture in Communication Complexity is False (EK, NL, RO), pp. 1–10.
- STOC-1996-Hastad #clique #testing
- Testing of the Long Code and Hardness for Clique (JH), pp. 11–19.
- STOC-1996-AlonMS #approximate #complexity
- The Space Complexity of Approximating the Frequency Moments (NA, YM, MS), pp. 20–29.
- STOC-1996-ChaudhuriR #complexity #strict
- Deterministic Restrictions in Circuit Complexity (SC, JR), pp. 30–36.
- STOC-1996-CheriyanT #algorithm #performance
- Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation (JC, RT), pp. 37–46.
- STOC-1996-BenczurK #approximate
- Approximating s-t Minimum Cuts in Õ(n2) Time (AAB, DRK), pp. 47–55.
- STOC-1996-Karger
- Minimum Cuts in Near-Linear Time (DRK), pp. 56–63.
- STOC-1996-NagamochiI #graph
- Deterministic Õ(nm) Time Edge-Splitting in Undirected Graphs (HN, TI), pp. 64–73.
- STOC-1996-Naor #evaluation #generative
- Evaluation May Be Easier Than Generation (MN), pp. 74–83.
- STOC-1996-Ogihara
- The PL Hierarchy Collapses (MO), pp. 84–88.
- STOC-1996-AfekMO #algorithm #complexity #convergence
- Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (YA, YM, ZO), pp. 89–98.
- STOC-1996-Ajtai #generative #problem
- Generating Hard Instances of Lattice Problems (MA), pp. 99–108.
- STOC-1996-Milenkovic #linear #programming #strict #using
- Translational Polygon Containment and Minimal Enclosure using Linear Programming Based Restriction (VM), pp. 109–118.
- STOC-1996-BernS
- Pushing Disks Together — The Continuous-Motion Case (MWB, AS), pp. 119–125.
- STOC-1996-BergadanoCV #learning #query
- Learning Sat-k-DNF Formulas from Membership Queries (FB, DC, SV), pp. 126–130.
- STOC-1996-Bshouty #towards
- Towards the Learnability of DNF Formulae (NHB), pp. 131–140.
- STOC-1996-Cesa-BianchiDFS #bound #learning
- Noise-Tolerant Learning Near the Information-Theoretic Bound (NCB, ED, PF, HUS), pp. 141–150.
- STOC-1996-BshoutyGMST #concept #geometry #learning
- Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (NHB, SAG, HDM, SS, HT), pp. 151–160.
- STOC-1996-AllenderBO #complexity #equation #linear #matrix #rank
- The Complexity of Matrix Rank and Feasible Systems of Linear Equations (EA, RB, MO), pp. 161–167.
- STOC-1996-BasuPR #algebra #set
- Computing Roadmaps of Semi-Algebraic Sets (SB, RP, MFR), pp. 168–173.
- STOC-1996-CleggEI #algorithm #proving #satisfiability #using
- Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability (MC, JE, RI), pp. 174–183.
- STOC-1996-KapurS
- Sparsity Considerations in Dixon Resultants (DK, TS), pp. 184–191.
- STOC-1996-VengroffV #3d #memory management #performance
- Efficient 3-D Range Searching in External Memory (DEV, JSV), pp. 192–201.
- STOC-1996-KaplanT #functional
- Purely Functional Representations of Catenable Sorted Lists (HK, RET), pp. 202–211.
- STOC-1996-Grover #algorithm #database #performance #quantum
- A Fast Quantum Mechanical Algorithm for Database Search (LKG), pp. 212–219.
- STOC-1996-BonetPWY #polymorphism
- Constructing Evolutionary Trees in the Presence of Polymorphic Characters (MLB, CAP, TW, SY), pp. 220–229.
- STOC-1996-FarachK #algorithm #evolution #performance
- Efficient Algorithms for Inverting Evolution (MF, SK), pp. 230–236.
- STOC-1996-AspnesW #algorithm #composition #distributed
- Modular Competitiveness for Distributed Algorithms (JA, OW), pp. 237–246.
- STOC-1996-Goodrich #parallel #sorting
- Communication-Efficient Parallel Sorting (MTG), pp. 247–256.
- STOC-1996-AndrewsLMZ #automation #latency #network
- Automatic Methods for Hiding Latency in High Bandwidth Networks (MA, FTL, PTM, LZ), pp. 257–265.
- STOC-1996-Ma #fault tolerance #network #sorting
- An O(n log n)-Size Fault-Tolerant Sorting Network (YM), pp. 266–275.
- STOC-1996-Ta-Shma #on the #random
- On Extracting Randomness From Weak Random Sources (ATS), pp. 276–285.
- STOC-1996-Zuckerman
- Randomness-Optimal Sampling, Extractors, and Constructive Leader Election (DZ), pp. 286–295.
- STOC-1996-Wilson #generative #random
- Generating Random Spanning Trees More Quickly than the Cover Time (DBW), pp. 296–303.
- STOC-1996-DimitriouI #algorithm #analysis #optimisation #towards
- Towards an Analysis of Local Optimization Algorithms (TD, RI), pp. 304–313.
- STOC-1996-Feige #approximate #set
- A Threshold of ln n for Approximating Set Cover (UF), pp. 314–318.
- STOC-1996-McCormick #algorithm #parametricity #performance #scheduling
- Fast Algorithms for Parametric Scheduling Come from Extensions to Parametric Maximum Flow (STM), pp. 319–328.
- STOC-1996-KhannaM #towards
- Towards a Syntactic Characterization of PTAS (SK, RM), pp. 329–337.
- STOC-1996-KleinL #algorithm #approximate #performance #source code
- Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING (PNK, HIL), pp. 338–347.
- STOC-1996-BroderU #array
- Dynamic Deflection Routing on Arrays (AZB, EU), pp. 348–355.
- STOC-1996-CypherHSV #algorithm
- Universal Algorithms for Store-and-Forward and Wormhole Routing (RC, FMadH, CS, BV), pp. 356–365.
- STOC-1996-RabaniT #distributed #network
- Distributed Packet Switching in Arbitrary Networks (YR, ÉT), pp. 366–375.
- STOC-1996-BorodinKRSW
- Adversarial Queueing Theory (AB, JMK, PR, MS, DPW), pp. 376–385.
- STOC-1996-Friedman #combinator
- Computing Betti Numbers via Combinatorial Laplacians (JF), pp. 386–391.
- STOC-1996-Mohar #graph #linear
- Embedding Graphs in an Arbitrary Surface in Linear Time (BM), pp. 392–397.
- STOC-1996-DeyG #algorithm
- Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space (TKD, SG), pp. 398–407.
- STOC-1996-Basu #algebra #bound #on the #set
- On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets (SB), pp. 408–417.
- STOC-1996-KellererTW
- Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine (HK, TT, GJW), pp. 418–426.
- STOC-1996-Karloff #algorithm #how #question
- How Good is the Goemans-Williamson MAX CUT Algorithm? (HJK), pp. 427–434.
- STOC-1996-Slavik #algorithm #analysis #set
- A Tight Analysis of the Greedy Algorithm for Set Cover (PS), pp. 435–441.
- STOC-1996-BlumRV #algorithm #approximate #problem
- A Constant-factor Approximation Algorithm for the k MST Problem (AB, RR, SV), pp. 442–448.
- STOC-1996-BergerKL #3d #fault
- Reconstructing a Three-Dimensional Model with Arbitrary Errors (BB, JMK, FTL), pp. 449–458.
- STOC-1996-KearnsM #algorithm #learning #on the #top-down
- On the Boosting Ability of Top-Down Decision Tree Learning Algorithms (MJK, YM), pp. 459–468.
- STOC-1996-AngluinWZ #navigation #query
- Robot Navigation with Range Queries (DA, JW, WZ), pp. 469–478.
- STOC-1996-Beaver #complexity #correlation #pseudo
- Correlated Pseudorandomness and the Complexity of Private Computations (DB), pp. 479–488.
- STOC-1996-DworkLN #self
- Digital Signets: Self-Enforcing Protection of Digital Information (CD, JBL, MN), pp. 489–498.
- STOC-1996-FrankelGY #encryption #robust
- Witness-Based Cryptographic Program Checking and Robust Function Sharing (YF, PG, MY), pp. 499–508.
- STOC-1996-LinialS
- Non-Expansive Hashing (NL, OS), pp. 509–518.
- STOC-1996-AwerbuchAFL #how #nondeterminism
- Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (BA, YA, AF, FTL), pp. 519–530.
- STOC-1996-BartalFL #bound #graph #online #problem
- Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing (YB, AF, SL), pp. 531–540.
- STOC-1996-KushilevitzOR #linear #privacy
- Characterizing Linear Size Circuits in Terms of Privacy (EK, RO, AR), pp. 541–550.
- STOC-1996-HromkovicS #communication #nondeterminism
- Nondeterministic Communication with a Limited Number of Advice Bits (JH, GS), pp. 551–560.
- STOC-1996-NewmanS #communication #game studies
- Public vs. Private Coin Flips in One Round Communication Games (IN, MS), pp. 561–570.
- STOC-1996-RobertsonSST #graph
- Efficiently Four-Coloring Planar Graphs (NR, DPS, PDS, RT), pp. 571–575.
- STOC-1996-Spielman #graph #morphism #performance #testing
- Faster Isomorphism Testing of Strongly Regular Graphs (DAS), pp. 576–584.
- STOC-1996-AggarwalKW #layout #trade-off
- Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout (AA, JMK, DPW), pp. 585–594.
- STOC-1996-Fu #composition #proving
- Modular Coloring Formulas Are Hard for Cutting Planes Proofs (XF), pp. 595–602.
- STOC-1996-BabaiGKRSW #bound #graph #source code
- Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs (LB, AG, JK, LR, TS, AW), pp. 603–611.
- STOC-1996-GrigorievKHS #algebra #bound #random
- A Lower Bound for Randomized Algebraic Decision Trees (DG, MK, FMadH, RS), pp. 612–619.
- STOC-1996-EvansP #bound
- Lower Bounds for Noisy Boolean Decision Trees (WSE, NP), pp. 620–628.
- STOC-1996-Beaver96a #adaptation
- Adaptive Zero Knowledge and Computational Equivocation (DB), pp. 629–638.
- STOC-1996-CanettiFGN #adaptation #multi
- Adaptively Secure Multi-Party Computation (RC, UF, OG, MN), pp. 639–648.
- STOC-1996-Okamoto #on the #proving #statistics
- On Relationships between Statistical Zero-Knowledge Proofs (TO), pp. 649–658.
- STOC-1996-KosarajuD #assembly #scalability #string
- Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees (Correction) (SRK, ALD), p. 659.

15 ×#algorithm

7 ×#performance

6 ×#bound

6 ×#complexity

6 ×#graph

5 ×#approximate

4 ×#learning

4 ×#linear

4 ×#on the

4 ×#set

7 ×#performance

6 ×#bound

6 ×#complexity

6 ×#graph

5 ×#approximate

4 ×#learning

4 ×#linear

4 ×#on the

4 ×#set