David S. Johnson, Uriel Feige
Proceedings of the 39th Annual ACM Symposium on Theory of Computing
STOC, 2007.

@proceedings{STOC-2007,
	address       = "San Diego, California, USA",
	editor        = "David S. Johnson and Uriel Feige",
	isbn          = "978-1-59593-631-8",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 39th Annual ACM Symposium on Theory of Computing}",
	year          = 2007,
}

Contents (78 items)

12 ×#algorithm
8 ×#graph
7 ×#approximate
6 ×#bound
5 ×#complexity
5 ×#polynomial
4 ×#multi
4 ×#network
4 ×#on the
4 ×#performance

STOC-2007-HaitnerR #statistics

Statistically-hiding commitment from any one-way function (IH, OR), pp. 1–10.

STOC-2007-Katz #multi #on the

On achieving the “best of both worlds” in secure multiparty computation (JK), pp. 11–20.

STOC-2007-IshaiKOS #multi

Zero-knowledge from secure multiparty computation (YI, EK, RO, AS), pp. 21–30.

STOC-2007-ChanP #diagrams

Voronoi diagrams in n·2osqrt(lg lg n) time (TMC, MP), pp. 31–39.

STOC-2007-Patrascu #2d #bound

Lower bounds for 2-dimensional range counting (MP), pp. 40–46.

STOC-2007-Basu #combinator #complexity #geometry

Combinatorial complexity in O-minimal geometry (SB), pp. 47–56.

STOC-2007-Furer #integer #multi #performance

Faster integer multiplication (MF), pp. 57–66.

STOC-2007-BjorklundHKK #fourier #performance #set

Fourier meets möbius: fast subset convolution (AB, TH, PK, MK), pp. 67–74.

STOC-2007-NissimRS #data analysis

Smooth sensitivity and sampling in private data analysis (KN, SR, AS), pp. 75–84.

STOC-2007-DworkMT #privacy

The price of privacy and the limits of LP decoding (CD, FM, KT), pp. 85–94.

STOC-2007-Kenyon-MathieuS #fault #how #rank

How to rank with few errors (CKM, WS), pp. 95–103.

STOC-2007-GuhaM #algorithm #approximate #learning #problem

Approximation algorithms for budgeted learning problems (SG, KM), pp. 104–113.

STOC-2007-AsadpourS #algorithm #approximate

An approximation algorithm for max-min fair allocation of indivisible goods (AA, AS), pp. 114–121.

STOC-2007-BayatiGKNT #algorithm #approximate

Simple deterministic approximation algorithms for counting matchings (MB, DG, DAK, CN, PT), pp. 122–127.

STOC-2007-MosselR #network #on the #social

On the submodularity of influence in social networks (EM, SR), pp. 128–134.

STOC-2007-BorgsCDR #analysis

First to market is not everything: an analysis of preferential attachment with fitness (CB, JTC, CD, SR), pp. 135–144.

STOC-2007-AndrewsJS #network #protocol #scheduling

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads (MA, KJ, ALS), pp. 145–154.

STOC-2007-AttiyaC #bound #random

Tight bounds for asynchronous randomized consensus (HA, KC), pp. 155–164.

STOC-2007-ChuzhoyGKT #graph

Hardness of routing with congestion in directed graphs (JC, VG, SK, KT), pp. 165–178.

STOC-2007-ChuzhoyK #polynomial #problem

Polynomial flow-cut gaps and hardness of directed cut problems (JC, SK), pp. 179–188.

STOC-2007-Austrin #satisfiability

Balanced max 2-sat might not be the hardest (PA), pp. 189–197.

STOC-2007-GuruswamiR #integer

A 3-query PCP over integers (VG, PR), pp. 198–206.

STOC-2007-DunaganH

Iteratively constructing preconditioners via the conjugate gradient method (JD, NJAH), pp. 207–216.

STOC-2007-KieferLE #convergence #equation #on the #polynomial

On the convergence of Newton’s method for monotone systems of polynomial equations (SK, ML, JE), pp. 217–226.

STOC-2007-AroraK #approach #combinator #source code

A combinatorial, primal-dual approach to semidefinite programs (SA, SK), pp. 227–236.

STOC-2007-GilbertSTV #algorithm #performance #sketching

One sketch for all: fast algorithms for compressed sensing (ACG, MJS, JAT, RV), pp. 237–246.

STOC-2007-Lynch #algorithm #distributed #modelling #proving

Distributed computing theory: algorithms, impossibility results, models, and proofs (NAL), p. 247.

STOC-2007-VuT #matrix

The condition number of a randomly perturbed matrix (VHV, TT), pp. 248–255.

STOC-2007-TalwarW

Balanced allocations: the weighted case (KT, UW), pp. 256–265.

STOC-2007-Yekhanin #towards

Towards 3-query locally decodable codes of subexponential length (SY), pp. 266–274.

STOC-2007-Santhanam #bound

Circuit lower bounds for Merlin-Arthur classes (RS), pp. 275–283.

STOC-2007-Shpilka #multi

Interpolation of depth-3 arithmetic circuits with two multiplication gates (AS), pp. 284–293.

STOC-2007-Sherstov

Separating AC0 from depth-2 majority circuits (AAS), pp. 294–301.

STOC-2007-SchoenebeckTT

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut (GS, LT, MT), pp. 302–310.

STOC-2007-Dantchev #complexity #proving #rank

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems (SSD), pp. 311–317.

STOC-2007-PaghPR #constant #independence #linear

Linear probing with constant independence (AP, RP, MR), pp. 318–327.

STOC-2007-FranceschiniM

Optimal suffix selection (GF, SM), pp. 328–337.

STOC-2007-DobzinskiN

Limitations of VCG-based mechanisms (SD, NN), pp. 338–344.

STOC-2007-HartM #communication #complexity #equilibrium #nash

The communication complexity of uncoupled nash equilibrium procedures (SH, YM), pp. 345–353.

STOC-2007-WuZ #equilibrium

Proportional response dynamics leads to market equilibrium (FW, LZ), pp. 354–363.

STOC-2007-JainV #algorithm

Eisenberg-Gale markets: algorithms and structural properties (KJ, VVV), pp. 364–373.

STOC-2007-HeggernesPTV

Interval completion with few edges (PH, CP, JAT, YV), pp. 374–381.

STOC-2007-KawarabayashiR #linear

Computing crossing number in linear time (KiK, BAR), pp. 382–390.

STOC-2007-AnshelevichK #3d #graph #polynomial

Terminal backup, 3D matching, and covering cubic graphs (EA, AK), pp. 391–400.

STOC-2007-CaiL #algorithm #artificial reality

Holographic algorithms: from art to science (JyC, PL), pp. 401–410.

STOC-2007-Holenstein #parallel

Parallel repetition: simplifications and the no-signaling case (TH), pp. 411–419.

STOC-2007-PassV #game studies #parallel #performance #theorem

An efficient parallel repetition theorem for Arthur-Merlin games (RP, MV), pp. 420–429.

STOC-2007-ShaltielU #trade-off

Low-end uniform hardness vs. randomness tradeoffs for AM (RS, CU), pp. 430–439.

STOC-2007-GoldwasserGHKR #constant #verification

Verifying and decoding in constant depth (SG, DG, AH, TK, GNR), pp. 440–449.

STOC-2007-HayesVV #graph

Randomly coloring planar graphs with fewer colors than the maximum degree (TPH, JCV, EV), pp. 450–458.

STOC-2007-GoldbergJ #polynomial

Inapproximability of the Tutte polynomial (LAG, MJ), pp. 459–468.

STOC-2007-HavivR #polynomial #problem

Tensor-based hardness of the shortest vector problem to within almost polynomial factors (IH, OR), pp. 469–477.

STOC-2007-PeikertR #worst-case

Lattices that admit logarithmic worst-case to average-case connection factors (CP, AR), pp. 478–487.

STOC-2007-RodlS #testing

Property testing in hypergraphs and the removal lemma (VR, MS), pp. 488–495.

STOC-2007-AlonAKMRX #independence #testing

Testing k-wise and almost k-wise independence (NA, AA, TK, KM, RR, NX), pp. 496–505.

STOC-2007-Samorodnitsky #scalability #testing

Low-degree tests at large distances (AS), pp. 506–515.

STOC-2007-GavinskyKKRW #communication #complexity #encryption #exponential #quantum

Exponential separations for one-way quantum communication complexity, with applications to cryptography (DG, JK, IK, RR, RdW), pp. 516–525.

STOC-2007-HoyerLS

Negative weights make adversaries stronger (PH, TL, RS), pp. 526–535.

STOC-2007-MooreRS #algorithm #graph #morphism #on the #quantum

On the impossibility of a quantum sieve algorithm for graph isomorphism (CM, AR, PS), pp. 536–545.

STOC-2007-KakadeKL #algorithm #approximate #game studies

Playing games with approximation algorithms (SMK, ATK, KL), pp. 546–555.

STOC-2007-EnglertRW #metric #order

Reordering buffers for general metric spaces (ME, HR, MW), pp. 556–564.

STOC-2007-GutoskiW #game studies #quantum #towards

Toward a general theory of quantum games (GG, JW), pp. 565–574.

STOC-2007-MagniezNRS #quantum

Search via quantum walk (FM, AN, JR, MS), pp. 575–584.

STOC-2007-VassilevskaWY #graph

All-pairs bottleneck paths for general graphs in truly sub-cubic time (VV, RW, RY), pp. 585–589.

STOC-2007-Chan #algorithm #graph

More algorithms for all-pairs shortest paths in weighted graphs (TMC), pp. 590–598.

STOC-2007-Pap

Some new results on node-capacitated packing of A-paths (GP), pp. 599–604.

STOC-2007-HariharanKPB #algorithm #graph

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs (RH, TK, DP, AB), pp. 605–614.

STOC-2007-Indyk #nondeterminism

Uncertainty principles, extractors, and explicit embeddings of l2 into l1 (PI), pp. 615–620.

STOC-2007-BrinkmanKL #graph #random #reduction

Vertex cuts, random walks, and dimension reduction in series-parallel graphs (BB, AK, JRL), pp. 621–630.

STOC-2007-AbrahamBN #metric

Local embeddings of metric spaces (IA, YB, ON), pp. 631–640.

STOC-2007-DeshpandeV #approximate #reduction

Sampling-based dimension reduction for subspace approximation (AD, KRV), pp. 641–650.

STOC-2007-LauNSS #constraints #design #network #order

Survivable network design with degree or order constraints (LCL, JN, MRS, MS), pp. 651–660.

STOC-2007-SinghL #approximate #bound

Approximating minimum bounded degree spanning trees to within one of optimal (MS, LCL), pp. 661–670.

STOC-2007-AgarwalAC #approximate #problem

Improved approximation for directed cut problems (AA, NA, MC), pp. 671–680.

STOC-2007-DonovanSVW #network

Degree-constrained network flows (PD, FBS, AV, GTW), pp. 681–688.

STOC-2007-BeameJR #algorithm #bound #random

Lower bounds for randomized read/write stream algorithms (PB, TSJ, AR), pp. 689–698.

STOC-2007-LinialS #bound #communication #complexity

Lower bounds in communication complexity based on factorization norms (NL, AS), pp. 699–708.

STOC-2007-BravermanY #set

Constructing non-computable Julia sets (MB, MY), pp. 709–716.