FOCS 2012
TechTalks from event: FOCS 2012
The talks here are organized in the following order: Session 1A, Session 2A, Session 3A,... followed by Session 1B, Session 2B, and so on. Session 1B starts from Page 5.
- All Talks
- Learning Topic Models --- Going beyond SVD
- Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas
- Active Property Testing
- Constructive Discrepancy Minimization by Walking on The Edges
- Constructive Discrepancy Minimization by Walking on The Edges
- Combinatorial coloring of 3-colorable graphs
- A Permanent Approach to the Traveling Salesman Problem
- Split and Join: Strong Partitions and Universal Steiner Trees for Graphs
- The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
- Concave Generalized Flows with Applications to Market Equilibria
- Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
- Faster SDP hierarchy solvers for local rounding algorithms
- From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique
- A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- MIP* contains NEXP
- Beck's three permutations conjecture: A counterexample and some consequences
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- LP Rounding for k-Centers with Non-uniform Hard Capacities
- The Dynamics of Influence Systems
- The Locality of Distributed Symmetry Breaking
- How to Allocate Tasks Asynchronously
- Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies
- Population Recovery and Partial Identification
- The Privacy of the Analyst and The Power of the State
- The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
- Representative sets and irrelevant vertices: New tools for kernelization
- Designing FPT algorithms for cut problems using randomized contractions
- Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms
- Knuth Prize Lecture - Turing's Password: What Internet Cannot Leak
- Faster Algorithms for Rectangular Matrix Multiplication
- Quasi-optimal multiplication of linear differential operators
- Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings
- The Cutting Plane Method is Polynomial for Perfect Matchings
- A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs
- A New Direction for Counting Perfect Matchings
- Single Source - All Sinks Max Flows in Planar Digraphs
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
- The power of linear programming for valued CSPs
- Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis
- Matching with our Eyes Closed
- Online Matching with Stochastic Rewards
- How to Compute in the Presence of Leakage
- Positive Results for Concurrently Secure Computation in the Plain Model
- Constructing Non-Malleable Commitments: A Black-Box Approach
- A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions
- Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits
- Pseudorandomness from Shrinkage
- Better Pseudorandom Generators from Milder Pseudorandom Restrictions
- Efficient Interactive Coding Against Adversarial Noise
- A direct product theorem for the two-party bounded-round public-coin communication complexity
- An additive combinatorics approach relating rank to communication complexity
- A PTAS for Computing the Supremum of Gaussian Processes
- On-line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List
- Higher Cell Probe Lower Bounds for Evaluating Polynomials
- The tile assembly model is intrinsically universal
- On the complexity of finding narrow proofs
- The computational hardness of counting in two-spin models on d-regular graphs
- Making the Long Code Shorter
- Hardness of Finding Independent Sets in Almost q-Colorable Graphs
- On Range Searching with Semialgebraic Sets II
- Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
- On the homotopy test on surfaces
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Formulas Resilient to Short-Circuit Errors
- Lower bounds on Information Complexity via zero-communication protocols and applications
- Almost Optimal Canonical Property Testers for Satisfiability
- Partially Symmetric Functions are Efficiently Isomorphism-Testable
- Sparse affine-invariant linear codes are locally testable
- New Limits to Classical and Quantum Instance Compression
- Lower Bounds for Interactive Compression by Constant-Depth Circuits
- Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's normalization lemma
- Computing Multiplicities of Lie Group Representations
- How to Construct Quantum Random Functions
- Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
- Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
- A New Infinity of Distance Oracles for Sparse Graphs
- Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths
- Everywhere-Sparse Spanners via Dense Subgraphs