Organisers: Group effort between Tim van Bremen, Themis Gouleakis, Gunjan Kumar, and Dimitrios Myrisiotis
Meeting Time: Usually Mondays, 12-1pm
Location: Check the table below
The AlgoTheory Seminar is a venue for invited speakers, as well as researchers within NUS, to present research related to topics in algorithms and theoretical computer science (broadly construed). Pizza is provided before each talk!
Date and Time | Location | Speaker | Title |
October 3, 12-1pm | Seminar Room 8 (COM1 02-08) | Maciej Obremski (NUS) | Mother of All Leakages |
October 17, 12-1pm | Seminar Room 8 (COM1 02-08) | Themis Gouleakis (NUS) | Sample efficient distribution testing using centralized or distributed computation |
October 31, 12-1pm | Seminar Room 8 (COM1 02-08) | Dimitrios Myrisiotis (NUS) | One-way Functions and a Conditional Variant of MKTP |
November 7, 12-1pm | Seminar Room 8 (COM1 02-08) | Eldon Chung (NUS) | Stronger 3SUM-Indexing Lower Bounds |
November 21, 12-1pm | Seminar Room @ LT19 (BIZ 2) | Vipul Arora (NUS) | Low Degree Testing over the Reals |
November 28, 12-1pm | Meeting Room 1 (COM1 03-19) | Antonios Varvitsiotis (SUTD) | Multiplicative updates for first-order bilinear optimization over density matrices |
December 6, 11am-12pm | Executive Classroom @ COM 2 (COM2 04-02) | Vijay V. Vazirani (University of California, Irvine) | LP-Duality Theory and the Cores of Games |
December 12, 10-11am | Seminar Room @ LT19 (BIZ 2) | Xueyan Tang (NTU) | Dynamic Bin Packing for Busy Time Scheduling |
December 19, 12-1pm | Seminar Room @ LT19 (BIZ 2) | Yi Li (NTU) | The ℓₚ-Subspace Sketch Problem |
Date and Time | Location | Speaker | Title |
January 3, 12-1pm | Seminar Room @ LT19 (BIZ 2) | Shubhangi Saraf (University of Toronto) | Factors of sparse polynomials: structural results and some algorithms |
January 16, 12-1pm | Seminar Room 7 (COM1 02-07) | Anish Mukherjee (University of Warwick) | Recent Progress in Dynamic Complexity Theory |
January 31, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Rahul Jain (NUS) | A direct product theorem for quantum communication complexity with applications to device-independent QKD |
February 6, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Yash Pote (NUS) | Testing of Samplers |
February 13, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Jonathan Scarlett (NUS) | How to Propagate a Bit of Information |
February 20, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Sanjana Dey (NUS) | Complexity and Approximation for Discriminating Code Problems in Geometric Setups |
February 24, 12-1pm | Seminar Room @ LT19 (BIZ 2) | David Steurer (ETH Zurich) | Algorithms approaching the threshold for semi-random planted clique |
February 27, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Pranjal Dutta (NUS) | On the border complexity of binomials (& more) |
March 6, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Kuldeep S. Meel (NUS) | Distribution Testing: From Theory to Practice and Back |
March 13, 12-1pm | Meeting Room 1 (COM1 03-19) | Dean Leitersdorf (NUS) | Extremely Efficient Distance Computations using Distributed Sparsity-Aware Algorithms |
March 20, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Naganand Yadati (NUS) | Deep Learning over Hypergraphs |
April 10, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Timothy van Bremen (NUS) | Probabilistic Query Evaluation: the Combined FPRAS Landscape |
April 17, 12-1pm | Seminar Room @ LT19 (BIZ 2) | Davin Choo (NUS) | Learning causal DAGs using adaptive interventions |
April 24, 4-5pm | Online (via Zoom) | Bishwamittra Ghosh (NUS) | Fairness and Interpretability in Machine Learning: A Formal Methods Approach |
May 15, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Diptarka Chakraborty (NUS) | Matrix Completion: Approximating the Minimum Diameter |
May 22, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Alon Rosen (Bocconi University) | Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method |
May 26, 12-1pm | Meeting Room 1 (COM1 03-19) | Rishav Chourasia (NUS) | Unlearning Personal Information from Machine Learning Models: Trustworthy Certifications and Differential Privacy |
May 29, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | Alexandra Veliche (University of Michigan) | Mean-Based Trace Reconstruction over Oblivious Synchronisation Channels |
June 5, 12-1pm | Meeting Room 20 @ COM3 (COM3 02-59) | L. Sunil Chandran (Indian Institute of Science, Bangalore) | Graph Theory in Quantum Physics |