APPROX + RANDOM 2014 Preliminary Program

All sessions will take place in the Aula Master
located in the ground floor of the A3 Bulding, UPC North Campus
Each contributed presentation has been allocated a 20 minutes slot, please leave some time for questioning.

September 4

• 08:00 - 08:25 Registration
• 08:25 - 08:30 Welcome
• 08:30 - 09:35 Session 1
  
  • Jeremy Karp and R Ravi. A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
  • Takuro Fukunaga, Afshin Nikzad and R Ravi. Deliver or Hold: Approximation Algorithms for the Periodic Inventory Routing Problem
  • Chaitanya Swamy. Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• Break
• 09:45 - 10:50 Session 2
  • Hu Fu and Robert Kleinberg. Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
  • Arkadev Chattopadhyay and Michael E Saks. The Power of Super-logarithmic Number of Players
  • Oded Goldreich. On Multiple Input Problems in Property Testing
• Coffee Break
• 11:10 - 12:05 Invited talk
  • Uri Feige. TBA
• 12:10 - 13:15 Session 3
  • Noga Alon, Troy Lee and Adi Shraibman. The cover number of a matrix and its algorithmic applications.
  • Nicholas Harvey, Roy Schwartz and Mohit Singh. Discrepancy Without Partial Colorings
  • Ittai Abraham, Shiri Chechik and Kunal Talwar. Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
• Lunch Break
• 14:30 - 15:55 Session 4
  • Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Rassmann and Dan Vilenchik. The condensation phase transition in random graph coloring
  • Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic and Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
  • Andreas Galanis, Daniel Stefankovic, Eric Vigoda and Linji Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
  • Jingcheng Liu, Pinyan Lu and Chihao Zhang. The Complexity of Ferromagnetic Two-spin Systems with External Fields
• Coffee Break
• 16:15 - 17:40 Session 5
  • Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP
  • Shlomo Jozeph. Universal Factor Graphs for every NP-hard Boolean CSP
  • Cenny Wenner. Parity is Positively Useless
  • Eden Chlamtac and Michael Dinitz. Lowest Degree k-Spanner: Approximation and Hardness
• Break
• 17:50 - 18:55 Session 6
  • Alan Guo and Madhu Sudan. List decoding group homomorphisms between solvable groups
  • Venkatesan Guruswami and Carol Wang. Explicit rank-metric codes list-decodable with optimal redundancy
  • Adam Klivans and Pravesh Kothari. Embedding Hard Learning Problems into Gaussian Space

September 5

• 08:30 - 09:35 Session 7
  • Gábor Braun, Samuel Fiorini and Sebastian Pokutta. Average case polyhedral complexity of the maximum stable set problem
  • Julia Böttcher, Jan Hladký, Diana Piguet and Anusch Taraz. An approximate version of the tree packing conjecture via random embeddings
  • T.S. Jayram and Jan Vondrak. Exchangeability and realizability: de Finetti theorems on graphs
• Break
• 09:45 - 11:10 Session 8
  • Alan Soper and Vitaly Strusevich. Power of Preemption on Uniform Parallel Machines
  • Shashi Mittal, Andreas Schulz and Sebastian Stiller. Robust appointment scheduling
  • Kshipra Bhawalkar, Sreenivas Gollapudi and Debmalya Panigrahi. Online Set Cover with Set Requests
  • Michael Crouch and Daniel Stubbs. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching
• Coffee Break
• 11:30 - 12:55 Session 9
  • Anat Ganor and Ran Raz. Space Pseudorandom Generators by Communication Complexity Lower Bounds
  • Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities
  • Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction
  • Eric Blais, Joshua Brody and Badih Ghazi. The Information Complexity of Hamming Distance
• Lunch Break
• 14:15 - 15:40 Session 10
  • Siddharth Barman, Shuchi Chawla and Seeun Umboh. Network Design with Coverage Costs
  • Martin Gairing, Tobias Harks and Max Klimm. Complexity and Approximation of the Continuous Network Design Problem
  • Christoph Hansknecht, Max Klimm and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games
  • Michal Feldman, Nicole Immorlica, Brendan Lucier and S. Matthew Weinberg. Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks
• Coffee Break
• 16:00 - 17:25 Session 11
  • Nathanaë l François, Frederic Magniez and Rahul Jain. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
  • Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar and Silvio Lattanzi. On Reconstructing a Hidden Permutation
  • Vladimir Braverman, Jonathan Katzman, Charles Seidell and Greg Vorsanger. An Optimal Algorithm for Large Frequency Moments Using O(n^1-2/k) Bits
  • Chandan Dubey and Thomas Holenstein. Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
• Break
• 17:35 - 18:40 Session 12
  • Alina Ene and Jan Vondrak. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture
  • Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree
  • Adrian Dumitrescu, Minghui Jiang and Csaba Toth. Computing opaque interior barriers a la Shermer
• 21:00 Conference dinner

September 6

• 08:30 - 09:35 Session 13
  
  • Abbas Mehrabian and Nick Wormald. It's a Small World for Random Surfers
  • Milan Bradonjic and Will Perkins. On sharp thresholds in random geometric graphs
  • Josep Díaz, Leslie Ann Goldberg, David Richerby and Maria Serna. Absorption Time of the Moran Process
• Break
• 09:45 - 10:50 Session 14
  • Stavros Kolliopoulos and Yannis Moysoglou. Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location
  • Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad Salavatipour and Chaitanya Swamy. Approximation Algorithms for Minimum-Load k-Facility Location
  • Shanfei Li. An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
• Coffee Break
• 11:15 - 12:10 Invited talk
  • Colin McDiarmid. TBA
• 12:15 - 13:20 Session 15
  • Omer Reingold, Raghu Meka and Yuan Zhou. Deterministic Coupon Collection and Better Strong Dispersers
  • Gil Cohen, Anat Ganor and Ran Raz. Two Sides of the Coin Problem
  • Thomas Steinke, Salil Vadhan and Andrew Wan. Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
• Lunch Break
• 14:15 - 15:40 Session 16
  • Anand Louis and Yury Makarychev. Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
  • Prasad Raghavendra and Tselil Schramm. Gap Amplification for Small-Set Expansion via Random Walks & Tsz Chiu Kwok and Lap Chi Lau. Lower Bounds on Expansion of Graph Powers
  • Amit Deshpande and Rakesh Venkat. Guruswami-Sinop Rounding without Higher Level Lasserre
  • Abhiram Natarajan and Yi Wu. Complexity of Certifying Restricted Isometry Property and Sparse Cheeger's Inequality
• Coffee Break
• 16:10 - 17:15 Session 17
  • Michael Krivelevich, Daniel Reichman and Wojciech Samotij. Smoothed analysis on connected graphs
  • Varun Kanade, Elchanan Mossel and Tselil Schramm. Global and Local Information in Clustering Labeled Block Models
  • Reut Levi, Dana Ron and Ronitt Rubinfeld. Local Algorithms for Sparse Spanning Graphs
• Break
• 17:25 - 18:10 Session 18
  • Andreas Emil Feldmann, Jochen Koenemann, Neil Olver and Laura Sanita. On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
  • Michael Dinitz, Guy Kortsarz and Zeev Nutov. Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights