Milan Theory Workshop

Milan Theory Workshop — June 15-18, 2022 @ Bocconi University

This event is the colocation of a workshop on Spectral and Convex Optimization Techniques in Graph Algorithms and a workshop on Recent Advances in Cryptography.

Location: Bocconi University, Roentgen Building, Room AS01

This event is open to the public, but (free) registration is required to participate.

Registration site

Organizers: Alon Rosen and Luca Trevisan
Local arrangments: Diana Righi

Draft program (subject to change):

June 15

[Zoom Link]

9:00-9:30. Welcoming reception
9:30-11:10. Cryptography session
- Stefan Dziembowski (U. of Warsaw): Lower Bounds for Off-Chain Protocols: Exploring the Limists of Plasma
- Amos Beimel (Ben Gurion U.): Recent advances in secret sharing
11:10-11:40. Coffee break
11:40-12:40. Plenary session
- Moni Naor (Weizmann): Cryptography and Communication Complexity Meet (Again)
12:40-14:10. Lunch
14:10-15:50. Graph algorithms session
- Rasmus Kyng (ETH Zurich): Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
- Yang Liu (Stanford): Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
15:50-16:20. Coffee break
16:20-18:50. Cryptography session

Omer Paneth (MIT): Incrementally Verifiable Computation and Rate-1 Batch Arguments
Tal Malkin (Columbia): Unclonable Polymers and Their Cryptographic Applications
Ran Canetti (Boston U.): COA-Secure Obfuscation and Applications

June 16

[Zoom Link]

9:30-11:00. Graph algorithms session
- Ola Svensson (EPFL): Finding Unsplittable Flows and Schedules via Discrepancy Theory
- James Lee (U. of Washington): Entropic regularization for general metric spaces
11:00-11:30. Coffee break
11:30-12:25. Plenary session
- Sam Hopkins (MIT): Hypothesis testing, low-degree polynomials, and SoS lower bounds
12:25-14:20. Lunch
14:20-15:50. Cryptography session
- Giulio Malavolta (MPI-SP): Can we obfuscate quantum circuits?
- Maciej Obremsky (National University of Singapore): Non-malleability and Randomness
15:50-16:20. Coffee break
16:20-17:50. Graph Algorithms session

Pravesh Kothari (CMU): Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture
Chris Jones (U. of Chicago): Sum-of-Squares Lower Bounds for Sparse Independent Set

June 17

[Zoom Link]

9:30-11:00. Cryptography session
- Jad Siblak (Tel Aviv): Explicit uniquely decodable codes for space bounded channels that achieve BSC capacity
- Noam Mazor (Tel Aviv): On the complexity of Two-Party Differential Privacy
11:00-11:30. Coffee break
11:30-12:25. Plenary session
- Yael Tauman-Kalai MIT): Delegating Computation: Simple at Last
12:25-14:20. Lunch
14:20-15:50. Graph algorithms session
- Thatchaphol Saranurak (U. of Michigan): Using expanders for dynamic graph algorithms: a survey
- Gramoz Goranci (U. of Glasgow): Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
15:50-16:20. Coffee break
16:20-17:50. Cryptography session

Chethan Kamath (Tel Aviv): On Treewidth, Separators and Yao's Garbling
Chris Brzuska (Aalto U): TBA

20:00. Banquet at Cantine della Vetra

June 18

[Zoom Link]

9:30-11:00. Cryptography session
- Vlad Kolesnikov (GeorgiaTech): New directions in garbled circuits
- Lisa Kohl (CWI): Correlated Pseudorandom Functions
11:00-11:30. Coffee break
11:30-13:00. Graph algorithms session
- Goran Zuric (ETH Zurich): Approximation Boosting: a Pervasive and Underexplored Feature of Modern Graph Algorithms
- Michael Kapralov (EPFL): Spectral hypergraph sparsifiers of nearly linear size

This workshop is supported by the Bocconi CS department and is part of projects funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreements N. 834861 and N. 101019547)