default search action
53rd FOCS 2012: New Brunswick, NJ, USA
- 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. IEEE Computer Society 2012, ISBN 978-1-4673-4383-1
Session 1A
- Sanjeev Arora, Rong Ge, Ankur Moitra:
Learning Topic Models - Going beyond SVD. 1-10 - Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. 11-20 - Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang:
Active Property Testing. 21-30
Session 1B
- Shafi Goldwasser, Guy N. Rothblum:
How to Compute in the Presence of Leakage. 31-40 - Vipul Goyal:
Positive Results for Concurrently Secure Computation in the Plain Model. 41-50 - Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti:
Constructing Non-malleable Commitments: A Black-Box Approach. 51-60
Session 2A
- Shachar Lovett
, Raghu Meka:
Constructive Discrepancy Minimization by Walking on the Edges. 61-67 - Ken-ichi Kawarabayashi, Mikkel Thorup
Combinatorial Coloring of 3-Colorable Graphs. 68-75 - Nisheeth K. Vishnoi:
A Permanent Approach to the Traveling Salesman Problem. 76-80 - Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan:
Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. 81-90
Session 2B
- Daniel M. Kane:
A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. 91-100 - Chris Beck
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. 101-110 - Russell Impagliazzo
Pseudorandomness from Shrinkage. 111-119 - Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan
Better Pseudorandom Generators from Milder Pseudorandom Restrictions. 120-129
Session 3A
- Yang Cai
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. 130-139 - Zhiyi Huang
The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal. 140-149 - László A. Végh
Concave Generalized Flows with Applications to Market Equilibria. 150-159
Session 3B
- Zvika Brakerski, Yael Tauman Kalai:
Efficient Interactive Coding against Adversarial Noise. 160-166 - Rahul Jain
A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity. 167-176 - Eli Ben-Sasson, Shachar Lovett
An Additive Combinatorics Approach Relating Rank to Communication Complexity. 177-186
Session 4A
- Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. 187-196 - Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP Hierarchy Solvers for Local Rounding Algorithms. 197-206
Session 4B
- Aleksandrs Belovs:
Learning-Graph-Based Quantum Algorithm for k-Distinctness. 207-216 - Raghu Meka:
A PTAS for Computing the Supremum of Gaussian Processes. 217-222
Session 5
- Nir Bitansky, Omer Paneth:
From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique. 223-232 - Julia Chuzhoy, Shi Li:
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2. 233-242 - Tsuyoshi Ito, Thomas Vidick
A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. 243-252
Session 6A
- Alantha Newman, Ofer Neiman, Aleksandar Nikolov:
Beck's Three Permutations Conjecture: A Counterexample and Some Consequences. 253-262 - Takuro Fukunaga
Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design. 263-272 - Marek Cygan
LP Rounding for k-Centers with Non-uniform Hard Capacities. 273-282
Session 6B
- Tsvi Kopelowitz:
On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List. 283-292 - Kasper Green Larsen:
Higher Cell Probe Lower Bounds for Evaluating Polynomials. 293-301 - David Doty
The Tile Assembly Model is Intrinsically Universal. 302-310
Session 7A
- Bernard Chazelle:
The Dynamics of Influence Systems. 311-320 - Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. 321-330 - Dan Alistarh, Michael A. Bender, Seth Gilbert
How to Allocate Tasks Asynchronously. 331-340 - Thomas Sauerwald, He Sun:
Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies. 341-350
Session 7B
- Christoph Berkholz:
On the Complexity of Finding Narrow Proofs. 351-360 - Allan Sly, Nike Sun:
The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs. 361-369 - Boaz Barak, Parikshit Gopalan, Johan Håstad
Making the Long Code Shorter. 370-379 - Subhash Khot, Rishi Saket:
Hardness of Finding Independent Sets in Almost q-Colorable Graphs. 380-389
Session 8A
- Avi Wigderson, Amir Yehudayoff:
Population Recovery and Partial Identification. 390-399 - Cynthia Dwork, Moni Naor, Salil P. Vadhan:
The Privacy of the Analyst and the Power of the State. 400-409 - Jeremiah Blocki
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. 410-419
Session 8B
- Pankaj K. Agarwal, Jirí Matousek, Micha Sharir:
On Range Searching with Semialgebraic Sets II. 420-429 - Sariel Har-Peled
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space. 430-439 - Francis Lazarus, Julien Rivaud:
On the Homotopy Test on Surfaces. 440-449
Session 9A
- Stefan Kratsch, Magnus Wahlström
Representative Sets and Irrelevant Vertices: New Tools for Kernelization. 450-459 - Rajesh Hemant Chitnis
Designing FPT Algorithms for Cut Problems Using Randomized Contractions. 460-469 - Fedor V. Fomin
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. 470-479
Session 9B
- Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
Approximation Limits of Linear Programs (Beyond Hierarchies). 480-489 - Yael Tauman Kalai, Allison B. Lewko, Anup Rao:
Formulas Resilient to Short-Circuit Errors. 490-499 - Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications. 500-509
Session 10 - Knuth Prize Lecture
- Leonid A. Levin:
Rarity for Semimeasures. 510-513
Session 11A
- François Le Gall:
Faster Algorithms for Rectangular Matrix Multiplication. 514-523 - Alexandre Benoît, Alin Bostan, Joris van der Hoeven
Quasi-optimal Multiplication of Linear Differential Operators. 524-530 - Marek Cygan
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. 531-540
Session 11B
- Christian Sohler
Almost Optimal Canonical Property Testers for Satisfiability. 541-550 - Eric Blais, Amit Weinstein, Yuichi Yoshida:
Partially Symmetric Functions Are Efficiently Isomorphism-Testable. 551-560 - Eli Ben-Sasson, Noga Ron-Zewi
Sparse Affine-Invariant Linear Codes Are Locally Testable. 561-570
Session 12A
- Karthekeyan Chandrasekaran, László A. Végh
The Cutting Plane Method Is Polynomial for Perfect Matchings. 571-580 - Lyle Ramshaw, Robert Endre Tarjan:
A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs. 581-590 - Taisuke Izumi, Tadashi Wadayama:
A New Direction for Counting Perfect Matchings. 591-598 - Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen:
Single Source - All Sinks Max Flows in Planar Digraphs. 599-608
Session 12B
- Andrew Drucker:
New Limits to Classical and Quantum Instance Compression. 609-618 - Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. 619-628 - Ketan Mulmuley:
Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma. 629-638 - Matthias Christandl, Brent Doran, Michael Walter
Computing Multiplicities of Lie Group Representations. 639-648
Session 13A
- Niv Buchbinder
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. 649-658 - Yuval Filmus, Justin Ward:
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint. 659-668 - Johan Thapper
The Power of Linear Programming for Valued CSPs. 669-678
Session 13B
- Mark Zhandry:
How to Construct Quantum Random Functions. 679-687 - Xin Li:
Non-malleable Extractors, Two-Source Extractors and Privacy Amplification. 688-697 - Thomas Holenstein, Makrand Sinha:
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls. 698-707
Session 14A
- Matthias Poloczek, Mario Szegedy:
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. 708-717 - Gagan Goel, Pushkar Tripathi:
Matching with Our Eyes Closed. 718-727 - Aranyak Mehta, Debmalya Panigrahi:
Online Matching with Stochastic Rewards. 728-737
Session 14B
- Mihai Patrascu, Liam Roditty, Mikkel Thorup
A New Infinity of Distance Oracles for Sparse Graphs. 738-747 - Fabrizio Grandoni
Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. 748-757 - Eden Chlamtac, Michael Dinitz
Everywhere-Sparse Spanners via Dense Subgraphs. 758-767
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-28 20:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: