RANDOM/APPROX 2019 schedule
Room information: all plenary sessions and all RANDOM talks will take place in 32-G449. APPROX talks in parallel sessions will be in 32-D463. See directions here.
Friday 20th September
| 8:30-9:00 | Registration | |
| RANDOM Session 1 | APPROX Session 1 | |
| 9:00-9:20 | Svante Janson and Gregory Sorkin. Successive minimum spanning trees | Sagar Kale. Small Space Stream Summary for Matroid Center |
| 9:20-9:40 | Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal and Barna Saha.Connectivity of Random Annulus Graphs and the Geometric Block Model | Rajesh Jayaram and David P. Woodruff. Towards Optimal Moment Estimation in Streaming and Distributed Models |
| 9:40-10:00 | Michael Anastos, Peleg Michaeli and Samantha Petti. Thresholds in Random Motif Graphs | Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou.Improved Algorithms for Time Decay Streams |
| 10:00-10:20 | Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller and Angelika Steger. Maximum Label Propagation Algorithm on Sparse Random Graphs | Chi-Ning Chou, Zhixian Lei and Preetum Nakkiran. Tracking the l2 Norm with Constant Update Time |
| 10:20-10:40 | Grant Schoenebeck, Biaoshuai Tao and Fang-Yi Yu. Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization | Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games |
| 10:40-11:00 | Coffee break | |
| APPROX Session 2 | ||
| 11:00-11:20 | Suprovat Ghoshal, Anand Louis and Rahul Raychaudhury. Approximation Algorithms for Partially Colorable Graphs | |
| 11:20-11:40 | Kent Quanrud. Fast and Deterministic Approximations for k-Cut | |
| 11:40-12:00 | Devvrit, Ravishankar Krishnaswamy and Nived Rajaraman. Robust Correlation Clustering | |
| 12:00-12:20 | Ioana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt and Melanie Schmidt. On the cost of essentially fair clusterings | |
| 12:20-14:00 | Lunch break | |
| 14:00-15:00 | Invited talk Constantinos Daskalakis: Reducing AI Bias using Truncated Statistics | |
| RANDOM Session 2 | ||
| 15:10-15:30 | Vladimir Braverman, Dan Feldman, Harry Lang and Daniela Rus. Streaming Coresets for M-Estimators | |
| 15:30-15:50 | Amit Chakrabarti and Prantar Ghosh. Streaming Verification of Graph Computations via Graph Structure | |
| 15:50-16:10 | Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions | |
| 16:10-16:30 | Coffee break | |
| RANDOM Session 3 | APPROX Session 3 | |
| 16:30-16:50 | Bruce Spang and Mary Wootters.Unconstraining Graph-Constrained Group Testing | Sevag Gharibian and Ojas Parekh.Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut |
| 16:50-17:10 | Jack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan. Deterministic Approximation of Random Walks in Small Space | Reyna Hulett. Single-Elimination Brackets Fail to Approximate Copeland Winner |
| 17:10-17:30 | Roy Gotlib and Tali Kaufman. Testing Odd Direct Sums Using High Dimensional Expanders | Manuel Fernandez, David Woodruff and Taisuke Yasuda. The Query Complexity of Mastermind with lp Distances |
| 17:30-17:50 | Irit Dinur and Konstantin Golubev. Direct Sum Testing: the General Case | Neeraj Kumar, Stavros Sintos and Subhash Suri. The Maximum Exposure Problem |
| 18:00-19:30 | Reception |
Saturday 21st September
| RANDOM Session 4 | APPROX Session 4 | |
| 9:00-9:20 | Sarah Cannon, Joshua Daymude, Cem Gokmen, Dana Randall and Andréa Richa.A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems | Devanathan Thiruvenkatachari, Euiwoong Lee, Subhash Khot and Prahladh Harsha. Improved Hardness for 3LIN via Linear Label Cover |
| 9:20-9:40 | Michael Anastos and Alan Frieze. On a connectivity threshold for colorings of random graphs and hypergraphs | Per Austrin and Aleksa Stankovic.Global cardinality constraints make approximating some Max-2-CSPs harder |
| 9:40-10:00 | Josep Diaz and Mordecai J. Golin. The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions | Venkatesan Guruswami and Sai Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms |
| 10:00-10:20 | Domagoj Bradac, Sahil Singla and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing | Dhruv Rohatgi. Conditional Hardness of Earth Mover Distance |
| 10:20-10:40 | Zongchen Chen and Santosh Vempala.Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions | Eric Allender, Martin Farach-Colton and Meng-Tsung Tsai.Syntactic Separation of Subset Satisfiability Problems |
| 10:40-11:00 | Coffee break | |
| APPROX Session 5 | ||
| 11:00-11:20 | Alexander Birx, Yann Disser and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line | |
| 11:20-11:40 | Susanne Albers, Arindam Khan and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model | |
| 11:40-12:00 | Alon Eden, Uriel Feige and Michal Feldman. Max-Min Greedy Matching | |
| 12:00-12:20 | Ilan Reuven Cohen, Alon Eden, Amos Fiat and Łukasz Jeż. Dynamic Pricing of Servers on Trees | |
| 12:20-14:00 | Lunch break | |
| 14:00-15:00 | Invited talk Shuchi Chawla: Online resource allocation, pricing, and prophet inequalities | |
| RANDOM Session 5 | ||
| 15:10-15:30 | Ray Li and Mary Wootters. Lifted Multiplicity Codes | |
| 15:30-15:50 | Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf and Shashwat Silas. On List Recovery of High-Rate Tensor Codes | |
| 15:50-16:10 | Frank Ban, Xi Chen, Rocco Servedio and Sandip Sinha. Efficient average-case population recovery in the presence of insertions and deletions | |
| 16:10-16:30 | Coffee break | |
| RANDOM Session 6 | APPROX Session 6 | |
| 16:30-16:50 | Thomas Watson and Mika Göös. A Lower Bound for Sampling Disjoint Sets | Dimitris Fotakis, Jannik Matuschke and Orestis Papadigenopoulos.Malleable scheduling beyond identical machines |
| 16:50-17:10 | Amos Beimel, Kobbi Nissim and Mohammad Zaheri. Exploring Differential Obliviousness | Rajan Udwani and Andreas Schulz. Robust Appointment Scheduling with Heterogeneous Costs |
| 17:10-17:30 | Shyam Narayanan. Pairwise Independent Random Walks can be Slightly Unbounded | D Ellis Hershkowitz, R. Ravi and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty |
| 17:30-17:50 | Meena Jagadeesan. Simple Analysis of Sparse, Sign-Consistent JL | |
| 17:50-18:10 | Ioannis Emiris, Vasilis Margonis and Ioannis Psarros. Near neighbor preserving dimension reduction for doubling subsets of l_1 |
Sunday 22nd September
| RANDOM Session 7 | APPROX Session 7 | |
| 9:00-9:20 | Andrej Bogdanov, Nikhil Mande, Justin Thaler and Christopher Williamson.Approximate degree, secret sharing, and concentration phenomena | Eden Chlamtac, Michael Dinitz and Thomas Robinson. Approximating the Norms of Graph Spanners |
| 9:20-9:40 | Ronitt Rubinfeld and Arsen Vasilyan.Approximating the noise sensitivity of a monotone Boolean function | Arnold Filtser. On Strong Diameter Padded Decompositions |
| 9:40-10:00 | Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0 | Alexander Golovnev, Alexander Kulikov, Alexander Logunov, Ivan Mikhailin and Maksim Nikolaev. Collapsing Superstring Conjecture |
| 10:00-10:20 | V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay.Efficient Black-Box Identity Testing for Free Group Algebras | Timothy Carpenter, Ario Salmasi and Anastasios Sidiropoulos. Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion |
| 10:20-10:40 | Alexander Golovnev, Mika Goos, Daniel Reichman and Igor Shinkar.String Matching: Communication, Circuits, and Learning | Gary Miller, Noel Walkington and Alex Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues |
| 10:40-11:00 | Coffee break | |
| RANDOM Session 8 | APPROX Session 8 | |
| 11:00-11:20 | Dean Doron, Amnon Ta-Shma, Avraham Ben-Aroya and Gil Cohen.Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions | Benjamin Moseley and Maxim Sviridenko. Submodular Optimization with Contention Resolution Extensions |
| 11:20-11:40 | Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic Sources | Umang Bhaskar and Gunjan Kumar.The Complexity of Partial Function Extension for Coverage Functions |
| 11:40-12:00 | Rohit Agrawal. Samplers and extractors for unbounded functions | Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell and Nabil Mustafa. Maximizing Covered Area in a Euclidean Plane with Connectivity Constraint |
| 12:00-12:20 | Rocco Servedio and Li-Yang Tan.Improved pseudorandom generators from pseudorandom multi-switching lemmas | |
| 12:20-14:00 | Lunch break | |
| RANDOM Session 9 | ||
| 14:00-14:20 | Zongchen Chen, Andreas Galanis, Leslie Goldberg, Will Perkins, James Stewart and Eric Vigoda. Fast algorithms at low temperatures via Markov chains | |
| 14:20-14:50 | Antonio Blanca, Reza Gheissari and Eric Vigoda. Random-cluster dynamics in Z^2: rapid mixing with general boundary conditions | |
| 14:50-15:10 | Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases | |
| 15:10-15:30 | Charilaos Efthymiou, Andreas Galanis, Thomas Hayes, Daniel Stefankovic and Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees | |
| 15:30-15:50 | Chao Liao, Jiabao Lin, Pinyan Lu and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs |
RANDOM: THE CONFERENCE 