BibSLEIGH — Proceedings of the 47th Annual ACM Symposium on Theory of Computing

Rocco A. Servedio, Ronitt Rubinfeld
Proceedings of the 47th Annual ACM Symposium on Theory of Computing
STOC, 2015.

TCS

@proceedings{STOC-2015,
	acmid         = "2746539",
	address       = "Portland, Oregon, USA",
	editor        = "Rocco A. Servedio and Ronitt Rubinfeld",
	isbn          = "978-1-4503-3536-2",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 47th Annual ACM Symposium on Theory of Computing}",
	year          = 2015,
}

Contents (93 items)

STOC-2015-Chechik #approximate #bound #distance: Approximate Distance Oracles with Improved Bounds (SC), pp. 1–10.
STOC-2015-LackiOPSZ #algorithm #distance #performance #power of: The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree (JL, JO, MP, PS, AZ), pp. 11–20.
STOC-2015-HenzingerKNS #multi #online #problem: Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (MH, SK, DN, TS), pp. 21–30.
STOC-2015-ChanL #clustering #combinator #integer: Clustered Integer 3SUM via Additive Combinatorics (TMC, ML), pp. 31–40.
STOC-2015-AbboudWY: Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (AA, VVW, HY), pp. 41–50.
STOC-2015-BackursI #distance #edit distance: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (AB, PI), pp. 51–58.
STOC-2015-DingSS #proving #satisfiability #scalability: Proof of the Satisfiability Conjecture for Large k (JD, AS, NS), pp. 59–68.
STOC-2015-MosselNS #consistency: Consistency Thresholds for the Planted Bisection Model (EM, JN, AS), pp. 69–75.
STOC-2015-FeldmanPV #complexity #on the #problem #random #satisfiability: On the Complexity of Random Satisfiability Problems with Planted Solutions (VF, WP, SV), pp. 77–86.
STOC-2015-MekaPW #bound #clique: Sum-of-squares Lower Bounds for Planted Clique (RM, AP, AW), pp. 87–96.
STOC-2015-BarakCK #bound #independence: Sum of Squares Lower Bounds from Pairwise Independence (BB, SOC, PKK), pp. 97–106.
STOC-2015-BraunPZ #combinator #problem: Inapproximability of Combinatorial Problems via Small LPs and SDPs (GB, SP, DZ), pp. 107–116.
STOC-2015-DworkFHPRR #adaptation #data analysis #statistics: Preserving Statistical Validity in Adaptive Data Analysis (CD, VF, MH, TP, OR, ALR), pp. 117–126.
STOC-2015-BassilyS #performance #protocol: Local, Private, Efficient Protocols for Succinct Histograms (RB, ADS), pp. 127–135.
STOC-2015-LovettZ #difference: Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions (SL, JZ), pp. 137–142.
STOC-2015-BarakKS #composition #learning #taxonomy: Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method (BB, JAK, DS), pp. 143–151.
STOC-2015-MirrokniZ #composition #distributed #random: Randomized Composable Core-sets for Distributed Submodular Maximization (VSM, MZ), pp. 153–162.
STOC-2015-CohenEMMP #approximate #clustering #rank #reduction: Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (MBC, SE, CM, CM, MP), pp. 163–172.
STOC-2015-BhattacharyaHNT #algorithm #maintenance: Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams (SB, MH, DN, CET), pp. 173–182.
STOC-2015-CohenP: Lp Row Sampling by Lewis Weights (MBC, RP), pp. 183–192.
STOC-2015-BansalGG #graph #independence #on the #set: On the Lovász Theta function for Independent Sets in Sparse Graphs (NB, AG, GG), pp. 193–200.
STOC-2015-FearnleyS #complexity: The Complexity of the Simplex Method (JF, RS), pp. 201–208.
STOC-2015-HansenZ #algorithm: An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm (TDH, UZ), pp. 209–218.
STOC-2015-ChawlaMSY #algorithm #clustering #graph: Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs (SC, KM, TS, GY), pp. 219–228.
STOC-2015-ZhuO #convergence #performance: Nearly-Linear Time Positive LP Solver with Faster Convergence Rate (ZAZ, LO), pp. 229–236.
STOC-2015-ZhuLO #matrix #multi: Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates (ZAZ, ZL, LO), pp. 237–245.
STOC-2015-KothariM #generative #pseudo: Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract (PKK, RM), pp. 247–256.
STOC-2015-GoosLM0Z: Rectangles Are Nonnegative Juntas (MG, SL, RM, TW, DZ), pp. 257–266.
STOC-2015-DinurHK #composition #fault #query: Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition (ID, PH, GK), pp. 267–276.
STOC-2015-BhowmickL: The List Decoding Radius of Reed-Muller Codes over Small Fields (AB, SL), pp. 277–285.
STOC-2015-ChenJL #capacity #online: A Characterization of the Capacity of Online (causal) Binary Channels (ZC, SJ, ML), pp. 287–296.
STOC-2015-AbbeSW #fault #random: Reed-Muller Codes for Random Erasures and Errors (EA, AS, AW), pp. 297–306.
STOC-2015-AaronsonA #named #problem #quantum: Forrelation: A Problem that Optimally Separates Quantum from Classical Computing (SA, AA), pp. 307–316.
STOC-2015-Touchette #complexity #quantum: Quantum Information Complexity (DT), pp. 317–326.
STOC-2015-BaconFHS #quantum: Sparse Quantum Codes from Quantum Circuits (DB, STF, AWH, JS), pp. 327–334.
STOC-2015-BravermanG #game studies #parallel: Small Value Parallel Repetition for General Games (MB, AG), pp. 335–340.
STOC-2015-BravermanW #interactive: An Interactive Information Odometer and Applications (MB, OW), pp. 341–350.
STOC-2015-GowersV #communication #complexity: The communication complexity of interleaved group products (TG, EV), pp. 351–360.
STOC-2015-Barman #approximate #nash #theorem: Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory’s Theorem (SB), pp. 361–369.
STOC-2015-ColeG #approximate #nash #social: Approximating the Nash Social Welfare with Indivisible Items (RC, VG), pp. 371–380.
STOC-2015-ChenDO #complexity #game studies #nash #on the: On the Complexity of Nash Equilibria in Anonymous Games (XC, DD, AO), pp. 381–390.
STOC-2015-Lee #graph: Hardness of Graph Pricing Through Generalized Max-Dicut (EL), pp. 391–399.
STOC-2015-DanielySS: Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension (AD, MS, GS), pp. 401–408.
STOC-2015-Rubinstein #equilibrium #nash: Inapproximability of Nash Equilibrium (AR), pp. 409–418.
STOC-2015-KoppulaLW #bound #memory management #obfuscation #turing machine: Indistinguishability Obfuscation for Turing Machines with Unbounded Memory (VK, ABL, BW), pp. 419–428.
STOC-2015-CanettiH0V #obfuscation #ram #source code: Succinct Garbling and Indistinguishability Obfuscation for RAM Programs (RC, JH, AJ, VV), pp. 429–437.
STOC-2015-BitanskyGLPT #encoding #random: Succinct Randomized Encodings and their Applications (NB, SG, HL, RP, ST), pp. 439–448.
STOC-2015-GargLOS #ram: Garbled RAM From One-Way Functions (SG, SL, RO, AS), pp. 449–458.
STOC-2015-AggarwalDKO #reduction: Non-malleable Reductions and Applications (DA, YD, TK, MO), pp. 459–468.
STOC-2015-GorbunovVW #standard: Leveled Fully Homomorphic Signatures from Standard Lattices (SG, VV, DW), pp. 469–477.
STOC-2015-AndoniKR #sketching: Sketching and Embedding are Equivalent for Norms (AA, RK, IPR), pp. 479–488.
STOC-2015-ElkinFN #metric: Prioritized Metric Structures and Embedding (ME, AF, ON), pp. 489–498.
STOC-2015-BourgainDN #formal method #reduction #towards: Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space (JB, SD, JN), pp. 499–508.
STOC-2015-AbdullahV #bound #difference: A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds (AA, SV), pp. 509–518.
STOC-2015-ChenDST #adaptation #query #testing: Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries (XC, AD, RAS, LYT), pp. 519–528.
STOC-2015-ODonnellW #quantum #testing: Quantum Spectrum Testing (RO, JW), pp. 529–538.
STOC-2015-CousinsV #algorithm: Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (BC, SV), pp. 539–548.
STOC-2015-LiuL #bound: FPTAS for #BIS with Degree Bounds on One Side (JL, PL), pp. 549–556.
STOC-2015-GanorKR #communication #exponential: Exponential Separation of Information and Communication for Boolean Functions (AG, GK, RR), pp. 557–566.
STOC-2015-LeeRS #bound #programming: Lower Bounds on the Size of Semidefinite Programming Relaxations (JRL, PR, DS), pp. 567–576.
STOC-2015-DvirG #communication: 2-Server PIR with Sub-Polynomial Communication (ZD, SG), pp. 577–584.
STOC-2015-AmbainisFG #matrix #multi #performance: Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method (AA, YF, FLG), pp. 585–593.
STOC-2015-AlwenS #complexity #graph #parallel: High Parallel Complexity Graphs and Memory-Hard Functions (JA, VS), pp. 595–603.
STOC-2015-AbrahamD #complexity #polynomial: Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.
STOC-2015-GiakkoupisHHW: Test-and-Set in Optimal Space (GG, MH, LH, PW), pp. 615–623.
STOC-2015-AlstrupKTZ #graph: Adjacency Labeling Schemes and Induced-Universal Graphs (SA, HK, MT, UZ), pp. 625–634.
STOC-2015-HalldorssonT #graph #how #question: How Well Can Graphs Represent Wireless Interference? (MMH, TT), pp. 635–644.
STOC-2015-Chuzhoy #grid #theorem: Excluded Grid Theorem: Improved and Simplified (JC), pp. 645–654.
STOC-2015-KawarabayashiK #grid #theorem: The Directed Grid Theorem (KiK, SK), pp. 655–664.
STOC-2015-KawarabayashiT #graph: Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time (KiK, MT), pp. 665–674.
STOC-2015-KawarabayashiS #approximate #graph: Beyond the Euler Characteristic: Approximating the Genus of General Graphs (KiK, AS), pp. 675–682.
STOC-2015-GroheS: Computing with Tangles (MG, PS), pp. 683–692.
STOC-2015-SunW #canonical #performance: Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract (XS, JW), pp. 693–702.
STOC-2015-Czumaj #network #permutation #random #using: Random Permutations using Switching Networks (AC), pp. 703–712.
STOC-2015-Louis #algorithm #approximate #markov: Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms (AL), pp. 713–722.
STOC-2015-CzumajPS #clustering #graph #testing: Testing Cluster Structure of Graphs (AC, PP, CS), pp. 723–732.
STOC-2015-AggarwalDRS #problem #using: Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract (DA, DD, OR, NSD), pp. 733–742.
STOC-2015-LiRSS #learning #statistics: Learning Arbitrary Statistical Mixtures of Discrete Distributions (JL, YR, LJS, CS), pp. 743–752.
STOC-2015-HardtP #bound #learning: Tight Bounds for Learning a Mixture of Two Gaussians (MH, EP), pp. 753–760.
STOC-2015-GeHK #learning: Learning Mixtures of Gaussians in High Dimensions (RG, QH, SMK), pp. 761–770.
STOC-2015-Bresler #graph #learning #modelling: Efficiently Learning Ising Models on Arbitrary Graphs (GB), pp. 771–782.
STOC-2015-MulzerNSS #approximate #nearest neighbour: Approximate k-flat Nearest Neighbor Search (WM, HLN, PS, YS), pp. 783–792.
STOC-2015-AndoniR #approximate: Optimal Data-Dependent Hashing for Approximate Near Neighbors (AA, IR), pp. 793–801.
STOC-2015-LarsenNN #adaptation #algorithm #bound #streaming: Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms (KGL, JN, HLN), pp. 803–812.
STOC-2015-ChristianiPT #independence: From Independence to Expansion and Back Again (TC, RP, MT), pp. 813–820.
STOC-2015-Moitra #matrix: Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices (AM), pp. 821–830.
STOC-2015-SchulmanS #algorithm #analysis #matrix: Analysis of a Classical Matrix Preconditioning Algorithm (LJS, AS), pp. 831–840.
STOC-2015-FoxKM #approximate #polynomial: A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection (KF, PNK, SM), pp. 841–850.
STOC-2015-BansalK: Minimizing Flow-Time on Unrelated Machines (NB, JK), pp. 851–860.
STOC-2015-Nikolov #problem #random: Randomized Rounding for the Largest Simplex Problem (AN), pp. 861–870.
STOC-2015-Gupta0 #algorithm: Greedy Algorithms for Steiner Forest (AG, AK), pp. 871–878.
STOC-2015-KesselheimKN #order #problem: Secretary Problems with Non-Uniform Arrival Order (TK, RDK, RN), pp. 879–888.
STOC-2015-KorulaMZ #online #order #random: Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order (NK, VSM, MZ), pp. 889–898.

Rocco A. Servedio, Ronitt RubinfeldProceedings of the 47th Annual ACM Symposium on Theory of ComputingSTOC, 2015.

Contents (93 items)

Rocco A. Servedio, Ronitt Rubinfeld
Proceedings of the 47th Annual ACM Symposium on Theory of Computing
STOC, 2015.