List of past theory student seminars

2022 - 2023

**Organizer: Lawrence Li**

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] | 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 |

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 |

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 |

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 |

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 |

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 |

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 |

2015 - 2016

2014 - 2015

2013 - 2014

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 |

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 |

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 |

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 |

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 |

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 |

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 |

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 |

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 |

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 |

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 |