## 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)

- 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.

12 ×#algorithm

8 ×#graph

7 ×#approximate

6 ×#bound

5 ×#complexity

5 ×#polynomial

4 ×#multi

4 ×#network

4 ×#on the

4 ×#performance

8 ×#graph

7 ×#approximate

6 ×#bound

5 ×#complexity

5 ×#polynomial

4 ×#multi

4 ×#network

4 ×#on the

4 ×#performance