| ||||
Accepted Papers L_p metrics on the Heisenberg group and the Goemans-Linial conjecture A Geometric Generalization of the Upper Bound Theorem A generalization of the Dobrushin uniqueness condition and applications to MCMC sampling A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks Accidental Algorithms Algebraic Structures and Algorithms for Matching and Matroid Problems Algorithms on negatively curved spaces An O(2^n) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion-Exclusion An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems Approximation algorithms for allocation problems: Improving the factor of 1-1/e Balanced Allocations of Cake Better lossless condensers through derandomized curve samplers Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method Bounded Degree Minimum Spanning Trees Computing Nash Equilibria: Approximation and Smoothed Complexity Concurrent Non-Malleable Zero Knowledge Coresets for Weighted Facilities and Their Applications Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets Cryptographic Hardness Results for Learning Intersections of Halfspaces Cryptography from Anonymity Dispersion of Mass and the Complexity of Randomized Algorithms Explicit Exclusive Set Systems with Cryptographic Applications Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths Fault-Tolerant Distributed Computing in Full-Information Networks Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders Hardness of Learning Halfspaces with Noise Heat flow and a faster algorithm to compute the surface area of a convex body Higher Lower Bounds for Near-Neighbor and Further Rich Problems How to Play any Unique Game Improved Approximation Algorithms for Large Matrices via Random Projections Improved Bounds for Online Routing and Packing via a Primal-Dual Approach Improved Dynamic Planar Point Location Improved approximation algorithms for multidimensional bin packing problems Inclusion-Exclusion Algorithms for Counting Set Partitions Index Coding with Side Information Input-Indistinguishable Computation List-decoding direct product codes and uniform hardness amplification Local Graph Partitioning using PageRank Vectors Local Peering and Service Contracts in Strategic Network Formation Lower Bounds for Additive Spanners, Emulators, and More Lower bounds for circuits with MOD_m gates Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions New Results for Learning Noisy Parities and Halfspaces New limits on fault-tolerant quantum computation Norm of the inverse of a random matrix On the Compressibility of NP Instances and Cryptographic Applications On the Impact of Combinatorial Structure on Congestion Games On the Optimality of the Dimensionality Reduction Method On the Quantum Query Complexity of Local Search in Two and Three Dimensions On the time complexity of 2-tag systems and small universal Turing machines Planar Earthmover is not in L_1 Planar Point Location in Sublogarithmic Time Point Location in o(log n) Time, Voronoi diagrams in o(n log n) time, and Other Transdichotomous Results in Computational Geometry Points on Computable Curves Postselection threshold against biased noise Ramsey partitions and proximity data structures SDP gaps and UGC-hardness for MaxCutGain Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority Settling the Complexity of 2-Player Nash-Equilibrium Solving Evacuation Problems Efficiently - Earliest Arrival Flows with Multiple Sources Statistical Zero-Knowledge Arguments for NP from Any One-Way Function Subspace Polynomials and List Decoding of Reed-Solomon Codes Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP The Effectiveness of Lloyd-type Methods for the k-Means Problem The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs Towards Secure and Scalable Computation in Peer-to-Peer Networks Witnesses for non-satisfiability of dense random 3CNF formulas Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method. |