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

RANDOM Session 1APPROX Session 1
9:00-9:20Svante Janson and Gregory Sorkin. Successive minimum spanning treesSagar Kale. Small Space Stream Summary for Matroid Center
9:20-9:40Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal and Barna Saha.Connectivity of Random Annulus Graphs and the Geometric Block ModelRajesh Jayaram and David P. Woodruff. Towards Optimal Moment Estimation in Streaming and Distributed Models
9:40-10:00Michael Anastos, Peleg Michaeli and Samantha Petti. Thresholds in Random Motif GraphsVladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou.Improved Algorithms for Time Decay Streams
10:00-10:20Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller and Angelika Steger. Maximum Label Propagation Algorithm on Sparse Random GraphsChi-Ning Chou, Zhixian Lei and Preetum Nakkiran. Tracking the l2 Norm with Constant Update Time
10:20-10:40Grant Schoenebeck, Biaoshuai Tao and Fang-Yi Yu. Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence MaximizationVenkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games
10:40-11:00Coffee break
APPROX Session 2
11:00-11:20Suprovat Ghoshal, Anand Louis and Rahul Raychaudhury. Approximation Algorithms for Partially Colorable Graphs
11:20-11:40Kent Quanrud. Fast and Deterministic Approximations for k-Cut
11:40-12:00Devvrit, Ravishankar Krishnaswamy and Nived Rajaraman. Robust Correlation Clustering
12:00-12:20Ioana 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:00Lunch break
14:00-15:00Invited talk
Constantinos Daskalakis: Reducing AI Bias using Truncated Statistics
RANDOM Session 2
15:10-15:30Vladimir Braverman, Dan Feldman, Harry Lang and Daniela Rus. Streaming Coresets for M-Estimators
15:30-15:50Amit Chakrabarti and Prantar Ghosh. Streaming Verification of Graph Computations via Graph Structure
15:50-16:10Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions
16:10-16:30Coffee break
RANDOM Session 3APPROX Session 3
16:30-16:50Bruce Spang and Mary Wootters.Unconstraining Graph-Constrained Group TestingSevag Gharibian and Ojas Parekh.Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut
16:50-17:10Jack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan. Deterministic Approximation of Random Walks in Small SpaceReyna Hulett. Single-Elimination Brackets Fail to Approximate Copeland Winner
17:10-17:30Roy Gotlib and Tali Kaufman. Testing Odd Direct Sums Using High Dimensional ExpandersManuel Fernandez, David Woodruff and Taisuke Yasuda. The Query Complexity of Mastermind with lp Distances
17:30-17:50Irit Dinur and Konstantin Golubev. Direct Sum Testing: the General CaseNeeraj Kumar, Stavros Sintos and Subhash Suri. The Maximum Exposure Problem

Saturday 21st September

RANDOM Session 4APPROX Session 4
9:00-9:20Sarah Cannon, Joshua Daymude, Cem Gokmen, Dana Randall and Andréa Richa.A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle SystemsDevanathan Thiruvenkatachari, Euiwoong Lee, Subhash Khot and Prahladh Harsha. Improved Hardness for 3LIN via Linear Label Cover
9:20-9:40Michael Anastos and Alan Frieze. On a connectivity threshold for colorings of random graphs and hypergraphsPer Austrin and Aleksa Stankovic.Global cardinality constraints make approximating some Max-2-CSPs harder
9:40-10:00Josep Diaz and Mordecai J. Golin. The Expected Number of Maximal Points of the Convolution of Two 2-D DistributionsVenkatesan Guruswami and Sai Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms
10:00-10:20Domagoj Bradac, Sahil Singla and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value ProbingDhruv Rohatgi. Conditional Hardness of Earth Mover Distance
10:20-10:40Zongchen Chen and Santosh Vempala.Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave DistributionsEric Allender, Martin Farach-Colton and Meng-Tsung Tsai.Syntactic Separation of Subset Satisfiability Problems
10:40-11:00Coffee break
APPROX Session 5
11:00-11:20Alexander Birx, Yann Disser and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line
11:20-11:40Susanne Albers, Arindam Khan and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model
11:40-12:00Alon Eden, Uriel Feige and Michal Feldman. Max-Min Greedy Matching
12:00-12:20Ilan Reuven Cohen, Alon Eden, Amos Fiat and Łukasz Jeż. Dynamic Pricing of Servers on Trees
12:20-14:00Lunch break
14:00-15:00Invited talk
Shuchi Chawla: Online resource allocation, pricing, and prophet inequalities
RANDOM Session 5
15:10-15:30Ray Li and Mary Wootters. Lifted Multiplicity Codes
15:30-15:50Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf and Shashwat Silas. On List Recovery of High-Rate Tensor Codes
15:50-16:10Frank Ban, Xi Chen, Rocco Servedio and Sandip Sinha. Efficient average-case population recovery in the presence of insertions and deletions
16:10-16:30Coffee break
RANDOM Session 6APPROX Session 6
16:30-16:50Thomas Watson and Mika Göös. A Lower Bound for Sampling Disjoint SetsDimitris Fotakis, Jannik Matuschke and Orestis Papadigenopoulos.Malleable scheduling beyond identical machines
16:50-17:10Amos Beimel, Kobbi Nissim and Mohammad Zaheri. Exploring Differential ObliviousnessRajan Udwani and Andreas Schulz. Robust Appointment Scheduling with Heterogeneous Costs
17:10-17:30Shyam Narayanan. Pairwise Independent Random Walks can be Slightly UnboundedD Ellis Hershkowitz, R. Ravi and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
17:30-17:50Meena Jagadeesan. Simple Analysis of Sparse, Sign-Consistent JL
17:50-18:10Ioannis Emiris, Vasilis Margonis and Ioannis Psarros. Near neighbor preserving dimension reduction for doubling subsets of l_1

Sunday 22nd September

RANDOM Session 7APPROX Session 7
9:00-9:20Andrej Bogdanov, Nikhil Mande, Justin Thaler and Christopher Williamson.Approximate degree, secret sharing, and concentration phenomenaEden Chlamtac, Michael Dinitz and Thomas Robinson. Approximating the Norms of Graph Spanners
9:20-9:40Ronitt Rubinfeld and Arsen Vasilyan.Approximating the noise sensitivity of a monotone Boolean functionArnold Filtser. On Strong Diameter Padded Decompositions
9:40-10:00Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0Alexander Golovnev, Alexander Kulikov, Alexander Logunov, Ivan Mikhailin and Maksim Nikolaev. Collapsing Superstring Conjecture
10:00-10:20V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay.Efficient Black-Box Identity Testing for Free Group AlgebrasTimothy Carpenter, Ario Salmasi and Anastasios Sidiropoulos. Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
10:20-10:40Alexander Golovnev, Mika Goos, Daniel Reichman and Igor Shinkar.String Matching: Communication, Circuits, and LearningGary Miller, Noel Walkington and Alex Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues
10:40-11:00Coffee break
RANDOM Session 8APPROX Session 8
11:00-11:20Dean 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:40Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic SourcesUmang Bhaskar and Gunjan Kumar.The Complexity of Partial Function Extension for Coverage Functions
11:40-12:00Rohit Agrawal. Samplers and extractors for unbounded functionsChien-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:20Rocco Servedio and Li-Yang Tan.Improved pseudorandom generators from pseudorandom multi-switching lemmas
12:20-14:00Lunch break
RANDOM Session 9
14:00-14:20Zongchen Chen, Andreas Galanis, Leslie Goldberg, Will Perkins, James Stewart and Eric Vigoda. Fast algorithms at low temperatures via Markov chains
14:20-14:50Antonio Blanca, Reza Gheissari and Eric Vigoda. Random-cluster dynamics in Z^2: rapid mixing with general boundary conditions
14:50-15:10Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases
15:10-15:30Charilaos Efthymiou, Andreas Galanis, Thomas Hayes, Daniel Stefankovic and Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees
15:30-15:50Chao Liao, Jiabao Lin, Pinyan Lu and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs