8h-9h Registration desk open

Note: The registration Desk will be open on every break during the conference period

9h-10h50am (Random)

• Oded Goldreich. On Testing Computability by Small Width OBDDs
• Noga Alon and Eric Blais. Testing boolean function isomorphism
• Yuichi Yoshida and Hiro Ito. Testing Outerplanarity of Bounded Degree Graphs
• Suguru Tamaki and Yuichi Yoshida. A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness
• Dana Ron and Elya Dolev. Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries

10h50-11h15am Coffee Break

11h15 -1h10pm (Approx)

• Leslie A Goldberg (invited talk). Approximating the Tutte polynomial of a graph
• Per Austrin. Improved Inapproximability For Submodular Maximization
• Preyas Popat, Subhash Khot and Rishi Saket. Approximate Lasserre Integrality Gap for Unique Games
• Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson and Ola Svensson. Approximating Linear Threshold Predicates

1h10pm-2h30pm Lunch

2h30pm-4h20pm (Random)

• Arie Matsliah, Jop Briet, Sourav Chakraborty and David Garci'a-Soriano. Monotonicity Testing and Shortest-Path Routing on the Cube
• Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
• Funda Ergun, Hossein Jowhari and Mert Saglam. Periodicity in Streams
• Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick and Ronald de Wolf. Better Gap-Hamming Lower Bounds via Better Round Elimination
• Rasmus R. Amossen, Andrea Campagna and Rasmus Pagh. Better size estimation for sparse matrix products

4h20pm-4h45pm Coffee Break

4h45pm-6h35pm (Approx)

• Mohammad Hossein Bateni and Julia Chuzhoy. Approximation Algorithms for the Directed k-Stroll and k-Tour Problems
• Hyung-Chan An, Robert D. Kleinberg and David B. Shmoys. Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
• Igor Gorodezky, Robert Kleinberg, David Shmoys and Gwen Spencer. Improved lower bounds for the universal and a priori TSP
• Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Julian Mestre. The Checkpoint Problem
• Thomas Erlebach and Erik Jan van Leeuwen. PTAS for Weighted Set Cover on Unit Squares
  

9h30pm Conference dinner

Restaurant: El Tunel del Port
Address: Moll de Gregal 12, at the Olympic Harbor
Website: http://www.eltuneldelport.com/index.php?op=inici&idioma=3

9h-10h50am (Approx)

• Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi and Morteza Zadimoghaddam . Submodular Secretary Problem and Extensions
• Spyros Kontogiannis and Paul Spirakis. Exploiting Concavity in Bimatrix Games: New polynomially tractable subclasses
• Piotr Berman and Sofya Raskhodnikova. Approximation Algorithms for Min-Max Generalization Problems
• Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
• Gruia Calinescu. Min-Power Strong Connectivity

10h50-11h15am Coffee Break

11h15 -1h10pm (Random)

• Oded Goldreich (Invited talk). Some Thoughts regarding Unconditional Derandomization
• Russell Impagliazzo and Valentine Kabanets. Constructive Proofs of Concentration Bounds
• Elazar Goldenberg and Irit Dinur. The Structure of Winning Strategies in Parallel Repetition Games
• David Steurer. Improved Rounding for Parallel Repeated Unique Games

1h10pm-2h30pm Lunch

2h30pm-4h20pm (Approx)

• Irit Dinur and Igor Shinkar. On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors
• Prasad Chebolu, Leslie Ann Goldberg and Russell Martin. The Complexity of Approximately Counting Stable Matchings
• Evdokia Nikolova. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
• Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam and Kunal Talwar. Vertex Sparsifiers: New Results from Old Techniques
• Eden Chlamtac, Robert Krauthgamer and Prasad Raghavendra. Approximating Sparsest Cut in Graphs of Bounded Treewidth

4h20pm-4h45pm Coffee Break

4h45pm-6h57pm (Random)

• Parikshit Gopalan and Rocco Servedio. Learning and Lower Bounds for AC0 with Threshold Gates
• Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani. Improved Pseudorandom Generators for Depth 2 Circuits
• Eric Allender, V Arvind and Fengming Wang. Uniform Derandomization from Pathetic Lower Bounds
• Roy Kasher and Julia Kempe. Two-source Extractors Secure Against Quantum Adversaries
• Piotr Indyk and Stanislaw Szarek. Almost-Euclidean subspaces of ell_1^N via tensor products: a simple approach to randomness reduction
• Aaron Roth. Differential Privacy and the Fat-Shattering Dimension of Linear Queries

9h-10h50am (Random)

• Nikolaos Fountoulakis and Konstantinos Panagiotou. Rumor spreading on random regular graphs and expanders
• Amin Coja-Oghlan, Mikael Onsjo and Osamu Watanabe. Propagation Connectivity of Random Hypergraphs
• Nayantara Bhatnagar, Allan Sly and Prasad Tetali. Reconstruction threshold for the hardcore model
• Thomas Hayes and Alistair Sinclair. Liftings of Tree-Structured Markov Chains
• Alistair Sinclair and Dan Vilenchik. Delaying satisfiability for random 2SAT

10h50-11h15am Coffee Break

11h15 -1h05pm (Approx)

• Ishay Haviv and Oded Regev. The Euclidean Distortion of Flat Tori
• Lee-Ad Gottlieb and Tyler Neylon. Matix sparsification and the sparse null space problem
• Ken-ichi Kawarabayashi and Yusuke Kobayashi. Improved Algorithm for the Half-Disjoint Paths Problem
• Guyslain Naves, Nicolas Sonnerat and Adrian Vetta. Maximum Flows on Disjoint Paths
• Ken-ichi Kawarabayashi and Yusuke Kobayashi. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs

1h10pm-2h30pm Lunch

2h30pm-4h20pm (Random)

• Tali Kaufman and Michael Viderman. Locally Testable vs. Locally Decodable Codes
• Eli Ben-Sasson and Michael Viderman. Low Rate Is Insufficient for Local Testability
• David Woodruff. A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
• Atri Rudra and Steve Uurtamo. Two Theorems on List Decoding
• Thomas Watson. Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

4h20pm-4h45pm Coffee Break

4h45pm-6h35pm (Approx)

• Mohit Singh and Kunal Talwar. Improving Integrality Gaps via \chvatal-Gomory Rounding
• Lee-Ad Gottlieb and Robi Krauthgamer. Proximity algorithms for nearly-doubling spaces
• Frank Kammer,Heiko Voepel and Torsten Tholey. Approximation Algorithms for Intersection Graphs
• Piotr Indyk, Avner Magen, Anastasios Sidiropoulos and Anastasios Zouzias. On-line Embeddings
• Victor Chepoi, Feodor Dragan, Ilan Newman, Yuri Rabinovich and Yann Vaxes. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs