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 |