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)

15 ×#algorithm
7 ×#performance
6 ×#bound
6 ×#complexity
6 ×#graph
5 ×#approximate
4 ×#learning
4 ×#linear
4 ×#on the
4 ×#set

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.