List of past theory student seminars
2023 - 2024
Organizer: Ziyang Jin & Harry Sha
Date Title Speaker
2023 / 09 / 13 Multiplicative Auction Algorithms for Approximate Maximum Weight Bipartite Matching [show abstract] Da Wei (David) Zheng
2023 / 09 / 20 Near Neighbour Search and Locality-Sensitive Hashing [show abstract][slides] Deepanshu Kush
2023 / 09 / 27 Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking [show abstract] Victor Sanches Portella
2023 / 10 / 04 Influence and the KKL Theorem [show abstract][slides] Harry Sha
2023 / 10 / 11 Graph Colouring and the Rödl Nibble [show abstract][slides] Ziyang Jin
2023 / 10 / 18 Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds [show abstract][slides] Devansh Shringi
2023 / 10 / 25 Construction of t-independent hash functions [show abstract] Arvin Sahami
2023 / 11 / 01 Word Circuits [show abstract] Morgan Shirley
2023 / 11 / 08 Spectral digraph sparsification via matrix discrepancy theory [show abstract] Yibin Zhao
2023 / 11 / 15 Divide and Conquer Grover search and its consequences [show abstract] Noah Brustle
2023 / 11 / 22 Communication Complexity and The Pattern Matrix Method [show abstract] Adrian She
2023 / 11 / 29 Couplings, Privacy, and Programs as Regular Languages [show abstract] Sky Li
2023 / 12 / 06 General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [show abstract] Haohua Tang
2023 / 12 / 13 Wait-free bounded min registers [show abstract] Jordan Malek
2023 / 12 / 20 The Impossibility of Approximate Agreement on a Larger Class of Graphs [show abstract] Jason Liu
2024 / 01 / 17 Extension-based proofs and the impossibility of approximate agreement on graphs [show abstract] Jason Liu
2024 / 01 / 24 Frugal Colouring of Graphs with Girth At Least Five [show abstract][slides] Ziyang Jin
Back to top
2022 - 2023
Organizer: Lawrence Li & Morgan Shirley
Date Title Speaker
2022 / 09 / 28 Query Complexity: Simple, Structured and Significant [show abstract][slides] Suhail Sherif
2022 / 10 / 05 Exactly N With More Than 3 Players [show abstract][slides] Morgan Shirley
2022 / 10 / 12 Lower Bounds on the Error of Unbiased Differentially Private Mechanisms [show abstract][slides] Haohua Tang
2022 / 10 / 19 A Simple and Efficient Parallel Laplacian Solver [show abstract][slides] Yibin Zhao
2022 / 10 / 26 How to allocate goods or chores fairly and efficiently [show abstract][slides] Soroush Ebadian
2022 / 11 / 02 Determinant Bound for Discrepancy I [show abstract][slides] Lily Li
2022 / 11 / 09 Determinant Bound for Discrepancy II [show abstract][slides] Lily Li
2022 / 11 / 16 The Dark Side of SAT [show abstract] Suhail Sherif
2022 / 11 / 23 Basic Combinatorial Designs and Applications [show abstract][slides] Harry Sha
2022 / 11 / 30 Trivia Night![notes][slides] Lawrence Li
2022 / 12 / 07 A Faster Algorithm for 0-1 Integer Programming via Communication Complexity [show abstract][slides] Deepanshu Kush
2023 / 01 / 25 Degree vs Approximate Degree for Boolean Functions [show abstract][slides] Suhail Sherif
2023 / 02 / 01 Random Graphs, Giant Components, and Fixed Degree Sequences [show abstract][slides] Harry Sha
2023 / 02 / 08 Voting with Preference Intensities [show abstract][slides] Mohamad Latifian
2023 / 02 / 15 Sublinear Edge Sampling and Bernoulli Factories [show abstract][slides] Morgan Shirley
2023 / 02 / 22 Is Sortition Both Representative and Fair? [show abstract][slides] Soroush Ebadian
2023 / 03 / 01 Lower Bound on Error for Unbiased Differentially Private Mechanisms - The Gamma-p Function and Approximate DP [show abstract] Haohua Tang
2023 / 03 / 15 Reconstruction Algorithm for Depth-3 Arithmetic Circuit with Top Fan-in 2 [show abstract][slides] Devansh Shringi
2023 / 03 / 22 Online Decision-Making in Adaptive Random Graph Processes [show abstract] Calum MacRury
2023 / 03 / 29 Random Spanning Trees, Random Walks and Determinantal​ Point Processes [show abstract] Yibin Zhao
2023 / 04 / 05 Probabilistic Couplings and Approximate Liftings [show abstract] Sky Li
2023 / 04 / 12 Discrepancy Minimization via a Self Balancing Walk [show abstract] Lily Li
2023 / 04 / 19 PRGs for Two-Party Communication Protocols [show abstract][slides] Deepanshu Kush
2023 / 04 / 26 The Probablistic Method and Entropy Compression [show abstract][slides] Ziyang Jin
2023 / 05 / 03 How to Cut Cake: An Overview of Fair Online Resource Allocation Problems [show abstract] Arkaprava Choudhury
2023 / 05 / 10 The Space Complexity of Signal Detection [show abstract] Sean Ovens
2023 / 05 / 17 Dynamic MST in the Massively Parallel Computational model [show abstract] Lawrence Li
Back to top
2021 - 2022
Organizer: Ian Mertz & Adrian She
Date Title Speaker
2022 / 04 / 27 Envy-Free Partitions [show abstract] Lily Li and Evi Micha
2022 / 04 / 20 Proof of the Kahn-Kalai Conjecture [show abstract] Greg Rosenthal
2022 / 04 / 13 A Lower Bound in Geometric Disrepancy Theory [show abstract][slides] Deepanshu Kush
2022 / 04 / 06 Algorithms and Lower Bounds for Local Differential Privacy [show abstract] Alex Edmonds
2022 / 03 / 30 On Range Searching in the Group Model and Combinatorial Discrepancy [show abstract] Morgan Shirley
2022 / 03 / 23 Effective Resistances and Max Flow [show abstract][slides] Lawrence Li
2022 / 03 / 02 The Satisfiability Coding Lemma [show abstract][slides] Harry Sha
2022 / 02 / 23 Property Testing and Boolean Function Analysis [show abstract][notes] Adrian She
2022 / 02 / 16 Trading Time and Space in Catalytic Branching Programs [show abstract] Ian Mertz
2021 / 12 / 15 TCS Trivia Night Lawrence Li
2021 / 12 / 08 Basics of Boolean Function Analysis, with Applications [show abstract] Adrian She
2021 / 12 / 01 Simple Random Walks [show abstract][notes] Lily Li
2021 / 11 / 24 The Isolation Lemma [show abstract][slides] Deepanshu Kush
2021 / 11 / 17 Nisan's Pseudorandom Generator for Space-Bounded Computation [show abstract][slides] Ian Mertz
2021 / 11 / 10 Matrix Norms and Communication Complexity [show abstract] Morgan Shirley
2021 / 11 / 03 Smaller ACC0 Circuits for Symmetric Functions [show abstract] Gregory Rosenthal
2021 / 10 / 20 Lifting with Sunflowers [show abstract][slides] Ian Mertz
2021 / 10 / 13 Width-Reduced Methods for Quasi-Self-Concordant Optimization [show abstract] Deeksha Adil
Back to top
2020 - 2021
Organizer: Ian Mertz
Date Title Speaker
2021 / 05 / 26 Toda's Theorem [show abstract][notes] Adrian She
2021 / 05 / 11 The Differential Equation Method [show abstract] Calum MacRury
2021 / 04 / 29 Depth reduction and depth compression using arithmetic [show abstract] Ian Mertz
2021 / 04 / 15 A Brief Introduction to the Exactly-N Problem in Number-on-Forehead Communication [show abstract] Morgan Shirley
2021 / 03 / 18 Stein's Method: a brief overview [show abstract][notes] Lily Li
2021 / 03 / 04 LogCFL is closed under complementation [show abstract][slides] Deepanshu Kush
2021 / 02 / 04 Overview of Acceleration Algorithms for Convex Functions [show abstract][slides] Deeksha Adil
2021 / 01 / 21 Cell Probe Lower Bounds for Prefix Sum [show abstract][slides] Ian Mertz
2020 / 12 / 15 Worst-Case Analysis for Randomly Collected Data [show abstract] Morgan Shirley
2020 / 12 / 08 Natural Proofs [show abstract] Noah Fleming
2020 / 12 / 01 Bounds on the \(QAC^0\) Complexity of Approximating Parity [show abstract] Gregory Rosenthal
2020 / 11 / 18 Introduction to Proof Complexity [show abstract][notes] Adrian She
Back to top
2019 - 2020
Organizer: Ian Mertz, Alex Edmonds
Date Title Speaker
2020 / 07 / 07 Three Ways to Get Your Way: Strategize, Gerrymander, Party [show abstract] Tyrone Strangway
2020 / 06 / 09 Orthogonal Vectors and the Subquadratic World [show abstract][slides] Deepanshu Kush
2020 / 05 / 26 Automating Cutting Planes is NP-Hard [show abstract] Ian Mertz
2020 / 05 / 12 Topological Impossibility Proofs in Distributed Computing [show abstract] Kayman Brusse
2020 / 04 / 28 Catalytic Approaches to the Tree Evaluation Problem [show abstract] Ian Mertz
2020 / 04 / 14 List Coloring and Bipartite Graphs [show abstract][notes] Lily Li
2020 / 03 / 05 Complexity-Theoretic Backing for Quantum Advantage Experiments [show abstract] Adrian She
2020 / 02 / 27 Stochastic Probing [show abstract] Calum MacRury
2020 / 02 / 13 A geometric alternative to Nesterov's accelerated gradient descent [show abstract] Deeksha Adil
2020 / 02 / 06 Voting Systems in a Distributional Setting [show abstract] Evi Micha
2020 / 01 / 30 A Tail Bound for Read-k Families of Functions [show abstract] Gregory Rosenthal
2020 / 01 / 23 Local Differential Privacy [show abstract] Alex Edmonds
2019 / 12 / 12 Maximal cliques and colourings via SAT, temporal cliques, and applications [show abstract] Coby Viner
2019 / 12 / 05 Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings [show abstract] Rafael Oliveira
2019 / 11 / 28 Dynamic Graph Algorithms [show abstract] Gregory Rosenthal
2019 / 11 / 14 Coding for Sunflowers [show abstract] Morgan Shirley
2019 / 11 / 07 A generalization of CHSH and the algebraic structure of optimal solutions [show abstract] Hamoon Mousavi
2019 / 10 / 17 Quantum Random Walks [show abstract] Adrian She
2019 / 10 / 10 Constructive Proof of the General Lovasz Local Lemma (LLL) II Lily Li
2019 / 10 / 03 Constructive Proof of the General Lovasz Local Lemma (LLL) [show abstract] Lily Li
2019 / 09 / 26 The distortion of distributed voting [show abstract] Evi Micha
2019 / 09 / 19 Normalized Matching Property in Random & Pseudorandom Graphs [show abstract][slides] Deepanshu Kush
2019 / 09 / 12 Issues in Fair Prediction for Recidivism [show abstract] Ian Mertz
2019 / 09 / 03 Beating Treewidth for Average-Case Subgraph Isomorphism [show abstract][slides] Gregory Rosenthal
Back to top
2018 - 2019
Organizer: Ian Mertz
Date Title Speaker
2019 / 07 / 02 Short Proofs Are Hard To Find [show abstract] Ian Mertz
2019 / 06 / 25 Karchmer-Wigderson Games [show abstract] Morgan Shirley
2019 / 06 / 18 Quantum Graphs and all the Colours of the Rainbow [show abstract] Arthur Mehta
2019 / 06 / 11 Discrepancy in Random Set Systems [show abstract] Calum MacRury
2019 / 06 / 04 The Container Method in Extremal Combinatorics [show abstract] Bruno Cavalar
2019 / 05 / 28 A contribution to the critique of liquid democracy [show abstract] Evi Micha
2019 / 05 / 21 Catalytic computing [show abstract] Ian Mertz
2019 / 04 / 23 Survey of algebraic proof complexity [show abstract] Noah Fleming
2019 / 04 / 02 NEXP is not in ACC [show abstract] Gregory Rosenthal
2019 / 03 / 26 A Tour of Symmetric Function Theory [show abstract] Adrian She
2019 / 03 / 19 Games Variant of Quantum PCP Conjecture [show abstract] Hamoon Mousavi
2019 / 03 / 12 \(\ell_p\) norm minimization - a brief overview of methods [show abstract] Deeksha Adil
2019 / 02 / 26 Equality Alone Does Not Simulate Randomness [show abstract] Morgan Shirley
2019 / 02 / 19 PAC learning and VC dimension II Alex Edmonds
2019 / 02 / 05 PAC learning and VC dimension [show abstract] Alex Edmonds
2019 / 01 / 29 Efficient maximal clique elucidation and its applications [show abstract] Coby Viner
2019 / 01 / 22 DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals [show abstract] Chris Karavasilis
2018 / 12 / 06 Property Testing and Communication [show abstract] Noah Fleming
2018 / 11 / 29 The Amortized Analysis of a Non-blocking Chromatic Tree [show abstract] Jeremy Ko
2018 / 11 / 22 Spectral Algorithm for the Planted Bisection Problem [show abstract] Deeksha Adil
2018 / 11 / 08 Complexity of Games with Hidden Information [show abstract] Noah MacAulay
2018 / 11 / 01 On the Structure of Unconditional UC Hybrid Protocols [show abstract] Morgan Shirley
2018 / 10 / 18 The Linear Algebra Method in Extremal Combinatorics [show abstract] Gregory Rosenthal
2018 / 10 / 11 Discrepancy of Set-systems and Matrices [show abstract] Lily Li
2018 / 09 / 27 The Minimum Circuit Size Problem [show abstract] Ian Mertz
Back to top
2017 - 2018
Organizer: Robert Robere
Date Title Speaker
2018 / 04 / 19 Parameterized Complexity [show abstract] Coby Viner
2018 / 04 / 12 The Fastest and Shortest Algorithm for All Well-Defined Problems [show abstract] Noah MacAulay
2018 / 03 / 15 Subgraph Isomorphism [show abstract] Gregory Rosenthal
2018 / 03 / 08 Matching [show abstract] Deeksha Adil
2018 / 03 / 01 Cheeger's Inequality [show abstract] Lily Li
2018 / 02 / 08 Monotone circuits for Majority [show abstract] Morgan Shirley
2018 / 02 / 01 Barrington's Theorem [show abstract] Ian Mertz
2018 / 01 / 25 MIP vs \(\mathsf{NEXP}\) [show abstract] Robert Robere
2017 / 12 / 12 The Haplotype Inference by Pure Parsimony problem [show abstract] Coby Viner
2017 / 12 / 06 Algorithmic Stability for Adaptive Data Analysis [show abstract] Alex Edmonds
2017 / 11 / 27 Non-blocking binary trees [show abstract] Jeremy Ko
2017 / 11 / 14 Lalla Mouatadid
2017 / 11 / 07 Synchronization problems in distributed computing [show abstract] Eric DiTomasso
2017 / 10 / 31 Differential privacy in machine learning [show abstract] Yuxing Zhang
2017 / 10 / 24 A De Bruijn-Erdos Theorem for Chordal Graphs [show abstract] Lalla Mouatadid
2017 / 10 / 17 Non-concurrent union-find data structures [show abstract] Gregory Rosenthal
2017 / 10 / 10 Secure multiparty computation [show abstract] Morgan Shirley
2017 / 10 / 03 The Minimum Enclosing Circle Problem [show abstract] Lily Li
2017 / 09 / 25 Constructive Proof of the Lovasz Local Lemma [show abstract] Noah Fleming
2017 / 09 / 19 The Satisfiability Coding Lemma [show abstract] Robert Robere
Back to top
2016 - 2017
Organizer: Robert Robere
Date Title Speaker
2017 / 05 / 15 Logic and program semantics [show abstract] Chris Karavasilis
2017 / 05 / 08 Sublinear time and local algorithms [show abstract] Ryan Murray
2017 / 05 / 01 Constructive Proof of the Lovasz Local Lemma [show abstract] Noah Fleming
2017 / 04 / 24 Limitations of Sub-Modular Complexity measures [show abstract] Venkatesh Medabalimi
2017 / 04 / 10 Hard-core predicates and Goldreich-Levin [show abstract] Jaiganesh Balasundaram
2017 / 04 / 02 Introduction to Point-Set Topology [show abstract] Felipe de Azevedo Piovezan
2017 / 03 / 27 Relaxed memory consistency models [show abstract] Eric DiTomasso
2017 / 03 / 20 Amortized Analysis of Concurrent Data Structures [show abstract] Jeremy Ko
2017 / 03 / 13 Submodular Function Maximization [show abstract] Sepehr Abbasi Zadeh
2017 / 02 / 27 Planar Graph, Square Root Phenomena, and \(\mathsf{ETH}\) [show abstract] Lalla Mouatadid
2017 / 02 / 13 Quantum computation: a primer [show abstract] Ian Mertz
2017 / 01 / 30 Pseudorandomness [show abstract] Nicholas Spooner
2017 / 01 / 23 Strongly Exponential Lower Bounds for Monotone Computation [show abstract] Robert Robere
2016 / 12 / 05 A positive result regarding obfuscating point circuits [show abstract] Jaiganesh Balasundaram
2016 / 11 / 28 Cutting planes [show abstract] Noah Fleming
2016 / 11 / 20 Log-depth circuits II Ian Mertz
2016 / 11 / 13 Log-depth circuits [show abstract] Ian Mertz
2016 / 10 / 31 Minors and Well Quasi Orderings [show abstract] Lalla Mouatadid
2016 / 10 / 24 Secret sharing schemes [show abstract] Robert Robere
2016 / 10 / 17 Interactive oracle proofs and perfect zero knowledge [show abstract] Nicholas Spooner
Back to top
2015 - 2016
Organizer: Robert Robere
Date Title Speaker
Back to top
2014 - 2015
Organizer: Robert Robere
Date Title Speaker
Back to top
2013 - 2014
Organizer: Robert Robere
Date Title Speaker
Back to top
2012 - 2013
Organizer: Wesley George
Date Title Speaker
2012 / 09 / 17 The Permanent is hard to compute even on a good day[notes] Yuval Filmus
2012 / 09 / 10 Concerning Randomness Extraction Wesley George
Back to top
2011 - 2012
Organizer: Wesley George
Date Title Speaker
2012 / 04 / 12 Iterative Methods for Combinatorial Optimization Justin Ward
2012 / 04 / 05 Approximation algorithms for Max-Bisection Siavosh Benabbas
2012 / 03 / 29 Privacy and Communication Complexity: part II Lila Fontes
2012 / 03 / 22 Functional Encryption with Bounded Collusions via Multi-Party Computation Serge Gorbunov
2012 / 03 / 15 The experts selection problem and multiplicative updates method Joel Oren
2012 / 03 / 08 Clock Synchronization over Wireless Networks Anastasios Zouzias
2012 / 03 / 01 SAT algorithms and proof complexity Kaveh Ghasemloo
2012 / 02 / 23 Time-Space Tradeoffs through Communication Complexity Robert Robere
2012 / 02 / 16 Counting perfect matchings in planar graphs [Kasteleyn], [Fisher-Temperley] Dai Le
2012 / 02 / 02 Matrix Multiplication II[notes] Yuval Filmus
2012 / 02 / 09 Matrix Multiplication I[notes] Yuval Filmus
2012 / 01 / 26 Pseudorandom generators for space bounded computation Anastasios Zouzias
2012 / 01 / 19 Cheeger's Inequality and its higher order extension II Yu Wu
2011 / 12 / 05 Cheeger's Inequality and its higher order extension Yu Wu
2011 / 11 / 28 Lower Bounds for Bounded Timestamping Marek Janicki
2011 / 11 / 21 The search for local one-way functions Wesley George
2011 / 11 / 16 Von Neumann's minimax theorem and some applications Lila Fontes
2011 / 11 / 07 Pipage Rounding Justin Ward
2011 / 10 / 24 A Threshold For Clusters in Real-World Random Graphs Arron Norwell
2011 / 10 / 17 Some recent results on The Steiner Tree Problem II Siavosh Benabbas
2011 / 10 / 03 Some recent results on The Steiner Tree Problem Siavosh Benabbas
2011 / 09 / 26 Approximate mechanism design without money Joel Oren
Back to top
2010 - 2011
Organizer: Wesley George
Date Title Speaker
2011 / 04 / 19 A matrix hyperbolic cosine algorithm and applications Anastasios Zouzias
2011 / 04 / 12 Algebraic Topology and Distributed Computing: A Primer Marek Janicki
2011 / 04 / 05 Kolmogorov complexity and games Lei Huang
2011 / 03 / 22 Quantum Proofs of Classic Results Per Austrin
2011 / 03 / 15 Current Barriers in Boolean Circuit Complexity Anil Ada
2011 / 03 / 08 Online Stochastic Matching Joel Oren
2011 / 02 / 22 Generalizations of Matroids for Approximation Algorithms Justin Ward
2011 / 02 / 15 Balanced graph partition problems Arron Norwell
2011 / 02 / 08 Secure physical computation in person Wesley George
2011 / 02 / 01 Probabilistic Automata (Group Exercise) Lila Fontes
2011 / 01 / 25 Introduction to Proof Complexity, Uniform and Nonuniform Kaveh Ghasemloo
2011 / 01 / 18 Approximation Algorithm for Balanced Separator Eden Chlamtáč
2011 / 01 / 11 Exponential lower bounds for constant-depth proofs of the pigeonhole principle Yuval Filmus
2010 / 12 / 16 Probabilistic Reasoning in Bounded Arithmetic: A Pigeon's Perspective Dai Le
2010 / 12 / 09 Szemerédi's Theorem for length 3 progressions (Roth's Theorem) Anil Ada
2010 / 12 / 02 Dueling Algorithms Brendan Lucier
2010 / 11 / 25 Approximation Algorithm for Balanced Separator and Its Applications Yu Wu
2010 / 11 / 18 The PCP Theorem Anastasios Zouzias
2010 / 11 / 11 Strategy Iteration is strongly polynomial for two player games with constant discount Lei Huang
2010 / 11 / 04 Maximizing non-monotone submodular functions Justin Ward
2010 / 10 / 28 Constructing pseudorandom generators from one-way functions Wesley George
2010 / 10 / 21 Faster Hamiltonicity Testing Per Austrin
2010 / 10 / 14 Unprovability of Lower Bounds on the Circuit Size for SAT in \(S_2^2(\alpha)\) Kaveh Ghasemloo
2010 / 10 / 07 The Power of Graph Searching Steve Chaplick
2010 / 09 / 30 Privacy and Communication Complexity Lila Fontes
2010 / 09 / 23 A "simple" proof of Alon-Roichman's Theorem Anastasios Zouzias
2010 / 09 / 16 Using Polynomials to Prove PARITY not in \(\mathsf{AC}^0\)[notes] Yuval Filmus
Back to top
2009 - 2010
Organizer: unknown
Date Title Speaker
2010 / 04 / 14 Maximizing The Spread of Influence Through a Social Network Joel Oren
2010 / 04 / 07 Local Search Heuristics for k-Median and Facility Location Problems Justin Ward
2010 / 03 / 31 On basing one-way functions on \(\mathsf{NP}\)-Hardness Wesley George
2010 / 03 / 24 Bayesian Algorithmic Mechanism Design Brenden Lucier
2010 / 03 / 17 Computational Game Theory Lila Fontes
2010 / 03 / 10 Matrix-Valued Chernoff bounds and applications Anastasios Zouzias
2010 / 03 / 03 Complexity Theory for Operators in Analysis Akitoshi Kawamura
2010 / 02 / 24 An asymptotically tight bound on the adaptable chromatic number Giovanna Thron
2010 / 02 / 10 Computability and Complexity over Real Numbers and Uncountable Structures Kaveh Ghasemloo
2010 / 02 / 03 Connections between Complexity, SAT-solvers and Cryptography Periklis Papakonstantinou
2010 / 01 / 27 Depth and rank considerations in the Polynomial Identity Testing problem Bruno Grenet
2010 / 01 / 20 Two proofs of the Central Limit Theorem[notes] Yuval Filmus
2010 / 01 / 13 The Isolation Lemma Dai Le
2009 / 12 / 09 The Myth of the Folk Theorem Brendan Lucier
2009 / 12 / 02 Lipschitz ODEs are \(\mathsf{PSPACE}\)-complete Akitoshi Kawamura
2009 / 11 / 25 Modern Factorization Methods[notes] Yuval Filmus
2009 / 11 / 18 Clique Trees and Chordal Families of Graphs Steve Chaplick
2009 / 11 / 11 An Introduction to Kolmogorov Complexity Lila Fontes
2009 / 11 / 04 A Constructive Proof of the Lovasz Local Lemma Justin Ward
2009 / 10 / 28 \(\mathsf{AM}[k]\) is in \(\mathsf{AM}[2]\) Marek Janicki
2009 / 10 / 21 Recent efforts in cryptography to model and deal with physical side-channel attacks Yevgeniy Vahlis
2009 / 10 / 14 Ultraproducts and approximation of circuit bounds Kaveh Ghasemloo
2009 / 10 / 07 Private Coins versus Public Coins in Interactive Proof Systems Wesley George
2009 / 09 / 30 The Goldreich-Levin Theorem Periklis Papakonstantinou
2009 / 09 / 23 Introduction to game theory and how to play large games using simple strategies Anastasios Zouzias
2009 / 09 / 16 Seven trees in one[notes] Yuval Filmus
Back to top
2008 - 2009
Organizer: unknown
Date Title Speaker
2009 / 08 / 17 On the Structure of the Optimal Greedy Computation Periklis Papakonstantinou
2009 / 05 / 21 Disproving Borsuk's Conjecture Siavosh Benabbas
2009 / 04 / 23 Formal Theories for Logspace Counting Lila Fontes
2009 / 04 / 16 Cryptography in \(\mathsf{NC}^0\) Periklis Papakonstantinou
2009 / 04 / 09 Time-Space Lower Bounds and Diagonalization Kaveh Ghasemloo
2009 / 04 / 02 Uncertainty Principles, Extractors and Explicit embeddings of \(\ell_2\) into \(\ell_1\) Anastasios Zouzias
2009 / 03 / 26 Distance Trisectors and Zone Diagrams Akitoshi Kawamura
2009 / 03 / 19 Tango trees and the dynamic optimality problem Brendan Lucier
2009 / 03 / 12 How NOT to solve Vertex Cover using Semidefinite Programming Costis Georgiou
2009 / 03 / 05 Collaborative Filtering Marek Janicki
2009 / 02 / 26 Levels of detail in terrains Giovanna Thron
2009 / 02 / 19 A Black Box Separation of One-Wayness From Correlated One-Wayness in Trapdoor Permutations Yevgeniy Vahlis
2009 / 02 / 12 A little bit of Coding Theory (LP bounds on the size of Codes) II Siavosh Benabbas
2009 / 02 / 05 A little bit of Coding Theory (LP bounds on the size of Codes) Siavosh Benabbas
2009 / 01 / 22 Determinism versus non-determinism and related problems Wesley George
2009 / 01 / 15 Price of Anarchy for Combinatorial Auction Mechanisms Brendan Lucier
2008 / 12 / 18 New directions in derandomization II Periklis Papakonstantinou
2008 / 12 / 10 New directions in derandomization Periklis Papakonstantinou
2008 / 12 / 03 Lift and Project systems as potential algorithms and their limitations II Costis Georgiou
2008 / 11 / 26 Lift and Project systems as potential algorithms and their limitations Costis Georgiou
2008 / 11 / 19 Parity not in \(\mathsf{AC}^0\) Lila Fontes
2008 / 11 / 12 Introduction to compressed sensing (Basis Pursuit) Anastasios Zouzias
2008 / 11 / 05 On Distributing Symmetric Streaming Computations Anastasios Sidiropoulos
2008 / 10 / 29 Open Problems Session Paul Medvedev
2008 / 10 / 17 A Survey of Gower's Norm Shachar Lovett
2008 / 10 / 15 Intersection Graphs of Paths in a Tree Steve Chaplick
2008 / 10 / 01 Regret bounds for online convex programming Ilya Sutskever
2008 / 09 / 24 Provable total functions of \(I_{\exists}^+\) Kaveh Ghasemloo
2008 / 09 / 17 The Ogiwara-Watanabe Theorem Akitoshi Kawamura
2008 / 09 / 10 On The Impossibility of Basing Identity Based Encryption on Trapdoor Permutations Yevgeniy Vahlis
Back to top
2007 - 2008
Organizer: unknown
Date Title Speaker
2008 / 06 / 19 Near Optimal Dimensionality Reductions that Preserve Volumes Anastasios Zouzias
2008 / 05 / 01 Bounded Timestamping Systems Marek Janicki
2008 / 04 / 24 The complexity of simulating Brownian Motion Mark Braverman
2008 / 04 / 10 PQ-trees and applications Steve Chaplick
2008 / 04 / 03 Superpolynomial monotone circuits lower bounds for CLIQUE Periklis Papakonstantinou
2008 / 03 / 27 Randomized Matrix Computations Anastasios Zouzias
2008 / 03 / 20 Computability and Complexity of Real Functions Akitoshi Kawamura
2008 / 03 / 13 Discovering Community in Social Networks Alvin Chin
2008 / 03 / 06 Sparse graphs: metrics and random models Hamed Hatami
2008 / 02 / 28 Selected Results in Additive Combinatorics Siu Man Chan
2008 / 02 / 14 Lower Bounds for Selection in Randomly Ordered Streams Matei David
2008 / 02 / 07 Derandomizing shallow circuits Siavosh Benabbas
2007 / 11 / 29 Survey Propagation Eric Hsu
2007 / 11 / 22 On the non-existence of dimension reduction in \(\ell_2^2\) Mohammad Moharrami
2007 / 11 / 15 Brower fixed point and Borsuk-Ulam theorem: combinatorial proofs Massimo Lauria
2007 / 11 / 08 Graph norms and Sidorenko's conjecture Hamed Hatami
2007 / 11 / 01 Edmonds' bipartite matching algorithm James Kwon
2007 / 10 / 25 On non-deterministic auxiliary pushdown automata Periklis Papakonstantinou
2007 / 10 / 18 Black box separation of public key encryption from one way functions Yevgeniy Vahlis
2007 / 10 / 11 Introduction to expanders Mark Braverman
2007 / 10 / 04 Noisy Sorting Mark Braverman
Back to top
2006 - 2007
Organizer: unknown
Date Title Speaker
2007 / 04 / 12 Affinity Propagation Delbert Dueck
2007 / 03 / 29 "Dinur's Combinatorial Proof of the PCP Theorem" II Siavosh Benabbas
2007 / 03 / 22 "Dinur's Combinatorial Proof of the PCP Theorem" Siavosh Benabbas
2007 / 03 / 01 A new lower bound for the Lovasz-Schrijver SDP matrix-cut operator Costis Georgiou
2007 / 02 / 15 The small world phenomen: An algorithm perspective Marek Janicki
2007 / 02 / 08 Kazhdan property and expanders Hamed Hatami
2007 / 02 / 01 Cut-free tree-like and dag-like proof systems Phuong Nguyen
2007 / 01 / 25 KKL Theorem and the Discrete Fourier transform Ilya Sutskever
2006 / 12 / 07 Applications of limits of graph sequences II Siu Man Chan and Siu On Chan
2006 / 11 / 30 Applications of limits of graph sequences Siu Man Chan and Siu On Chan
2006 / 11 / 09 Asymptotic behaviour of the Mafia game Mark Braverman
2006 / 10 / 26 Lower bounds on bounded timestamps Marek Janicki
2006 / 10 / 19 Sorting Signed Permutations Paul Medvedev
2006 / 10 / 12 Computing the number of spanning trees mod p Mark Braverman
2006 / 10 / 05 Lower bounds for the Lovasz-Schrijver hierachy II Costis Georgiou
2006 / 09 / 28 Lower bounds for the Lovasz-Schrijver hierachy Costis Georgiou
2006 / 09 / 21 Pebbling Game is PSPACE complete Philipp Hertel
Back to top
2005 - 2006
Organizer: unknown
Date Title Speaker
2006 / 04 / 03 Spectra of Graphs Periklis Papakonstantinou
2006 / 03 / 28 PSPACE-completeness Philipp Hertel
2006 / 03 / 20 Monadic Second-order Logic captures regular languages (over strings) Anthony Widjaja To
2006 / 03 / 13 Counting accepting paths in \(\mathsf{NL}\) machines, and the Determinant problem Mark Braverman
2006 / 03 / 07 Introduction to Bounded Arithmetic Phuong Nguyen
2006 / 02 / 20 Comparing Encrypted Numbers Vladimir Kolesnikov
2006 / 02 / 13 Key Exchange Using Passwords and Long Keys Vladimir Kolesnikov
2006 / 02 / 06 Hard-Core Distributions for Somewhat Hard Problems by Russell Impagliazzo Mark Braverman
2006 / 01 / 30 Introduction to proof of Toda's Theorem II Philipp Hertel
2006 / 01 / 23 Introduction to proof of Toda's Theorem Philipp Hertel
2006 / 01 / 16 Proving integrality gaps without knowing the linear program Periklis Papakonstantinou
2005 / 11 / 28 Introduction to discharging Marc Tedder
2005 / 11 / 21 Secure Function Evaluation Vladimir Kolesnikov
2005 / 11 / 14 Approximation results for the Minimum Vertex Cover problem Costis Georgiou
2005 / 11 / 07 Lower bounds for resolution proof system Philipp Hertel
2005 / 10 / 31 Prover/Delayer games for tree resolution Alex Hertel
2005 / 10 / 17 Introduction to VC theory Ilya Sutskever
2005 / 10 / 03 A tutorial on Fourier transforms and applications Periklis Papakonstantinou
2005 / 09 / 26 Introduction to probabilistic computation Mark Braverman
Back to top
2004 - 2005
Organizer: unknown
Date Title Speaker
2005 / 05 / 19 A proof system for logical contingencies Alex Hertel, Philipp Hertel
2005 / 05 / 03 Pebble games Phuong Nguyen
2005 / 04 / 19 Pseudorandom generators for space bounded computation Mark Braverman
2005 / 04 / 12 Expander graphs Paul McCabe
2005 / 04 / 05 Nonautomatizability of resolution I
2005 / 03 / 22 Finite Metric Embeddings and Applications II Periklis Papakonstantinou
2005 / 03 / 29 Finite Metric Embeddings and Applications Periklis Papakonstantinou
2005 / 03 / 08 Program Checkability Paul McCabe
2005 / 03 / 01 \(\mathsf{IP} = \mathsf{PSPACE}\) Mark Braverman
2005 / 02 / 22 Switching lemma II: applications to lower bounds on AC0 Philipp Hertel
2005 / 02 / 08 Switching lemma Philipp Hertel
2005 / 02 / 01 A generalization of the infinite Ramsey theorem Nazanin Mirmohammadi
2004 / 12 / 09 Razborov-Smolensky's lower bounds for \(\mathsf{AC}^0[2]\) Mark Braverman
2004 / 12 / 02 Product-Free Lambek Calculus Periklis Papakonstantinou
2004 / 11 / 25 Intro to Game Theory Periklis Papakonstantinou
2004 / 11 / 18 Strong Conditional Oblivious Transfer and Computing on Intervals. Vladimir Kolesnikov
2004 / 11 / 11 Graph Ramsey Theory and the Polynomial Hierarchy Phuong The Nguyen
2004 / 10 / 28 Communication Complexity II Mark Braverman
2004 / 11 / 04 Communication Complexity Mark Braverman
2004 / 10 / 21 The Static Optimality Theorem Travis Gagie
2004 / 10 / 14 Kolmogorov Complexity Nazanin Mirmohammadi
2004 / 10 / 07 Size-Depth Trade-offs for Boolean Formulae, by Bonet and Buss Alan Skelley
2004 / 09 / 30 A factor 2 approximation algorithm for the generalized Steiner network problem Lap Chi Lau
2004 / 09 / 23 Complete characterizations and complexity results for greedy algorithms admitting optimal inputs Periklis Papakonstantinou
2004 / 09 / 09 Game Based Notions of Locality over Finite Models Pablo Barcelo
Back to top
2003 - 2004
Organizer: unknown
Date Title Speaker
2004 / 06 / 24 Pseudorandom generators for space-bounded computation Paul McCabe
2004 / 06 / 17 AKS sorting networks Shlomo Hoory
2004 / 06 / 10 Approximate range searching in higher dimensions Avner Magen
2004 / 06 / 03 Monotone Circuits without the Monotony. Josh Buresh-Oppenheim
2004 / 05 / 11 Sorting Low-Entropy Sequences. Travis Gagie
2004 / 05 / 04 On The Computability of Julia Sets Mark Braverman
2004 / 04 / 27 \(\mathsf{NP}\) is as easy as detecting unique solutions Josh Buresh-Oppenheim
2004 / 04 / 20 On truth-table reducibility to \(\mathsf{SAT}\) Tsuyoshi Morioka
2004 / 03 / 29 DNFs are not Properly PAC learnable Mark Braverman
2004 / 03 / 23 Fixed-point logics. Antonina Kolokolova
2004 / 03 / 16 Parameterized Complexity Phuong The Nguyen
2004 / 03 / 09 Two millionaires problem. Vladimir Kolesnikov
2004 / 03 / 01 Implicit proofs. Tsuyoshi Morioka
2004 / 02 / 24 Fun with Lempel-Ziv. Travis Gagie
2004 / 02 / 10 \(\mathsf{SAT}(2)\) is \(\mathsf{L}\)-complete. Mark Braverman
2004 / 01 / 27 Golomb Rulers Periklis Papakonstantinou
2003 / 12 / 15 Priority algorithms Periklis Papakonstantinou
2003 / 12 / 08 A brief history of permutation branching programs II Alex Brodsky
2003 / 12 / 01 A brief history of permutation branching programs Alex Brodsky
2003 / 11 / 17 The Hypergraph Transversal Problem Philipp Hertel
2003 / 11 / 10 Real sets computability and complexity Mark Braverman
2003 / 11 / 03 Recognizing GHorn formulas is NL complete. Phuong The Nguyen
2003 / 10 / 27 More on Barnette's Conjecture and Computability and complexity of real numbers Mark Braverman
2003 / 10 / 20 Strengthening Barnette's Conjecture Alex Hertel
2003 / 10 / 06 Relative to a Random Oracle A, \(\mathsf{P}^A \neq \mathsf{NP}^A \neq \mathsf{coNP}^A\) with probability 1 Alan Skelley
2003 / 09 / 29 Complexity of deciding equivalence of regular expressions. Tsuyoshi Morioka
2003 / 09 / 22 Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size Josh Buresh-Oppenheim
2003 / 09 / 15 Segerlind, Buss and Impagliazzo's switching lemma for k-DNF resolution
2003 / 08 / 07 Schaefer's dichotomy theorem Antonina Kolokolova
Back to top
2002 - 2003
Organizer: unknown
Date Title Speaker
2003 / 07 / 31 Introduction to Posets Richard Krueger
2003 / 07 / 24 Lower Bounds on Nullstellensatz Proofs via Designs Tsuyoshi Morioka
2003 / 07 / 17 "Communication Complexity: A new Approach to Circuit Depth", from Karchmer's PhD Periklis Papakonstantinou
2003 / 07 / 10 Sequence Maxima Trees Travis Gagie
2003 / 06 / 26 Real-time interval scheduling Travis Gagie
2003 / 06 / 19 Introduction to model theory III Neil Thapen
2003 / 06 / 12 Introduction to model theory II Neil Thapen
2003 / 06 / 05 Introduction to model theory Neil Thapen
2003 / 05 / 29 Interval selection: Applications, algorithms, and lower bounds Stephanie Horn
2003 / 05 / 15 Primes is in \(\mathsf{P}\) Periklis Papakonstantinou
2003 / 05 / 08 Mutual exclusion for message passing models. Kleoni Ioannidou
2003 / 05 / 01 Formula isomorphism problem. Tsuyoshi Morioka
2003 / 04 / 24 Data compression: Burrows-Wheeler Transform Travis Gagie
2003 / 04 / 10 Intro to bounded arithmetic and RSUV isomorphism Alan Skelley
2003 / 03 / 27 Symmetric Logspace is closed under complement Antonina Kolokolova
2003 / 03 / 20 Hard-core distributions for somewhat hard problems Mark Braverman
2003 / 03 / 13 Fussy closeness Vladimir Kolesnikov
2003 / 03 / 06 Chernoff bounds Mark Braverman
2003 / 02 / 27 Two-tape simulation of multitape Turing machines Phuong The Nguyen
2003 / 02 / 12 Searching constant width mazes captures the AC0 hierarchy Tsuyoshi Morioka
2003 / 02 / 05 Natural proofs Josh Buresh-Oppenheim
2003 / 01 / 28 Profit Cover and parameterized complexity Philipp Hertel
2003 / 01 / 12 "The Berman-Hartmanis conjecture" from Schoning's book Antonina Kolokolova
2003 / 01 / 14 Pursuit and evasion: Modeling a changing problem Kevin Brewer
2002 / 12 / 10 Secure Multiparty Computation II Vladimir Kolesnikov
2002 / 12 / 03 Secure Multiparty Computation Vladimir Kolesnikov
2002 / 11 / 19 A direct connection between PLS and \(G_1\) Alan Skelley
2002 / 11 / 12 Bounded-depth Frege lower bounds for weaker pigeonhole principles Josh Buresh-Oppenheim
2002 / 10 / 29 Restructuring trees Travis Gagie
2002 / 10 / 29 The complexity of acyclic conjunctive queries Antonina Kolokolova
2002 / 10 / 17 Approximability of local search Pixing Zhang
2002 / 10 / 10 \(\mathsf{P}^{\#\mathsf{P}} \subseteq \mathsf{IP}\) Steve Myers
2002 / 10 / 03 Different (and yet equivalent) ways to ask NP queries Tsuyoshi Morioka
2002 / 09 / 24 Transformations of Self-Stabilizing Algorithms Kleoni Ioannidou
2002 / 09 / 10 Randomness and Computation Valentine Kabanets
Back to top