Conference Program
Saturday, May 19th at New York University (Except Reception)
| Saturday, May 19, 2012 | ||||
|---|---|---|---|---|
|
Tutorial |
||||
| 9:45-10:45 |
Algorithmic Trading and Computational Finance,
Part I
Michael Kearns Room 109 |
|||
| 10:45-11:00 | Coffee break | |||
| 11:00-12:00 |
Algorithmic Trading and Computational Finance,
Part II
Michael Kearns Room 109 |
|||
| 12:00-1:30 | Lunch (Not Provided) | |||
|
Workshops |
||||
| 1:30-3:30 |
Computational Sustainability
Steven Phillips, Kirk Pruhs, David Shmoys Room 1302 |
Algorithms for Distributed and Streaming Data
Ashish Goel, Andrew McGregor, Sergei Vassilvitskii Room 101 |
Algorithms for Memory-Sensitive Computing
Michael Bender, Martin Farach-Colton Room 102 |
Unique Games Conjecture and Related Advances
Sanjeev Arora, Moses Charikar Room 109 |
| 3:30-4:00 | Coffee break | |||
| 4:00-6:00 |
Computational Sustainability
Steven Phillips, Kirk Pruhs, David Shmoys Room 1302 |
Algorithms for Distributed and Streaming Data
Ashish Goel, Andrew McGregor, Sergei Vassilvitskii Room 101 |
Algorithms for Memory-Sensitive Computing
Michael Bender, Martin Farach-Colton Room 102 |
Unique Games Conjecture and Related Advances
Sanjeev Arora, Moses Charikar Room 109 |
| 7:00-9:00 |
Reception NOTE: The reception will take place at The New Yorker Hotel. |
|||
Sunday, May 20th at The New Yorker Hotel
| Sunday, May 20, 2012 | ||
|---|---|---|
|
Session 1A Chair: Dan Spielman |
Session 1B Chair: Oded Regev |
|
| 8:45-9:05 |
Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows
Jonathan A. Kelner, Gary L. Miller, Richard Peng |
Quantum Money from Hidden Subspaces
Scott Aaronson, Paul Christiano |
| 9:10-9:30 |
When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks
Amit Chakrabarti, Lisa Fleisher, Christophe Weibel |
Certifiable Quantum Dice: Or, True Random Number Generation Secure Against Quantum Adversaries
Umesh Vazirani, Thomas Vidick |
| 9:35-9:55 |
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Laszlo A. Vegh |
Span Programs for Functions with Constant-Sized 1-certificates Aleksandrs Belovs |
| 9:55-10:25 | Coffee break | |
|
Session 2 Chair: Toniann Pitassi |
||
| 10:25-10:45 |
The Cell Probe Complexity of Dynamic Range Counting Kasper Green Larsen |
|
| 10:50-11:10 |
Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf |
|
|
Session 3A Chair: Amin Saberi |
Session 3B Chair: Shubanghi Saraf |
|
| 11:20-11:40 |
Polyhedral Clinching Auctions and the Adwords Polytope
Gagan Goel, Vahab Mirrokni, Renato Paes Leme |
Computing a Nonnegative Matrix Factorization - Provably
Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra |
| 11:45-12:05 |
Matroid Prophet Inequalities
Robert Kleinberg, Seth Matthew Weinberg |
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
Michael A. Forbes, Amir Shpilka |
| 12:10-12:30 |
Online matching with concave returns
Nikhil R. Devanur, Kamal Jain |
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs Martin Grohe, Daniel Marx |
| 12:30-2:00 |
Lunch (Not Provided)
|
|
|
Session 4A Chair: Toniann Pitassi |
Session 4B Chair: Oded Regev |
|
| 2:00-2:20 |
Short Proofs for the Determinant Identities
Pavel Hrubes, Iddo Tzameret |
Solution of the propeller conjecture in $R^3$
Steven Heilman, Aukosh Jagannath, Assaf Naor |
| 2:25-2:45 |
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
Paul Beame, Christopher Beck, Russell Impagliazzo |
$2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem
with Preprocessing
Subhash Khot, Preyas Popat, Nisheeth Vishnoi |
| 2:50-3:10 |
On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity
Trinh Huynh, Jakob Nordstrom |
A new point of NP-hardness for Unique Games
Ryan O'Donnell, John Wright |
| 3:15-3:35 |
Determinism versus Nondeterminism with Arithmetic Tests and Computation
Miklos Ajtai |
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando G.S.L. Brandao, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou |
| 3:35-4:05 |
Coffee Break
|
|
|
Session 5A Chair: Madhur Tulsiani |
Session 5B Chair: Sanjeev Khanna |
|
| 4:05-4:25 |
From Irreducible Representations to Locally Decodable Codes
Klim Efremenko |
Approximation Algorithms for Semi-Random Partitioning Problems
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 4:30-4:50 |
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding Venkatesan Guruswami, Chaoping Xing |
A Near-Linear Time $\eps$-Approximation Algorithm for Geometric Bipartite Matching R. Sharathkumar, Pankaj K. Agarwal |
| 4:55-5:15 |
Subspace Evasive Sets
Zeev Dvir, Shachar Lovett |
Using Petal-Decompositions to Build a Low Stretch Spanning Tree Ittai Abraham, Ofer Neiman |
| 5:20-5:40 |
Edge Transitive Ramanujan Graphs and Symmetric LDPC Good Codes
Tali Kaufman, Alexander Lubotzky |
Improved Smoothed Analysis of Multiobjective Optimization Tobias Brunsch, Heiko Roglin |
| 5:50 - 7:30 |
Poster Session |
|
Monday, May 21st at The New Yorker Hotel
| Monday, May 21, 2012 | ||
|---|---|---|
|
Session 6A Chair: Amin Saberi |
Session 6B Chair: Rahul Santhanam |
|
| 8:50-9:10 |
Prior-Free Auctions with Ordered Bidders
Stefano Leonardi, Tim Roughgarden |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola |
| 9:15-9:35 |
On the limits of black-box reductions in mechanism design
Shuchi Chawla, Nicole Immorlica, Brendan Lucier |
Tight Bounds for Monotone Switching Networks via Fourier Analysis
Siu Man Chan, Aaron Potechin |
| 9:40-10:00 |
Budget Feasible Mechanism Design: From Prior-Free to Bayesian
Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu |
Interactive Information Complexity
Mark Braverman |
| 10:05-10:25 |
An Algorithmic Characterization of Multi-Dimensional Mechanisms
Yang Cai, Constantinos Deskalakis, S. Matthew Weinberg |
The Multiparty Communication Complexity of Set Disjointness
Alexander A. Sherstov |
| 10:25-10:55 | Coffee break | |
|
Session 7A Chair: Satish Rao |
Session 7B Chair: Shubhanghi Saraf |
|
| 10:55-11:15 |
Fast Matrix Rank Algorithms and Applications
Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau |
Jacobian Hits Circuits: Hitting-sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena |
| 11:20-11:40 |
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
Separating multilinear branching programs and formulas
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff |
| 11:45-12:05 |
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2
Ankit Gupta, Neeraj Kayal, Satya Lokam |
| 12:10-12:30 |
Optmal Online Buffer Scheduling for Block Devices
Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Raecke |
Affine Projections of Polynomials
Neeraj Kayal |
| 12:30-2:00 |
Lunch (Provided!)
|
|
|
Session 8A Chair: Suresh Venkatasubramanian |
Session 8B Chair: Dana Ron |
|
| 2:00-2:20 |
The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer |
Learning Poisson Binomial Distributions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio |
| 2:25-2:45 |
On Vertex Sparsifiers with Steiner Nodes
Julia Chuzhoy |
Nearly optimal solutions for the Chow Parameters Problem and low- weight approximation of halfspaces
Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio |
| 2:50-3:10 |
Approximation Algorithms and Hardness of Integral Concurrent Flow
Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li |
Making Polynomials Robust to Noise
Alexander A. Sherstov |
| 3:10-3:30 |
Coffee Break
|
|
|
Session 9A Chair: Rahul Santhanam |
Session 9B Chair: Guy Rothblum |
|
| 3:30-3:50 |
Competitive Contagion in Networks
Sanjeev Goyal, Michael Kearns |
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
Benny Applebaum |
| 3:55-4:15 |
Finding red balloons with split contracts: robustness to individuals' selfishness
Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris |
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
Salil Vadhan, Colin Jia Zheng |
| 4:20-4:40 |
A Rigorous Analyis of One-Dimensional Schelling Segregation
Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg |
Design Extractors, Non-Malleable Condensers and Privacy Amplification
Xin Li |
| 4:40-5:00 | Coffee break | |
|
Session 10 Chair: David Williamson |
||
| 5:00-5:20 |
Routing in Undirected Graphs with Constant Congestion
Julia Chuzhoy |
|
| 5:25-5:45 |
Improving Chrisofides' Algorithm for the s-t Path TSP
Hyung-Chan An, Robert Kleinberg, David B. Shmoys |
|
| 5:50-6:10 |
Multiplying Matrices Faster Than Coppersmith-Winograd
Virginia Vassilevska Williams |
|
| 9:00 |
Business Meeting |
|
Tuesday, May 22nd at The New Yorker Hotel
| Tuesday, May 22, 2012 | ||
|---|---|---|
|
Session 11A Chair: Rina Panigrahy |
Session 11B Chair: Dana Ron |
|
| 8:50-9:10 |
Catching the k-NAESAT threshold
Amin Coja-Oglan, Konstantinos Panagiotou |
Tight Bounds for Distributed Functional Monitoring David P. Woodruff, Qin Zhang |
| 9:15-9:35 |
Complexity of Counting CSP with Complex Weights
Jin-Yi Cai, Xi Chen |
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov |
| 9:40-10:00 |
The freezing threshold for k-colourings of a random graph Michael Molloy |
Tight Time-Space Tradeoff for Mutual Exclusion
Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally |
| 10:05-10:25 |
Robust satisfiability of constraint satisfaction problems Libor Barto, Marcin Kozik |
A Tight RMR Lower Bound for Randomized Mutual Exclusion
George Giakkoupis, Philipp Woelfel |
| 10:25-10:55 | Coffee break | |
|
Session 12A Chair: Andrew McGregor |
Session 12B Chair: Tom Hayes |
|
| 10:55-11:15 |
A Complementary Pivot Algorithm for Markets under Separable, Piecewise-Linear Concave Utilities Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani |
Monotone expansion Jean Bourgain, Amir Yehudayoff |
| 11:20-11:40 |
Rational Proofs Pablo Azar, Silvio Micali |
Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
Noga Alon, Ankur Moitra, Benny Sudakov |
| 11:45-12:05 |
Minimax Option Pricing Meets Black-Scholes in the Limit Jacob Abernethy, Rafael Frongillo, Andre Wibisono |
Probabilistic existence of rigid combinatorial structures
Greg Kuperberg, Shachar Lovett, Ron Peled |
| 12:10-12:30 |
A quantitative Gibbard-Satterthwaite theorem without neutrality
Elchanan Mossel, Miklos Z. Racz |
From Query Complexity to Computational Complexity Shahar Dobzinski, Jan Vondrak |
| 12:30-2:00 | Lunch (Not Provided) | |
|
Session 13A Chair: Andrew McGregor |
Session 13B Chair: Guy Rothblum |
|
| 2:00-2:20 |
Multiway spectral partitioning and
higher-order Cheeger inequalities / Many Sparse Cuts via Higher Eigenvalues James R. Lee, Shayan Oveis Gharan, Luca Trevisan / Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala |
On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption
Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan |
| 2:25-2:45 |
Approximating the Exponential, the Lancoz Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator Lorenzo Orecchia, Sushant Sachdeva, Nisheeth Vishnoi |
Multiparty Computation Secure Against Continual Memory Leakage Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai |
| 2:50-3:10 |
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen |
Beating Randomized Response on Incoherent Matrices Moritz Hardt, Aaron Roth |
| 3:15-3:35 |
Strict Fibonacci Heaps
Gerth Stolting Brodal, George Lagogiannis, Robert E. Tarjan |
Unconditionally Differentially Private Mechanisms for Linear Queries
Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar |
| 3:40-4:00 |
Tight lower bounds for the online labeling problem Jan Bulanek, Michal Koucky, Michael Saks |
Optimal Private Halfspace Counting via Discrepancy
S. Muthukrishnan, Aleksandar Nikolov |
| 4:05-4:25 |
Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance labels
Ittai Abraham, Shiri Chechik, Cyril Gavoille |
|
| 4:25 PM |
End of Conference |
|
