Speaker info

Title: TBD

Website: https://www.csail.mit.edu/person/shafi-goldwasser 

Title: Semi-Algebraic Proof Systems for QBF

Abstract: In this talk, I will describe new semi-algebraic proof systems for Quantified Boolean Formulas (QBF), analogous to the propositional proof systems Nullstellensatz, Sherali-Adams and Sum-of-Squares.  I will describe how we transfer to this settin techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation), obtaining a number of strong QBF lower bounds and separations between the QBF systems.

Bio: Meena Mahajan is a professor at The Institute of Mathematical Sciences, HBNI, Chennai, India. Her interests span most of theoretical computer science. Her research focusses primarily on understanding the limits of efficient computation, and encompasses many aspects of complexity theory, including Boolean function complexity, algebraic circuits, and proof complexity.

Website: https://www.imsc.res.in/~meena 

Title: Extendable dictionaries et al.

Abstract: The talk is about recent advancements in the design of dictionaries and other related data structures, focusing on the challenge of extendability: designing optimal data structures when the input set size is unknown and can vary over time. A dynamic dictionary (hash table) is a data structure that maintains sets under insertions, deletions, and membership queries. A related problem is that of designing filters, which are approximate dictionaries that permit false positives. Classically, extendability is addressed using the doubling/halving technique, where a fixed-capacity structure is swapped for a larger/smaller one as the set size changes. While this technique is effective for dictionaries, it poses significant new technical challenges for filters and other data structures that do not explicitly store the input set. In this talk, we review novel techniques for extendability and discuss their practical implications for designing efficient, space-efficient data structures.

Bio: Ioana Bercea is an Assistant Professor in Computer Science at the KTH Royal Institute of Technology in Stockholm. She specializes in developing efficient data structures, spanning both theoretical foundations and practical implementations. She holds a Ph.D. from the University of Maryland and completed postdocs at Tel Aviv University and most recently with the Basic Algorithms Research Group in Copenhagen.

Website: https://ioanabercea.github.io/webpage/ 

Title: Quantum Graph Colouring

Bio: Lorenzo Ciardo is an Assistant Professor at TU Graz, which he joined in 2025. Previously, he spent 4.5 years at the University of Oxford working as a Senior Research Associate, and he  obtained a Ph.D. in mathematics at the University of Oslo in 2020. His research activity lies at the intersection of computational complexity, quantum information, and discrete mathematics. Two long-term goals of his work are to understand the common algebraic structure underlying the power of convex relaxations for computational problems involving satisfaction of local constraints, and to explore the connections between the algebraic approach to constraint satisfaction and quantum information.

Website: https://sites.google.com/view/lorenzociardo/home-page 

Title: Learning interpretable and reliable classifiers using local algorithms

Bio: I'm a sixth-year Ph.D. student at MIT CSAIL, where I'm fortunate to study theoretical computer science under Ronitt Rubinfeld. Broadly, I am interested in algorithms related to machine learning and property testing. More specifically, I am interested in the application of techniques from the fields of sublinear algorithms and analysis of Boolean functions for the purpose of designing efficient algorithms for learning, property testing, and other similar problems.

Website: https://people.csail.mit.edu/jlange/ 

Title: The Computation of Nature: algorithms, cryptography and complexity of physical systems

Bio: You may have heard of the book "The Nature of Computation" by Moore and Martens, which beautifully articulated to generations of natural scientists why computational complexity is relevant to their lives. My research goes in the opposite direction: what is the complexity of learning about physical systems, and what cryptographic primitives and algorithms can arise from many-body physical systems? While physics abounds with intuitions about what phenomena are hard (or not) for classical computers to simulate or probe, my goal is to formalize these rigorously as assumptions and either use quantum computers to simulate or learn them, or when that proves impossible, to build cryptography out of them. 

I am currently an Assistant Professor in CS and Physics at EPFL, having completed a triumvirate of postdocs at MIT, Harvard and the Dahlem Center for Complex Quantum Systems in Berlin. Prior to that I obtained my PhD and BS from Stanford University and MIT respectively. My research has been recognized by a Research Excellence award from IBM, a Quantum Creators' Prize from the University of Chicago and the Quantum Innovator accolade from the University of Waterloo.

Website: https://sites.google.com/view/yihui-quek/ 

Title: Optimization in modern computational settings: algorithms and impossibility results

Bio: Santhoshini Velusamy is currently a Research Assistant Professor at Toyota Technological Institute at Chicago. She completed her PhD in 2023 from Harvard University, where she was supervised by Prof. Madhu Sudan. She is the recipient of a Google PhD fellowship and an NSF CRII award. Santhoshini does research in theoretical computer science, and is specifically interested in the design and analysis of algorithms in modern computational settings like streaming. She is also interested in problems in algorithmic game theory. Santhoshini is joining the University of Waterloo as an assistant professor in December 2025.

Website: https://sites.google.com/view/santhoshinivelusamy 

Title: Sublinear-Time Algorithms for Random-Walk Probability Estimation

Bio: Hanzhi Wang is a Lecturer at the School of Computing and Information Systems, University of Melbourne. From November 2024 to October 2025, she was a Postdoc at BARC (Basic Algorithms Research Copenhagen), University of Copenhagen. She received her PhD in July 2024 from Renmin University of China. Hanzhi’s research focuses on the design of scalable graph algorithms, with previous work centered on efficient estimation of random-walk probabilities on large graphs, such as fast PageRank estimation. 

Website: https://wanghzccls.github.io/