CINXE.COM

<!DOCTYPE html> <html> <head> <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css"> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1"> <link rel="stylesheet" type="text/css" href="http://itcsconf.github.io/style.css"> <title>ITCS 2023 - Program and Schedule</title> <style> .time_info { vertical-align: top; padding: 15px; border: 1px solid black; border-collapse: collapse; } .session_info { padding: 10px; border: 1px solid black; border-collapse: collapse; } .date { padding: 10px; vertical-align: middle; text-align: left; background-color: #ff8c00; border: 1px solid black; } .marked { background-color: #f9d4a6; vertical-align: middle; } .break { vertical-align: middle; } </style> </head> <body style="background-color: white;" class> <div id="header"></div> <div id="pg-wrapper"> <div class="container-fluid" id="all-but-header"> <div class="row"> <div class="col-md-11"> <p> <img style="float: right; padding-bottom: 20px;" id="itcs-logo" src="https://itcsconf.github.io/images/itcs_logo.png"> <h1>ITCS 2023 Program and Schedule</h1> </p> <p style="clear: both;"> Welcome to ITCS 2023. The conference will run in a single track and all sessions will take place at the Stata center room 32-G449 and overflow room 32-D463. <br> <big> <strong> All times are in EST. </strong> </big> </p> <table style="width: 100%"> <tr> <td class="date" colspan="2"> <h3><strong>Tuesday, January 10th</strong></h3> </td> </tr> <tr> <td class="time_info marked"><strong>9:40am - 9:50am<br>Yael Kalai</strong> </td> <td class="session_info marked"> Welcoming remarks. </td> </tr><tr> <td class="time_info "> <strong> Session 1 <br> 9:50am-10:50am <br> Chair: Raghuvansh Saxena </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Exponential separations using guarded extension variables </strong> <a href="https://youtu.be/rP-h9uLagYY">Video</a> </td></tr> <tr><td>Authors: Emre Yolcu, Marijn Heule (Carnegie Mellon University) </td></tr><tr> <td><strong> Certificate games </strong> <a href="https://youtu.be/6p05k5JlxP0">Video</a> </td></tr> <tr><td>Authors: Sourav Chakraborty (Indian Statistical Institute (ISI) , Kolkata, India); Anna Gal (University of Texas at Austin); Sophie Laplante (Universit茅 Paris Cit茅); Rajat Mittal (Indian Institute of Technology Kanpur); Anupa Sunny (Universit茅 Paris Cit茅) </td></tr><tr> <td><strong> Downward self-reducibility in TFNP </strong> <a href="https://youtu.be/5gk2O8v2HZA">Video</a> </td></tr> <tr><td>Authors: Prahladh Harsha (TIFR, Mumbai); Daniel Mitropolsky (Columbia University); Alon Rosen (Bocconi University and Reichman University) </td></tr><tr> <td><strong> Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP </strong> <a href="https://youtu.be/k-Z_KhCF9_k">Video</a> </td></tr> <tr><td>Authors: Amol Pasarkar, Christos Papadimitriou, Mihalis Yannakakis (Columbia University) </td></tr><tr> <td><strong> PPP-Completeness and Extremal Combinatorics </strong> <a href="https://youtu.be/xPZ6v0kCJ-8">Video</a> </td></tr> <tr><td>Authors: Romain Bourneuf (ENS de Lyon); Luk谩拧 Folwarczn媒, Pavel Hub谩膷ek (Charles University); Alon Rosen (Bocconi University and Reichman University); Nikolaj Ignatieff Schwartzbach (Aarhus University) </td></tr> </tbody></table> </td> </tr><tr> <td class="time_info "> <strong> Session 2 <br> 11:00am-12:00pm <br> Chair: John Wright </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Rigidity for Monogamy-of-Entanglement Games </strong></td></tr> <tr><td>Authors: Anne Broadbent, Eric Culf (University of Ottawa) </td></tr><tr> <td><strong> Quantum algorithms and the power of forgetting </strong> <a href="https://youtu.be/fyQkGMCjAZY">Video</a> </td></tr> <tr><td>Authors:Amin Shiraz Gilani, Andrew M. Childs, Matthew Coudron (University of Maryland) </td></tr><tr> <td><strong> Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement </strong> <a href="https://youtu.be/bA2WPdZaDB8">Video</a> </td></tr> <tr><td>Authors: Dorian Rudolph, Sevag Gharibian (Universit盲t Paderborn) </td></tr><tr> <td><strong> Unitary property testing lower bounds by polynomials </strong> <a href="https://youtu.be/pvzILHVzcws">Video</a> </td></tr> <tr><td>Authors: Adrian She (University of Toronto); Henry Yuen (Columbia University) </td></tr><tr> <td><strong> Fractional certificates for bounded functions </strong> <a href="https://youtu.be/7hsxWpUtePU">Video</a> </td></tr> <tr><td>Authors: Shachar Lovett (University of California San Diego); Jiapeng Zhang (University of Southern California) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>12:00pm- 1:40pm</strong> </td> <td class="session_info marked"> Lunch break (on your own). </td> <tr> <td class="time_info "> <strong> Session 3 <br> 1:40pm-2:40pm <br> Chair: Alex Lombardi </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Learning versus Pseudorandom Generators in Constant Parallel Time </strong> <a href="https://youtu.be/4MSWbKeVOGA">Video</a> </td></tr> <tr><td>Authors: Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology) </td></tr><tr> <td><strong> Kolmogorov Complexity Characterizes Statistical Zero Knowledge </strong> <a href="https://youtu.be/E7n_gBsdjlU">Video</a> </td></tr> <tr><td>Authors: Eric Allender (Rutgers University); Shuichi Hirahara (National Institute of Informatics); Harsha Tirumala (Rutgers University) </td></tr><tr> <td><strong> On Low-End Obfuscation and Learning </strong></td></tr> <tr><td>Authors: Elette Boyle (Reichman University and NTT Research); Yuval Ishai (Technion); Pierre Meyer (Reichman University and IRIF, Universit茅 Paris Cit茅, CNRS); Robert Robere (McGill); Gal Yehuda (Technion) </td></tr><tr> <td><strong> Bootstrapping Homomorphic Encryption via Functional Encryption </strong> <a href="https://youtu.be/X5N8uRrTy9U">Video</a> </td></tr> <tr><td>Authors: Nir Bitansky, Tomer Solomon (Tel Aviv University) </td></tr><tr> <td><strong> Incompressiblity and Next-Block Pseudoentropy </strong> <a href="https://youtu.be/AR8JhEw-wEs">Video</a> </td></tr> <tr><td>Authors: Iftach Haitner, Noam Mazor, Jad Silbak (Tel Aviv University) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 4 <br> 2:50pm-3:50pm <br> Chair: Raghuvansh Saxena </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Differentially Private Continual Releases of Streaming Frequency Moment Estimations </strong> <a href="https://youtu.be/se4FdIIgHdo">Video</a> </td></tr> <tr><td>Authors: Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong (Google Research) </td></tr><tr> <td><strong> A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators </strong> <a href="https://youtu.be/l8botDXqD_M">Video</a> </td></tr> <tr><td>Authors: Idan Attias (Ben-Gurion University); Edith Cohen (Google and Tel Aviv University); Moshe Shechner (Tel Aviv University); Uri Stemmer (Google and Tel Aviv University) </td></tr><tr> <td><strong> Expander Decomposition in Dynamic Streams </strong> <a href="https://youtu.be/bIrxfK5vb9c">Video</a> </td></tr> <tr><td>Authors: Arnold Filtser (Bar-Ilan University); Michael Kapralov, Mikhail Makarov (EPFL) </td></tr><tr> <td><strong> All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method </strong> <a href="https://youtu.be/R2PJ6ptmLW0">Video</a> </td></tr> <tr><td>Authors: Sepehr Assadi, Aaron Bernstein, Zachary Langley (Rutgers University) </td></tr><tr> <td><strong> Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly </strong> <a href="https://youtu.be/eFcXiu088J0">Video</a> </td></tr> <tr><td>Authors: Gillat Kol (Princeton University), Dmitry Paramonov (Princeton University); Raghuvansh Saxena (Microsoft Research); Huacheng Yu (Princeton University) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>3:50pm- 4:20pm</strong> </td> <td class="session_info marked"> Break. </td> <tr> <td class="time_info "> <strong> Session 5 <br> 4:20pm-5:30pm <br> Chair: Sam Hopkins </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Exact Completeness of LP Hierarchies for Linear Codes </strong> <a href="https://youtu.be/X8hDsnn2P1k">Video</a> </td></tr> <tr><td>Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo (Institute for Advanced Study); Chris Jones (University of Chicago) </td></tr> <tr> <td><strong> Is This Correct? Let's Check! </strong> <a href="https://youtu.be/YvdMmXJCfnA">Video</a> </td></tr> <tr><td>Authors: Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel (MIT); Madhu Sudan (Harvard University) </td></tr> <tr><td> <strong> An Improved Lower Bound for Matroid Intersection Prophet inequalities </strong> <a href="https://youtu.be/osGnFE9zt18">Video</a> </td></tr> <tr><td>Authors: Raghuvansh R. Saxena (Microsoft), Santhoshini Velusamy (Harvard University), S. Matthew Weinberg (Princeton University) </td></tr> <tr> <td><strong> Matroid Partition Property and the Secretary Problem </strong> <a href="https://youtu.be/qYEE3M-fxeY">Video</a> </td></tr> <tr><td>Authors: Dorna Abdolazimi, Anna Karlin, Nathan Klein, Shayan Oveis Gharan (University of Washington) </td></tr><tr> <td><strong> Is Untrusted Randomness Helpful? </strong> <a href="https://youtu.be/K5lajocgMZo">Video</a> </td></tr> <tr><td>Authors: Uma Girish, Ran Raz, Wei Zhan (Princeton University) </td></tr><tr> <td><strong> Is it easier to count communities than find them? </strong> <a href="https://youtu.be/ToMEPZTn7sE">Video</a> </td></tr> <tr><td>Authors: Cynthia Rush (Columbia); Fiona Skerman (Uppsala University); Alexander S Wein (UC Davis); Dana Yang (Cornell) </td></tr></tbody></table></tr> <tr> <td class="date" colspan="2"> <h3><strong>Wednesday, January 11th</strong></h3> </td> </tr> <tr> <td class="time_info "> <strong> Session 6 <br> 10:00am - 11:00am<br> Chair: Nikhil Srivastava</td> <td class = "session_info"><table><tbody> <tr> <td><strong> Bit Complexity of Jordan Normal Form and Spectral Factorization </strong> <a href="https://youtu.be/wVBRQ_ZUteE">Video</a> </td></tr> <tr><td>Authors: Nikhil Srivastava (UC Berkeley); Ravindran Kannan (Microsoft Reseach India); Nick Ryder (OpenAI); Papri Dey (Georgia Tech) </td></tr> <tr> <td><strong> Matrix multiplication via matrix groups </strong> <a href="https://youtu.be/xoM4nm_I8FM">Video</a> </td></tr> <tr><td>Authors: Jonah Blasiak (Department of Mathematics, Drexel University); Henry Cohn (Microsoft Research New England); Joshua A. Grochow (Departments of Computer Science and Mathematics, University of Colorado Boulder); Kevin Pratt (School of Computer Science, Carnegie Mellon University); Chris Umans (Department of Computing and Mathematical Sciences, California Institute of Technology) </td></tr> <tr> <td><strong> Efficient algorithms for certifying lower bounds on the discrepancy of random matrices </strong> <a href="https://youtu.be/B1WkKcU0Xfo">Video</a> </td></tr> <tr><td>Authors: Prayaag Venkat (Harvard) </td></tr> <tr> <td><strong> Symmetric Formulas for Products of Permutations </strong> <a href="https://youtu.be/eb35UmOLcrU">Video</a> </td></tr> <tr><td>Authors: William He, Benjamin Rossman (Duke University) </td></tr> <tr> <td><strong> On Identity Testing and Noncommutative Rank Computation over the Free Skew Field </strong> <a href="https://youtu.be/xVplqhq-HNU">Video</a> </td></tr> <tr><td>Authors: V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai); Abhranil Chatterjee (Indian Institute of Technology Bombay, India); Utsab Ghosal, Partha Mukhopadhyay (Chennai Mathematical Institute); Ramya C (Institute of Mathematical Sciences) </td></tr> </tbody></table></tr> <tr> <td class="time_info "> <strong> Session 7 <br> 11:10am-12:10pm <br> Chair: Avishay Tal </td> <td class = "session_info"><table><tbody> <tr> <td><strong> The Strength of Equality Oracles in Communication </strong> <a href="https://youtu.be/gAyNWStwaVY">Video</a> </td></tr> <tr><td>Authors: Toniann Pitassi (Columbia University); Morgan Shirley (University of Toronto); Adi Shraibman (The Academic College of Tel Aviv-Yaffo) </td></tr><tr> <td><strong> Communication Complexity of Inner Product in Symmetric Normed Spaces </strong></td></tr> <tr><td>Authors: Jaroslaw Blasiok, Alexandr Andoni (Columbia University); Arnold Filtser (Bar Ilan University) </td></tr><tr> <td><strong> TFNP Characterizations of Proof Systems and Monotone Circuits </strong> <a href="https://youtu.be/84CDHMHyZDY">Video</a> </td></tr> <tr><td>Authors: Noah Fleming (Memorial University); Sam Buss, Russell Impagliazzo (University of California, San Diego) </td></tr><tr> <td><strong> On disperser/lifting properties of the Index and Inner-Product functions </strong> <a href="https://youtu.be/cDOqZ1s_9g8">Video</a> </td></tr> <tr><td>Authors: Paul Beame (University of Washington); Sajin Koroth (University of Victoria) </td></tr><tr> <td><strong> Lifting to Parity Decision Trees Via Stifling </strong> <a href="https://youtu.be/xcnn6jVNY0o">Video</a> </td></tr> <tr><td>Authors: Arkadev Chattopadhyay (TIFR, Mumbai); Nikhil S. Mande (CWI and QuSoft,amsterdam); Swagato Sanyal (IIT Kharagpur); Suhail Sherif (Vector Institute, Toronto) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>12:10pm- 1:50pm</strong> </td> <td class="session_info marked"> Lunch break (on your own). </td> <tr> <td class="time_info "> <strong> Session 8 <br> 1:50pm- 2:50pm<br> Chair: John Wright </td> <td class = "session_info"><table><tbody> <tr> <td>馃弳<strong><span style="color:DarkRed"> Best Student Paper:</span> Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom </strong> <a href="https://youtu.be/-osdMWjIcq8">Video</a> </td></tr> <tr><td>Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang (University of Texas at Austin) </td></tr><tr> <td><strong> Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations </strong> <a href="https://youtu.be/Ugwm72aWXIs">Video</a> </td></tr> <tr><td>Authors: Anurag Anshu (Harvard University); Tony Metger (ETH Zurich) </td></tr><tr> <td><strong> A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit </strong> <a href="https://youtu.be/UCvJtQz0Slw">Video</a> </td></tr> <tr><td>Authors: Hamza Fawzi (University of Cambridge); Omar Fawzi (Inria, ENS de Lyon); Samuel Scalet (University of Cambridge) </td></tr><tr> <td><strong> Quantum majority vote </strong></td></tr> <tr><td>Authors: Harry Buhrman (QuSoft, CWI, University ofamsterdam); Noah Linden (University of Bristol); Laura Man膷inska (University of Copenhagen); Ashley Montanaro (Phasecraft Ltd, University of Bristol); Maris Ozols (QuSoft, University ofamsterdam) </td></tr><tr> <td><strong> Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses </strong> <a href="https://youtu.be/Y4_21NpO0bM">Video</a> </td></tr> <tr><td>Authors: Chris Jones, Kunal Marwaha (University of Chicago); Juspreet Singh Sandhu (Harvard University); Jonathan Shi (Bocconi University) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 9 <br> 3:00pm-3:50pm <br> Chair: Brendan Lucier </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Beyond Worst-Case Budget-Feasible Mechanism Design </strong> <a href="https://youtu.be/n4xFqlbdj9E">Video</a> </td></tr> <tr><td>Authors: Aviad Rubinstein, Junyao Zhao (Stanford University) </td></tr><tr> <td><strong> Strategyproof Scheduling with Predictions </strong> <a href="https://youtu.be/POBOLMVIXnE">Video</a> </td></tr> <tr><td>Authors: Eric Balkanski (Columbia University); Vasilis Gkatzelis, Xizhi Tan (Drexel University) </td></tr><tr> <td><strong> Opponent Indifference in Rating Systems: A Theoretical Case for Sonas </strong> <a href="https://youtu.be/0RpxE2HZXNc">Video</a> </td></tr> <tr><td>Authors: Greg Bodwin, Forest Zhang (University of Michigan) </td></tr><tr> <td><strong> The Complexity of Infinite-Horizon General-Sum Stochastic Games </strong> <a href="https://youtu.be/dc3RE0DlQis">Video</a> </td></tr> <tr><td>Authors: Yujia Jin (Stanford University); Vidya Muthukumar (Georgia Institute of Technology); Aaron Sidford (Stanford University) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>3:50pm- 4:20pm</strong> </td> <td class="session_info marked"> Break. </td> <tr> <td class="time_info "> <strong> Session 10 <br> 4:20pm- 5:10pm<br> Chair: Adam Smith </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Necessary Conditions in Multi-Server Differential Privacy </strong> <a href="https://youtu.be/mAuHz4N79m0">Video</a> </td></tr> <tr><td>Authors: Albert Cheu, Chao Yan (Georgetown University) </td></tr><tr> <td><strong> Generalized Private Selection and Testing with High Confidence </strong> <a href="https://youtu.be/SivSahmUlGY">Video</a> </td></tr> <tr><td>Authors: Edith Cohen (Google Research and Tel Aviv University); Xin Lyu (UC Berkeley); Jelani Nelson (UC Berkeley & Google Research); Tam谩s Sarl贸s (Google Research); Uri Stemmer (Tel Aviv University and Google Research) </td></tr><tr> <td><strong> Private Counting of Distinct and k-Occurring Items in Time Windows </strong> <a href="https://youtu.be/K1QFgoiF4mE">Video</a> </td></tr> <tr><td>Authors: Badih Ghazi, Ravi Kumar (Google); Pasin Manurangsi (Google Research); Jelani Nelson (UC Berkeley & Google Research) </td></tr><tr> <td><strong> Algorithms with More Granular Differential Privacy Guarantees </strong> <a href="https://youtu.be/F_BqYXyQTRo">Video</a> </td></tr> <tr><td>Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke (Google Research) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 11 <br> 5:20pm-6:00pm <br> Chair: Adam Smith </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Loss Minimization through the lens of Outcome Indistinguishability </strong> <a href="https://youtu.be/vzaW87RrSDk">Video</a> </td></tr> <tr><td>Authors: Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Michael P. Kim (UC Berkeley); Omer Reingold (Stanford University); Udi Wieder (VMware) </td></tr><tr> <td><strong> HappyMap: A Generalized Multicalibration Method </strong> <a href="https://youtu.be/PBxNZLzrgVk">Video</a> </td></tr> <tr><td>Authors: Zhun Deng, Cynthia Dwork (Harvard University); Linjun Zhang (Rutgers University) </td></tr><tr> <td><strong> Decision Making under Miscalibration </strong> <a href="https://youtu.be/6bkHi6e1TO4">Video</a> </td></tr> <tr><td>Authors: Guy Rothblum (Apple); Gal Yona (Weizmann Institute of Science) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>6:00pm- 8:00pm</strong> </td> <td class="session_info marked"> Graduating Bits and Pizza 馃崟馃崟馃崟 (in 32-G449). </td> <tr> <td class="date" colspan="2"> <h3><strong>Thursday, January 12th</strong></h3> </td> </tr> <tr> <td class="time_info "> <strong> Session 12 <br> 10:00am-11:00am <br> Chair: Avishay Tal </td> <td class = "session_info"><table><tbody> <tr> <td><strong> On Oracles and Algorithmic Methods for Proving Lower Bounds </strong><a href="https://youtu.be/9SUcl2-huOw">Video</a></td></tr> <tr><td>Authors: Nikhil Vyas, Ryan Williams (MIT) </td></tr><tr> <td><strong> Karchmer-Wigderson Games for Hazard-free Computation </strong> <a href="https://youtu.be/d95JKl5m4M4">Video</a> </td></tr> <tr><td>Authors: Christian Ikenmeyer (University of Liverpool, United Kingdom.); Balagopal Komarath (IIT Gandhinagar, Gujarat, India); Nitin Saurabh (IIT Hyderabad, India.) </td></tr><tr> <td><strong> Black-box Constructive Proofs are Unavoidable </strong><a href="https://youtu.be/2rpYqfBQuwA">Video</a></td></tr> <tr><td>Authors: Lijie Chen (UC Berkeley); Ryan Williams (MIT); Tianqi Yang (Tsinghua University) </td></tr><tr> <td><strong> New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method </strong> <a href="https://youtu.be/0d-MMtpFpXw">Video</a> </td></tr> <tr><td>Authors: Lijie Chen (UC Berkeley) </td></tr><tr> <td><strong> A New Conjecture on Hardness of Low-Degree 2-CSP鈥檚 with Implications to Hardness of Densest k-Subgraph and Other Problems </strong> <a href="https://youtu.be/1ONH3PXl5AM">Video</a> </td></tr> <tr><td>Authors: Julia Chuzhoy (Toyota Technological Institute at Chicago); Mina Dalirrooyfard (MIT); Vadim Grinberg (Weizmann Institute of Science); Zihan Tan (Rutgers University) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 13 <br> 11:10am - 12:10pm<br> Chair: Ankur Moitra </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Certification with an NP Oracle </strong> <a href="https://youtu.be/7BFnKbE3Ct4">Video</a> </td></tr> <tr><td>Authors: Guy Blanc, Caleb Koch (Stanford University); Jane Lange (MIT); Carmen Strassle, Li-Yang Tan (Stanford University) </td></tr><tr> <td><strong> On Flipping the Fr茅chet distance </strong></td></tr> <tr><td>Authors: Omrit Filtser (The Open University of Israel); Mayank Goswami (Queens College, City University of New York); Joseph Mitchell (Stony Brook University); Valentin Polishchuk (Linkoping University) </td></tr><tr> <td><strong> Consensus Division in an Arbitrary Ratio </strong> <a href="https://youtu.be/w3weG3xHJHk">Video</a> </td></tr> <tr><td>Authors: Paul W. Goldberg (University of Oxford); Jiawei Li (University of Texas at Austin) </td></tr> <tr> <td><strong> Unsplittable Euclidean Capacitated Vehicle Routing: A 2+\epsilon)(2+系)-Approximation Algorithm </strong> <a href="https://youtu.be/6yPMaoO2sRo">Video</a> </td></tr> <tr><td>Authors: Fabrizio Grandoni (IDSIA, University of Lugano); Claire Mathieu (CNRS); Hang Zhou (脡cole Polytechnique) </td></tr> <tr> <td><strong> Clustering Permutations: New Techniques with Streaming Applications </strong> <a href="https://youtu.be/hQkcFBxWxD0">Video</a> </td></tr> <tr><td>Authors: Diptarka Chakraborty (National University of Singapore); Debarati Das (Pennsylvania State University); Robert Krauthgamer (Weizmann Institute of Science) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>12:10pm- 1:50pm</strong> </td> <td class="session_info marked"> Lunch break (on your own). </td> <tr> <td class="time_info "> <strong> Session 14 <br> 1:50pm-2:50pm <br> Chair: Brendan Lucier </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Learning Reserve Prices in Second-Price Auctions </strong> <a href="https://youtu.be/VPQ_HPSZGjg">Video</a> </td></tr> <tr><td>Authors: Yaonan Jin (Columbia University); Pinyan Lu (Shanghai University of Finance and Economics); Tao Xiao (Huawei TCS Lab) </td></tr><tr> <td><strong> What Can Cryptography Do For Decentralized Mechanism Design? </strong> <a href="https://youtu.be/DERiUkVpWkk">Video</a> </td></tr> <tr><td>Authors: Elaine Shi, Hao Chung, Ke Wu (Carnegie Mellon University) </td></tr><tr> <td><strong> Making Auctions Robust to Aftermarkets </strong> <a href="https://youtu.be/pkzxPoHFZZ8">Video</a> </td></tr> <tr><td>Authors: Moshe Babaioff, Nicole Immorlica (Microsoft Research); Yingkai Li (Yale University); Brendan Lucier (Microsoft Research New England) </td></tr><tr> <td><strong> Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence </strong> <a href="https://youtu.be/TxxWcU1to70">Video</a> </td></tr> <tr><td>Authors: Jason Gaitonde (Cornell University); Yingkai Li (Yale University); Bar Light (Microsoft Research New York City); Brendan Lucier (Microsoft Research New England); Aleksandrs Slivkins (Microsoft Research New York City) </td></tr><tr> <td><strong> Rigidity in Mechanism Design and its Applications </strong></td></tr> <tr><td>Authors: Shahar Dobzinski, Ariel Shaulker (Weizmann Institute) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 15 <br> 3:00pm-4:00pm <br> Chair: Alex Lombardi </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Proofs of Quantumness from Trapdoor Permutations </strong> <a href="https://youtu.be/P5n5wFNqh40">Video</a> </td></tr> <tr><td>Authors: Tomoyuki Morimae (Kyoto University); Takashi Yamakawa (NTT Social Informatics Laboratories) </td></tr> <tr> <td><strong>Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and more</strong></td></tr> <tr><td>Qipeng Liu (Simons Institute) </td></tr> <tr> <td><strong> On the computational hardness needed for quantum cryptography </strong> <a href="https://youtu.be/8KgU-Y_s0Rs">Video</a> </td></tr> <tr><td>Authors: Zvika Brakerski (Weizmann Institute of Science); Ran Canetti, Luowen Qian (Boston University) </td></tr><tr> <td><strong> Asynchronous Multi-Party Quantum Computation </strong> <a href="https://youtu.be/XK-SO55DTaQ">Video</a> </td></tr> <tr><td>Authors: Vipul Goyal (Carnegie Mellon University and NTT Research); Chen-Da Liu-Zhang (NTT Research); Justin Raizes, Joao Ribeiro (Carnegie Mellon University) </td></tr><tr> <td><strong> Quantum Proofs of Deletion for Learning with Errors </strong> <a href="https://youtu.be/vSCdztR-EQ4">Video</a> </td></tr> <tr><td>Authors: Alexander Poremba (California Institute of Technology) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>4:00pm- 4:30pm</strong> </td> <td class="session_info marked"> Break. </td> <tr> <td class="time_info "> <strong> Session 16 <br> 4:30pm-5:30pm <br> Chair: Ankur Moitra </td> <td class = "session_info"><table><tbody> <tr> <td><strong> A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems </strong> <a href="https://youtu.be/BBMS_DlQAhA">Video</a> </td></tr> <tr><td>Authors: Monika Henzinger (University of Vienna); Billy Jin (Cornell University); Richard Peng (Carnegie Mellon University and University of Waterloo); David Williamson (Cornell University) </td></tr><tr> <td><strong> Vertex Sparsification for Edge Connectivity in Polynomial Time </strong> <a href="https://youtu.be/y19mmRPzKfQ">Video</a> </td></tr> <tr><td>Authors: Yang P. Liu (Stanford University) </td></tr><tr> <td><strong> On computing homological hitting sets </strong> <a href="https://youtu.be/6ZVUJ9GCNrY">Video</a> </td></tr> <tr><td>Authors: Ulrich Bauer (Technical University of Munich); Abhishek Rathod (Purdue University); Meirav Zehavi (Ben-Gurion University) </td></tr><tr> <td><strong> Worst-Case to Expander-Case Reductions </strong> <a href="https://youtu.be/BV31ygbFEtg">Video</a> </td></tr> <tr><td>Authors:amir Abboud, Nathan Wallheimer (Weizmann Institute) </td></tr><tr> <td><strong> Counting Subgraphs in Somewhere Dense Graphs </strong> <a href="https://youtu.be/DPX_vGCCLJY">Video</a> </td></tr> <tr><td>Authors: Marco Bressan (University of Milan); Leslie Ann Goldberg (University of Oxford); Kitty Meeks (University of Glasgow); Marc Roth (University of Oxford) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>5:30pm- 7:30pm</strong> </td> <td class="session_info marked"> Posters and Reception (in R&D Commons). </td> <tr> <td class="date" colspan="2"> <h3><strong>Friday, January 13th</strong></h3> </td> </tr> <tr> <td class="time_info "> <strong> Session 17 <br> 10:00am - 10:50am <br> Chair: Adam Kalai </td> <td class = "session_info"><table><tbody> <tr><td>馃弳 <strong><span style="color:DarkRed"> Best Student Paper:</span> Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes </strong> <a href="https://youtu.be/dEb4eYFjkvY">Video</a> </td></tr> <tr><td>Authors: Lunjia Hu, Charlotte Peale (Stanford University) </td></tr> <tr><td><strong> Online Learning and Bandits with Queried Hints </strong> <a href="https://youtu.be/xR1lF0nLizA">Video</a> </td></tr> <tr><td>Authors: Aditya Bhaskara (University of Utah); Sreenivas Gollapudi (Google); Sungjin Im (University of California-Merced); Kostas Kollias (Google); Kamesh Munagala (Duke University) </td></tr> <tr><td><strong> Making Decisions under Outcome Performativity </strong> <a href="https://youtu.be/NsXofrVB6Nc">Video</a> </td></tr> <tr><td>Authors: Michael P. Kim, Juan C. Perdomo (UC Berkeley) </td></tr> <tr><td><strong> Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique </strong> <a href="https://youtu.be/3Bs8VQtajJY">Video</a> </td></tr> <tr><td>Authors: Pasin Manurangsi (Google Research) </td></tr> </tbody></table></tr> <tr> <td class="time_info "> <strong> Session 18 <br> 11:00am-12:20pm <br> Chair: Mohsen Ghaffari </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks </strong> <a href="https://youtu.be/uGNKDnKpst4">Video</a> </td></tr> <tr><td>Authors: Antoine El-Hayek, Monika Henzinger (University of Vienna); Stefan Schmid (University of Vienna & TU Berlin) </td></tr><tr> <td><strong> The Time Complexity of Consensus Under Oblivious Message Adversaries </strong> <a href="https://youtu.be/vZIaYGAIy9Y">Video</a> </td></tr> <tr><td>Authors: Hugo Rincon Galeana (Technische Universit盲t Wien);ami Paz (LISN - CNRS and Paris-Saclay University); Stefan Schmid (TU Berlin & Fraunhofer SIT); Ulrich Schmid (TU Wien); Kyrill Winkler (ITK Engineering, Vienna, Austria) </td></tr><tr> <td><strong> False Consensus, Information Theory, and Prediction Markets </strong> <a href="https://youtu.be/iXDaxZIjY2k">Video</a> </td></tr> <tr><td>Authors: Yuqing Kong (Peking University); Grant Schoenebeck (University of Michigan) </td></tr><tr> <td><strong> Secure Distributed Network Optimization Against Eavesdroppers </strong> <a href="https://youtu.be/ZuN46goMlLA">Video</a> </td></tr> <tr><td>Authors: Yael Hitron, Merav Parter (Weizmann Institute); Eylon Yogev (Bar-Ilan University) </td></tr><tr> <td><strong> Resilience of 3-Majority Dynamics to Non-Uniform Schedulers </strong> <a href="https://youtu.be/aFWDhUSBXqs">Video</a> </td></tr> <tr><td>Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov (Tel Aviv University) </td></tr><tr> <td><strong> Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds </strong> <a href="https://youtu.be/9APaMYyBfzk">Video</a> </td></tr> <tr><td>Authors: Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research) </td></tr><tr> <td><strong> Beeping Shortest Paths via Hypergraph Bipartite Decomposition </strong> <a href="https://youtu.be/bIhsEG90sNs">Video</a> </td></tr> <tr><td>Authors: Fabien Dufoulon (University of Houston); Yuval Emek (Technion); Ran Gelles (Bar-Ilan University) </td></tr></tbody></table></tr> <td class="time_info marked"><strong>12:20pm- 2:00pm</strong> </td> <td class="session_info marked"> Lunch break (on your own). </td> <tr> <td class="time_info "> <strong> Session 19 <br> 2:00pm-2:50pm <br> Chair: Aaron Sidford </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Epic Fail: Emulators can tolerate some edge faults for free </strong> <a href="https://youtu.be/hY7R3oPVnDQ">Video</a> </td></tr> <tr><td>Authors: Greg Bodwin (University of Michigan); Michael Dinitz (Johns Hopkins University); Yasamin Nazari (University of Salzburg) </td></tr><tr> <td><strong> Graph Searching with Predictions </strong> <a href="https://youtu.be/2QTiuA0XRVU">Video</a> </td></tr> <tr><td>Authors: Siddhartha Banerjee (Cornell); Vincent Cohen-Addad (Google); Anupam Gupta (Carnegie Mellon); Zhouzi Li (Tsinghua University) </td></tr><tr> <td><strong> Rounding via Low Dimensional Embeddings </strong> <a href="https://youtu.be/Gpbl_l2pYbs">Video</a> </td></tr> <tr><td>Authors: Mark Braverman (Princeton University); Dor Minzer (MIT) </td></tr><tr> <td><strong> Garland鈥檚 Technique for Posets and High Dimensional Grassmannian Expanders </strong></td></tr> <tr><td>Authors: Tali Kaufman (BIU); Ran J. Tessler (Weizmann Institute of Science) </td></tr></tbody></table></tr> <tr> <td class="time_info "> <strong> Session 20 <br> 3:00pm-3:50pm <br> Chair: Sofya Raskhodnikova </td> <td class = "session_info"><table><tbody> <tr> <td><strong> On Interactive Proofs of Proximity with Proof-Oblivious Queries </strong> <a href="https://youtu.be/AuBxSSbUeGk">Video</a> </td></tr> <tr><td>Authors: Oded Goldreich (Weizmann Institute of Science); Guy N. Rothblum (Apple); Tal Skverer (Weizmann Institute of Science) </td></tr> <tr> <td><strong> Efficiently Testable Circuits </strong> <a href="https://youtu.be/oCeNdEsD7XU">Video</a> </td></tr> <tr><td>Authors: Mirza Ahad Baig (ISTA); Suvradip Chakraborty (ETH Zurich); Stefan Dziembowski (University of Warsaw and IDEAS NCBR); Ma艂gorzata Ga艂膮zka (University of Warsaw); Tomasz Lizurej (University of Warsaw and IDEAS NCBR); Krzysztof Pietrzak (ISTA) </td></tr> <tr> <td><strong> List Agreement Expansion from Coboundary Expansion </strong> <a href="https://youtu.be/9mhtbYRh6eE">Video</a> </td></tr> <tr><td>Authors: Roy Gotlib, Tali Kaufman (Bar-Ilan University) </td></tr> <tr> <td><strong> Improved Monotonicity Testing Over the Hypergrid via Hypercube Embeddings </strong> <a href="https://youtu.be/V9-9oh--hps">Video</a> </td></tr> <tr><td>Authors: Mark Braverman (Princeton University), Subhash Khot (NYU); Guy Kindler (Hebrew University of Jerusalem); Dor Minzer (MIT) </td></tr> </tbody></table></tr> <td class="time_info marked"><strong>3:50pm- 4:20pm</strong> </td> <td class="session_info marked"> Break. </td> <tr> <td class="time_info "> <strong> Session 21 <br> 4:20pm-5:20pm <br> Chair: Aaron Sidford </td> <td class = "session_info"><table><tbody> <tr> <td><strong> Online Pen Testing </strong> <a href="https://youtu.be/RDUJlu_FO5M">Video</a> </td></tr> <tr><td>Authors: Mingda Qiao, Gregory Valiant (Stanford University) </td></tr><tr> <td><strong> Recovery from Non-Decomposable Distance Oracles </strong> <a href="https://youtu.be/3ykcFx1B0v4">Video</a> </td></tr> <tr><td>Authors: Zhuangfei Hu (Unafilliated); Xinda Li (University of Waterloo); David Woodruff (Carnegie Mellon University); Hongyang Zhang, Shufan Zhang (University of Waterloo) </td></tr><tr> <td><strong> An Algorithmic Bridge Between Hamming and Levenshtein Distances </strong> <a href="https://youtu.be/P53-QAUFejc">Video</a> </td></tr> <tr><td>Authors: Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo); Tomasz Kociumaka (Max Planck Institute for Informatics); Robert Krauthgamer (Weizmann Institute of Science); Barna Saha (University of California San Diego) </td></tr><tr> <td><strong> Constant-depth sorting networks </strong><a href="https://youtu.be/X-Qt9IaLScQ">Video</a></td></tr> <tr><td>Authors: Natalia Dobrokhotova-Maikova (Yandex, Moscow, Russia); Alexander Kozachinskiy (Institute for Mathematical and Computational Engineering, Universidad Cat贸lica de Chile \ IMFD & CENIA Chile, Santiago, Chile); Vladimir Podolskii (Courant Institute of Mathematical Sciences, New York University, NY, USA) </td></tr><tr> <td><strong> Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments </strong> <a href="https://youtu.be/LaMe2sY1qZ0">Video</a> </td></tr> <tr><td>Authors: Varun Gupta (University of Chicago); Ravishankar Krishnaswamy (Microsoft Research India); Sai Sandeep (Carnegie Mellon University); Janani Sundaresan (Rutgers University) </td></tr></tbody></table></tr></table> <h1>Finito la comedia!</h1> </p> </div> </div> </div> </div> <div id="footer"></div> </body> </html>