|
Program
|
Every day, at 8:30am, there will be free breakfast available.
August 17
9:00-10:50 (Approx)
Chair: R.Ravi
- Johan Håstad. Satisfying degree d equations over GF[2]^n
- Michael Kapralov and Rina Panigrahy. Multiplicative approximations of random walk transition probabilities
- Sanjeev Arora and Rong Ge. New Tools for Graph Coloring
- Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala. Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
- Chandan Dubey and Thomas Holenstein. Approximating lattice problems using an approximate shortest vector oracle
10:50-11:15 Coffee break
11:15-13:10 (Random)
Chair: Leslie Goldberg
- Invited talk - Joel Spencer. Two Needles in Exponential Haystacks
- Omri Weinstein, Ronitt Rubinfeld, Dana Ron and Muli Safra. Approximating the influence of a monotone Boolean function in $O(\sqrt{n})$ query complexity
- Gilad Tsur and Dana Ron. On Approximating the Number of Relevant Variables in a Function
- Dana Dachman-Soled and Rocco Servedio. A canonical form for testing Boolean function properties
13:10-14:30 Lunch break (at your own)
14:30-16:20 (Approx)
Chair: Viswanath Nagarajan
- Michael Crouch and Andrew Mcgregor. Periodicity and Cyclic Shifts via Linear Sketches
- Khanh Do Ba and Piotr Indyk. Sparse recovery with partial support knowledge
- Zhiyi Huang, Lei Wang and Yuan Zhou. Black-Box Reductions in Mechanism Design
- Sagi Snir and Raphael Yuster. A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
- Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Social Welfare in One-sided Matching Markets without Money
16:20-16:45 Coffee break
16:45-18:57 (Random)
Chair: Eric Allender
- Zhiyi Huang and Sampath Kannan. On Sampling from Multivariate Distributions
- Nayantara Bhatnagar, Andrej Bogdanov and Elchanan Mossel. The Computational Complexity of Estimating MCMC Convergence Time
- Sarah Miracle, Dana Randall and Amanda Pascoe Streib. Clustering in Interfering Models of Binary Mixtures
- Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
- Mohammed Abdullah, Colin Cooper and Moez Draief. Viral Processes by Random Walks on Random Graphs
- Tobias Friedrich and Lionel Levine. Fast Simulation of Large-Scale Growth Models
19:00 Welcome Reception
August 18
9:00-10:50 (Random)
Chair: Oded Goldreich
- Venkatesan Guruswami and Carol Wang. Optimal rate list decoding via derivative codes
- Brett Hemenway, Martin Strauss, Rafail Ostrovsky and Mary Wootters. Public-Key Locally-Decodable Codes with Short Keys
- Irit Dinur and Tali Kaufman. Dense locally testable codes cannot have constant rate and distance
- Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes
- Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan. On Sums of Locally Testable Affine Invariant Properties
10:50-11:15 Coffee break
11:15-13:10 (Approx)
R. Ravi
- David Williamson, Some Open Problems in Approximation Algorithms
- Sushant Sachdeva and Rishi Saket. Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
- Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
- Per Austrin, Mark Braverman and Eden Chlamtac. Inapproximability of NP-Complete Variants of Nash Equilibrium
13:10-14:30 Lunch break (at your own)
14:30-16:20 (Random)
Chair: Dana Ron
- Lidor Avigad and Oded Goldreich. Testing Graph Blow-Up
- Oded Goldreich and Tali Kaufman. Proximity Oblivious Testing and the Role of Invariances
- Eldar Fischer and Eyal Rozenberg. Inflatable graph properties and natural property tests
- Alan Edelman, Avinatan Hassidim, Huy Nguyen and Krzysztof Onak. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Andris Ambainis, Andrew Childs and Yi-Kai Liu. Quantum property testing for bounded-degree graphs
16:20-16:45 Coffee break
16:45-18:57 (Approx)
Chair: Deeparnab Chakrabarty
- Feodor Dragan and Ekkehard Koehler. An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman. Bandwidth and Low Dimensional Embedding
- Adrian Dumitrescu, Minghui Jiang and Janos Pach. Opaque sets
- Sandor Fekete, Tom Kamphans, Alexander Kroeller, Joseph Mitchell and Christiane Schmidt. Exploring and Triangulating a Region by a Swarm of Robots
- Parinya Chalermsook. Coloring and Maximum Independent Set of Rectangles
- Piotr Berman, Erik D. Demaine and Morteza Zadimoghaddam. O(1)-Approximations for Maximum Movement Problems
August 19
9:00-10:50 (Approx)
Chair: Amit Kumar
- Rohit Khandekar, Guy Kortsarz and Zeev Nutov. Approximating node-connectivity and prize-collecting network-design problems with degree constraints
- Nachshon Cohen and Zeev Nutov. A $(1+\ln 2)$-approximation algorithm for minimum-cost $2$-edge-connectivity augmentation of trees with constant radius
- Timothy Carnes and David Shmoys. Primal-Dual Schema and Lagrangian Relaxation for the k-Location Routing Problem
- M. Reza Khani and Mohammad Salavatipour. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
- Inge Li Gørtz and Viswanath Nagarajan. Locating Depots for Capacitated Vehicle Routing
10:50-11:15 Coffee break
11:15-13:05 (Random)
Chair: Nayantara Bhatnagar
- Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtech Rodl and Asaf Shapira. A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
- Daniel Kane, Raghu Meka and Jelani Nelson. Almost Optimal Explicit Johnson-Lindenstrauss Transformations
- Anindya De and Thomas Watson. Extractors and Lower Bounds for Locally Samplable Sources
- Thomas Watson. Query Complexity in Errorless Hardness Amplification
- Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
13:10-14:30 Lunch break (at your own)
14:30-16:20 (Approx)
Chair:Zeev Nutov
- Maurice Cheung and David Shmoys. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- Venkatesan Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. Scheduling Resources for Throughput Maximization
- Marek Karpinski and Warren Schudy. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
- Moran Feldman, Seffi Naor and Roy Schwartz. Improved Competitive Ratios for Submodular Secretary
- Nikhil Bansal, Ravishankar Krishnaswamy and Barna Saha. On Capacitated Set Cover
16:20-16:45 Coffee break
16:45-18:35 (Random)
Chair: Jose Rolim
- Amit Chakrabarti and Ranganath Kondapally. Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Andrew Drucker. Efficient Probabilistically Checkable Debates
- Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC0 circuits with n^{1−o(1)} symmetric gates
- Varsha Dani and Cristopher Moore. Independent sets in random graphs from the weighted second moment method
- Joshua Brody and David Woodruff. Streaming Algorithms with One-Sided Estimation
|
|
|
|
PDF Format
Plain Text
(download the program in PDF here)