PDF Format
PostScript
Plain Text
Program
| For instructions on how to find the venue that the talks will take place, please follow this link. | |
| Monday | |
| 09:00am-10:00am | Invited speaker - Nathan Linial, The Hebrew University of Jerusalem |
| Section:Random | |
| 10:00am-10:20am | Venkatesan Guruswami, James R. Lee, and Avi Wigderson. Euclidean Sections of L_1^N with Sublinear Randomness and Error-Correction Over the Reals |
| 10:20am-10:40am | Coffee break |
| 10:40am-11:00am | Avner Magen and Anastasios Zouzias. Near Optimal Dimensionality Reductions that Preserve Volumes |
| 11:00am-11:20am | Edo Liberty, Nir Ailon and Amit Singer. Dense Fast Random Projections and Lean Walsh Transforms |
| 11:20am-11:40am | Gregory Sorkin. The Power of Choice in a Generalized Polya Urn Model |
| 11:40am-12:00pm | Jeff Abrahamson, Bela Csaba, Ali Shokoufandeh. Optimal Random Matchings on Trees and Applications |
| 12:00pm-12:20pm | Hariharan Narayanan and Partha Niyogi. Sampling Hypersurfaces through Diffusion |
| 12:20pm-02:00pm | Lunch break |
| Section:Approx | |
| 02:00pm-02:20pm | Venkat Guruswami and Prasad Raghavendra. Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness |
| 02:20pm-02:40pm | Yuval Lando and Zeev Nutov. Inapproximability of Survivable Networks |
| 02:40pm-03:00pm | Micah Adler and Brent Heeringa. Approximating Optimal Binary Decision Trees |
| 03:00pm-03:20pm | Richard Matthew McCutchen and Samir Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity |
| 03:20pm-03:40pm | Shashi Mittal and Andreas S. Schulz. A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One |
| 03:40pm-04:00pm | Coffee break |
| Section:Random | |
| 04:00pm-04:20pm | Kai-Min Chung and Salil Vadhan. Tight Bounds for Hashing Block Sources |
| 04:20pm-04:40pm | Anup Rao and David Zuckerman. Extractors for Three Uneven-Length Sources |
| 04:40pm-05:00pm | Ariel Gabizon and Ronen Shaltiel. Increasing the Output Length of Zero-Error Dispersers |
| 05:00pm-05:20pm | Anup Rao. A 2-Source Almost-Extractor for Linear Entropy |
| 05:20pm-05:40pm | Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs |
| 06:00pm | Reception |
| Tuesday | |
| 09:00am-10:00am | Invited speaker - Harald Räcke, University of Warwick |
| Section:Approx | |
| 10:00am-10:20am | Eden Chlamtac and Gyanit Singh. Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies |
| 10:20:am-10:40am | Coffee break |
| 10:40am-11:00am | Aravind Srinivasan. Budgeted allocations in the full-information setting |
| 11:00am-11:20am | Nir Halman, Chung-Lun Li, and David Simchi-Levi. Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks |
| 11:20am-11:40am | Arash Asadpour, Uriel Feige and Amin Saberi. Santa Claus Meets Hypergraph Matchings |
| 11:40am-12:00pm | Monaldo Mastrolilli, Nikolaus Mutsanas and Ola Svensson. Approximating Single Machine Scheduling with Scenarios |
| 12:00pm-12:20pm | David R. Karger and Jacob Scott. Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP |
| 12:20pm-02:00pm | Lunch break |
| Section:Random | |
| 02:00pm-02:20pm | Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman and Orly Yahalom.On the Query Complexity of Testing Orientations for being Eulerian |
| 02:20pm-02:40pm | Eric Blais. Improved Bounds for Testing Juntas |
| 02:40pm-03:00pm | Tali Kaufman, Simon Litsyn and Ning Xie. Breaking the ε-Soundness Bound of the Linearity Test over GF(2) |
| 03:00pm-03:20pm | Homin Lee, Jeffrey Jackson, Rocco Servedio and Andrew Wan. Learning random monotone DNF |
| 03:20pm-03:40pm | Hang Dinh and Alexander Russell. Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs |
| 03:40pm-04:00pm | Coffee break |
| Section:Approx | |
| 04:00pm-04:20pm | Zeev Nutov. Approximating Directed Weighted-Degree Constrained Networks |
| 04:20pm-04:40pm | Viswanath Nagarajan and R Ravi. The Directed Minimum Latency Problem |
| 04:40pm-05:00pm | Lukasz Kowalik and Marcin Mucha. Deterministic 7/8-approximation for the Metric Maximum TSP |
| 05:00pm-05:20pm | Thanh Nguyen. A simple LP relaxation for the Asymmetric Traveling Salesman Problem |
| 05:20pm-05:40pm | Adrian Dumitrescu and Minghui Jiang. Sweeping points |
| Wednesday | |
| 09:00am-10:00am | Invited speaker - Anup Rao, Institute for Advanced Study, Princeton University |
| Section:Random | |
| 10:00am-10:20am | Dan Gutfreund and Salil Vadhan. Limitations of Hardness vs. Randomness under Uniform Reductions |
| 10:20am-10:40am | Coffee break |
| 10:40am-11:00am | Noga Alon, Ido Ben Eliezer and Michael Krivelevich. Small sample spaces cannot fool low degree polynomials |
| 11:00am-11:20am | Vikraman Arvind and Partha Mukhopadhyay. Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size |
| 11:20am-11:40am | Dan Gutfreund and Guy Rothblum. The Complexity of Local List Decoding |
| 11:40am-12:00pm | Eli Ben-Sasson and Michael Viderman. Tensor Products of Weakly Smooth Codes are Robust |
| 12:00pm-12:20pm | David Woodruff. Corruption and Recovery-Efficient Locally Decodable Codes |
| 12:20pm-02:00pm | Lunch break |
| Section:Approx | |
| 02:00pm-02:20pm | Mihai Buadoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos and Morteza Zadimoghaddam. Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction |
| 02:20pm-02:40pm | Guy Kortsarz, Michael Langberg and Zeev Nutov. Approximating Maximum Subgraphs Without Short Cycles |
| 02:40pm-03:00pm | MohammadAli Safari and Mohammad Salavatipour. A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs |
| 03:00pm-03:20pm | Jean Cardinal and Eythan Levy. Connected Vertex Covers in Dense Graphs |
| 03:20pm-03:40pm | Coffee break |
| Section:Random | |
| 03:40pm-04:00pm | Matei David, Toniann Pitassi and Emanuele Viola. Improved Separations between Nondeterministic and Randomized Multiparty Communication |
| 04:00pm-04:20pm | Raphael Yuster. Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets |
| 04:20pm-04:40pm | Martin Fürer and Shiva Kasiviswanathan. Approximately Counting Embeddings into Random Graphs |
| 04:40pm-05:00pm | Guy Bresler, Elchanan Mossel and Allan Sly. Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms |
| 05:00pm-05:20pm | Andrej Bogdanov, Elchanan Mossel and Salil Vadhan. The complexity of distinguishing Markov Random Fields |