# Random Conference 2020 Program --- Welcome to Approx-Random 2020! The virtual conference to be held August 17-19 has three components: 1. A short 10 minute live presentation/Q&A on each paper. This will be the main substitute for the live conference. These will be over zoom and the schedule is below. For Approx sessions use [Zoom Room A](https://washington.zoom.us/j/95077625020); For Random sessions use [Zoom Room B](https://washington.zoom.us/j/97598941951). 2. Recorded 25 minute talks for each accepted paper available on youtube. (Linked to in the schedule below; thanks to Eshan Chattopadhyay for maintaining this). 3. Invited talks and a gather.town event on August 18th. Please follow [this link](https://gather.town/oQ2wR8MCHb5FRJ5K/APPROX-RANDOM-2020). The proceedings of the conference are available freely via [LIPICS](https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16157). Here you will find the detailed schedule for talks from RANDOM. The schedule for the sister conference APPROX is [here](https://approxconference.wordpress.com/random-approx-2020-schedule/). --- ### Monday 17th August (Chair Mary Wootters) --- All times are in Pacific Daylight time. Summary schedule: | | Approx | Random| |---|---|--- 7-7:40 | Approx Session 1| 7:40-8 | **Break** | **Break** 8-8:40 | Approx Session 2 | Random Session 1 <iframe width="400" height="220" src="https://www.youtube.com/embed/GbStM864xzY" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 8:40 - 9 | **Break**| **Break** 9-9:55 | [Invited Talk](https://washington.zoom.us/j/97598941951) | [Invited Talk](https://washington.zoom.us/j/97598941951) <iframe width="400" height="220" src="https://www.youtube.com/embed/0frz9RLgiQc" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:20-11 | Approx Session 3| Random Session 2 <iframe width="400" height="220" src="https://www.youtube.com/embed/VJc2FD46e70" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11-11:20 | **Break** | **Break** 11:20-12 | | Random Session 3 <iframe width="400" height="220" src="https://www.youtube.com/embed/whDqDJ0tAIw" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - **Invited talk 9-9:55: [Shachar Lovett](https://cseweb.ucsd.edu/~slovett/home.html) - Point location: an interface between geometry, machine learning and complexity** :::spoiler Abstract Point location is a basic problem in discrete and computational geometry. A given a set of hyperplanes in d-dimensional space partitions the space into cells. Given an input point, the goal is to find as efficiently as possible to which cell it belongs. This problem is tightly connected to the problem of active learning in machine learning, where the goal is to infer the labels of unlabeled data points, while making a small number of queries; and to complexity theory, in particular to the complexity of certain key problems (such as 3-SUM) in the linear decision tree model. In this talk, I will describe these connections, some recent results and the challenges that remain. Based on joint works with Max Hopkins, Daniel Kane, Gaurav Mahajan, Shay Moran and Jiapeng Zhang. | | [Zoom link](https://washington.zoom.us/j/97598941951) | Recorded Full Talks| | -------- | --------|--- | 8 | Ronen Shaltiel. [Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12613)| <iframe width="400" height="220" src="https://www.youtube.com/embed/AL7pMtZIz64" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> |8:10 | Sumegha Garg, Pravesh K. Kothari and Ran Raz. [Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12624)| <iframe width="400" height="220" src="https://www.youtube.com/embed/g7dzpPLM8KY" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> |8:20 | Shuichi Hirahara and Osamu Watanabe. [On Nonadaptive Security Reductions of Hitting Set Generators](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12618) | <iframe width="400" height="220" src="https://www.youtube.com/embed/n-nHvsMxSlk" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 8:30 | Shalev Ben-David, Mika Göös, Robin Kothari and Thomas Watson. [When Is Amplification Necessary for Composition in Randomized Query Complexity?](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12631) | <iframe width="400" height="220" src="https://www.youtube.com/embed/W8RJEfth7hs" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 8:40-9 | **Break** 9-9:55 | [**Invited talk by Shachar Lovett**](https://washington.zoom.us/j/97598941951) 10-10:20| **Break**. |10:20 | Eric Blais and Abhinav Bommireddi. [On testing and robust characterizations of convexity](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12621) | <iframe width="400" height="220" src="https://www.youtube.com/embed/IO7devZDo7Q" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> |10:30 | Eric Price and Jonathan Scarlett. [A Fast Binary Splitting Approach to Non-Adaptive Group Testing](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12616) | <iframe width="400" height="220" src="https://www.youtube.com/embed/F_hG-gM8xWE" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> |10:40 | Artur Czumaj, Hendrik Fichtenberger, Pan Peng and Christian Sohler. [Testable Properties in General Graphs and Random Order Streaming](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12619) | <iframe width="400" height="220" src="https://www.youtube.com/embed/SDN3S29unfU" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> |10:50 | Jeff Phillips and Wai Ming Tai. [The Gaussian Sketch for Almost Relative Error Kernel Distance](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12615) | <iframe width="400" height="220" src="https://www.youtube.com/embed/wb85BX_Fado" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11-11:20|**Break**. 11:20| Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty and Mrinal Kumar. [On Multilinear Forms: Bias, Correlation, and Tensor Rank](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12632) | <iframe width="400" height="220" src="https://www.youtube.com/embed/aKJCHxMFMgQ" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:30| Markus Bläser and Anurag Pandey. [Polynomial identity testing for low degree polynomials with optimal randomness](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12611) | <iframe width="400" height="220" src="https://www.youtube.com/embed/ubZhxGhYqZg" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:40| Zeyu Guo and Rohit Gurjar. [Improved explicit hitting-sets for ROABPs](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12607)| <iframe width="400" height="220" src="https://www.youtube.com/embed/zZ5g3KTMTRU" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:50| Dean Doron, Amnon Ta-Shma and Roei Tell. [On Hitting-Set Generators for Polynomials that Vanish Rarely](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12610) | <iframe width="400" height="220" src="https://www.youtube.com/embed/b1NUI_Q_l1c" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> --- ### Tuesday August 18 (Chair Tselil Schramm) --- All times are in Pacific Daylight time. Summary schedule: | | Approx | Random| |---|---|--- 7-7:40 | Approx Session 4| 7:40-8 | **Break** | **Break** 8-8:40 | Approx Session 5 | 8:40 - 9 | **Break**| **Break** 9-9:55 | [Gather event](https://gather.town/oQ2wR8MCHb5FRJ5K/APPROX-RANDOM-2020) | [Gather event](https://gather.town/oQ2wR8MCHb5FRJ5K/APPROX-RANDOM-2020) 10:20-11 | Approx Session 6| Random Session 4 <iframe width="400" height="220" src="https://www.youtube.com/embed/RE_OVolpUeA" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11-11:20 | **Break** | **Break** 11:20-12 | | Random Session 5 <iframe width="400" height="220" src="https://www.youtube.com/embed/fWL1wz_jOmc" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - **Social Event 9-10:20: Gather** :::spoiler Instructions Just [follow this link](https://gather.town/oQ2wR8MCHb5FRJ5K/APPROX-RANDOM-2020) and have a good microphone/camera setup. | | [Zoom link](https://washington.zoom.us/j/97598941951) | Recorded Full Talks| | -------- | --------|--- 10:20 | Sarah Miracle, Amanda Streib and Noah Streib. [Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov chains](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12606). |<iframe width="400" height="220" src="https://www.youtube.com/embed/YtQ9SAp4qHs" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:30 | Noga Alon and Sepehr Assadi. [Palette Sparsification Beyond (Delta+1) Vertex Coloring](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12609) | <iframe width="400" height="220" src="https://www.youtube.com/embed/kkHnQyFSwLM" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:40 | Jan Dreier, Philipp Kuinke and Peter Rossmanith. [Maximum Shallow Clique Minors in Preferential Attachment Graphs have Polylogarithmic Size](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12617) | <iframe width="400" height="220" src="https://www.youtube.com/embed/rOkAFufMqDQ" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:50 | Amit Chakrabarti, Prantar Ghosh and Justin Thaler. [Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12625)|<iframe width="400" height="220" src="https://www.youtube.com/embed/Rq56TXPh4Co" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11 - 11:20 | **Break**. 11:20 | Reut Levi and Moti Medina. [Distributed Testing of Graph Isomorphism in the CONGEST model](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12622)|<iframe width="400" height="220" src="https://www.youtube.com/embed/jtMClhkgrQA" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:30 | Dana Ron and Asaf Rosin. [Almost Optimal Distribution-Free Sample-Based Testing of k-Modality](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12630) | <iframe width="400" height="220" src="https://www.youtube.com/embed/hU24iNhmfBY" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:40 | Nader Bshouty. [Almost Optimal Testers for Concise Representations](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12608) | <iframe width="400" height="220" src="https://www.youtube.com/embed/NznLQ8kZj90" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:50 | Clément Canonne and Karl Wimmer. [Testing Data Binnings](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12627) | <iframe width="400" height="220" src="https://www.youtube.com/embed/hapTAqpaPlQ" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 12 | Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra and Manaswi Paraashar. [Disjointness through the Lens of VC-dimension: Sparsity and Beyond](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12626) | <iframe width="400" height="220" src="https://www.youtube.com/embed/AgSshF_2PWc" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> --- ### Wednesday August 19 (Chair Avishay Tal) --- All times are in Pacific Daylight time. Summary schedule: | | Approx | Random| |---|---|--- 7-7:40 | Approx Session 7| 7:40-8 | **Break** | **Break** 8-8:40 | Approx Session 8 | 8:40 - 9 | **Break**| **Break** 9-9:55 | [Invited Talk](https://washington.zoom.us/j/95077625020) | [Invited Talk](https://washington.zoom.us/j/95077625020) 10:20-11 | Approx Session 9| Random Session 6 <iframe width="400" height="220" src="https://www.youtube.com/embed/c2dONduByfw" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11-11:20 | **Break** | **Break** 11:20-12 | | Random Session 7 <iframe width="400" height="220" src="https://www.youtube.com/embed/FSrqUY4wxzM" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - **Invited talk 9-9:55: [Nathan Klein](https://homes.cs.washington.edu/~nwklein/) - [A (Slightly) Improved Approximation Algorithm for Metric TSP](https://arxiv.org/abs/2007.01409)**. [[Zoom Link]](https://washington.zoom.us/j/95077625020) :::spoiler Abstract In this talk, I will describe recent work in which we obtain a $3/2-\epsilon$ approximation algorithm for metric TSP, for some $\epsilon>10^{-36}$. This slightly improves over the classical $3/2$ approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk will focus on giving an overview of the key ideas involved. This is joint work with Anna Karlin and Shayan Oveis Gharan. | | [Zoom link](https://washington.zoom.us/j/97598941951) | Recorded Full Talks| | -------- | --------|---- 10:20 | Kwangjun Ahn. [A Simpler Strong Refutation of Random k-XOR](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12605) | <iframe width="400" height="220" src="https://www.youtube.com/embed/cMVk3GU3XOg" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:30 | Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro and Noah Stephens-Davidowitz. [Extractor lower bounds, revisited](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12604)| <iframe width="400" height="220" src="https://www.youtube.com/embed/JpHcqsqMFr0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:40 | Nicolas Resch, Venkatesan Guruswami, Jonathan Mosheiff, Ray Li, Shashwat Silas and Mary Wootters. [Bounds for list-decoding and list-recovery of random linear codes](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12612) | <iframe width="400" height="220" src="https://www.youtube.com/embed/M_6lPFudBbY" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 10:50 | Aditya Potukuchi and Ben Lund. [On the list recoverability of randomly punctured codes](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12633) | <iframe width="400" height="220" src="https://www.youtube.com/embed/3KGBMaaHuo0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11 - 11:20| **Break**. 11:20 | Tali Kaufman and Ella Sharakanski. [Chernoff Bound for High-Dimensional Expanders](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12628). | <iframe width="400" height="220" src="https://www.youtube.com/embed/iItBMQL0Ix0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:30 | Calvin Beideman, Karthekeyan Chandrasekaran and Chao Xu. [Multicriteria cuts and size-constrained k-cuts in hypergraphs](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12620) | <iframe width="400" height="220" src="https://www.youtube.com/embed/1OLFDBSclBk" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:40 | Linh Tran and Van Vu. [Reaching a Consensus on Random Networks: The Power of Few](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12623) | <iframe width="400" height="220" src="https://www.youtube.com/embed/6jKWcV65Fr0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 11:50 | Cyrus Rashtchian, David P. Woodruff and Hanlin Zhu. [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12629) | <iframe width="400" height="220" src="https://www.youtube.com/embed/TZQXAy8vT8o" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> 12 | Ali Pourmiri, Catherine Greenhill and Bernard Mans. [Balanced Allocation on Dynamic Hypergraphs](https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12614). | <iframe width="400" height="220" src="https://www.youtube.com/embed/GAclpqEk6vQ" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
Last changed by  
 
Raghu Meka
2733

Read more

Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

4/24/2024
Research

My main interests are in complexity theory, learning theory, algorithm design. More generally, I like probability and combinatorics related things. The best resource for up to date publications really is to look up my profile on Google scholar.

2/29/2024
Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

2/23/2024
Teaching

Here are the courses I have taught or will in the future.

2/23/2024
Read more from Raghu Meka
Published on HackMD