UCSD Theory Group
UCSD CS Theory Lunch
The theory lunch is a weekly meeting for theory students and
faculty to hang out, eat food, and talk about CS theory.
Each week, someone will give a short, informal talk about
a problem or an idea that's been on their mind. Food will be
provided.
Organizers: Anthony Ostuni, Adam Suhl (email if you want to present something)
Fall 2022:
-
09/23/22:
Anthony Ostuni
The Log-Rank Conjecture and Lifting Theorems
-
09/30/22:
Chris Ye,
Sub-cubic Algorithms for Special Cases of APSP
-
10/07/22:
Dustin Lin,
Randomness: Beating the Hybrid Argument
-
10/14/22:
Mark Schultz,
A Coding Theoretic Perspective on Lattice-Based Cryptography
Spring 2022:
-
04/01/22:
Sam Spiro
Theory Lunch: April Fool's Edition
-
04/08/22:
Noah Fleming,
TNFP (and how it's proof complexity)
-
04/15/22:
Gil Kur,
The Geometric Balls into Bins Problem
-
04/22/22:
Daniel Beaglehole,
Computation and the Brain
-
05/06/22:
Jess Sorrell,
The Continuum Hypothesis vs Uniform Convergence (Part 1)
-
05/13/22:
Jess Sorrell,
The Continuum Hypothesis vs Uniform Convergence (Part 2)
-
05/20/22:
Anthony Ostuni,
Communication Complexity and Hales-Jewett
-
05/27/22:
Jason O'Neill,
Theorems on Traces
Winter 2022:
-
01/14/22:
Anthony Ostuni,
Applications of Sunflowers to TCS
-
01/21/22:
Sam Spiro,
Recent Advances on the Sunflower Lemma
-
01/28/22:
Daniel Beaglehole,
An Efficient Approximation Algorithm for the Colonel Blotto Game
-
02/04/22:
Max Hopkins,
Realizable Learning is All You Need
-
02/11/22:
Noah Fleming,
Testing (Real) Linear Functions
-
02/18/22:
Jess Sorrell,
Outcome Indistinguishability
-
02/25/22:
Sihan Liu,
Statistical-Computational Gaps in Reinforcement Learning
-
03/09/22:
Amy Kanne,
Intro to Quantum Error-Correcting Codes
Fall 2021:
-
10/08/21:
Jessica Sorrell,
Reproducibility in ML
-
10/15/21:
Hantao Yu,
Discrete Fourier Transforms ove Schurian Schemes
-
10/22/21:
Preetum Nakkiran,
Theory without Theorems (Tales from Deep Learning)
-
10/29/21:
Sam Spiro,
Supuer (Saiyan) Permutations
-
11/05/21:
Adam Suhl,
Quantum Algorithms
-
11/12/21:
Amy Kanne,
Local Error Correcting Codes and the t-Disjoint Repair Property
-
11/19/21:
Jason Oneill,
Extremal Combinatorics on the Hypercube
-
12/03/21:
Daniel Beaglehole,
Linear Programming, Zero-Sum Games, and Online Learning
-
12/10/21:
Jiapeng Zhang
Constructions of Cryptographic Hash Functions
Spring 2021:
-
04/02/21:
Cyrus Rashtchian,
Covering Codes
-
04/09/21:
Sam McGuire,
Cliques in Random Graphs
-
04/16/21:
Gaurav Mahajan,
A Structural Framework for Provable Generalization in RL
-
04/23/21:
Mark Schultz,
Covering Codes 2
-
04/30/21:
Max Hopkins,
On the Equivalence of Realizable and Agnostic Learning
-
05/07/21:
Sam Spiro,
An Introduction to Hypergraph Containers
-
05/14/21:
Jess Sorrell,
Private median estimation
-
05/28/21:
Anthony Ostuni,
Graph Toughness
Winter 2021:
-
02/05/21:
Jess Sorrell,
Boosting for Fairness
-
02/12/21:
Max Hopkins,
Active Learning in Bounded Memory
-
02/19/21:
Michal Moshkovitz,
Explainable k-means and k-median clustering
-
02/26/21:
Gaurav Mahajan,
Sample Complexity of Reinforcement Learning
Fall 2020:
-
11/13/20:
Sam Spiro,
Playing Cards with Partial Feedback
-
11/20/20:
Sam McGuire,
Log-Rank and Lifting for AND-functions
-
12/4/20:
Mark Schultz,
Flipping Triangles Upside-down in Differential Privacy
-
12/11/20:
Max Hopkins,
Point Location and Active Learning Halfspaces
Spring/Summer 2020 (Covid: No Theory Lunch)
Winter 2020:
-
1/15/20:
Ragesh Jaiswal,
Low-rank Approximation with Length-squared Sampling
-
1/22/20:
Gaurav Mahajan,
Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
-
1/29/20:
Sam McGuire,
Intersecting Set Systems and Stability
-
2/5/20:
Sam McGuire,
More on Intersecting Set Systems
-
2/12/20:
Anant Dhayal,
(NP\cap CoNP)/poly Easy-witness Lemma
-
2/19/20:
Shachar Lovett,
Decision List Compression
-
2/26/20:
Dudi Mass,
Ramanujan Complexes are Agreement Expanders
-
3/04/20:
Jason O'Neill,
Graham-Pollak, Hypergraph analogs, and Open Problems
-
3/11/20:
Sasank Mouli,
Hilbert function and VC dimension
Fall 2019:
-
10/03/19:
Jess Sorrell,
The Projection Games Conjecture and the Closest Vector Problem
-
10/10/19:
Sankeerth Rao,
Recent Progress on the Collatz Conjecture
-
10/17/19:
Max Hopkins,
Tight Bounds for Small-set Expansion in the Johnson Graph
-
10/31/19:
Sam McGuire,
Switching Lemmas
-
11/07/19:
Rex Lei,
Deterministic Trace Reconstruction from k-decks
-
11/14/19:
Mark Schultz,
Galois Connections and the Moser-Lambek Theorem
-
11/21/19:
Michal Moshkovitz,
The Fundamental Theorem of Statistical Learning
-
12/05/19:
Sasank Mouli,
The Razborov Rank Method
-
12/12/19:
Anant Dhayal, Max Hopkins, Sam McGuire, Michal Moshkovitz,
Open Problem Session
Summer 2019:
-
6/27/19:
Sam McGuire,
Time Versus Space Trade-offs
-
7/11/19:
Jiapeng Zhang,
Constructing PRGs from OWPs and the Goldreich-Levin Theorem
-
7/18/19:
Joe Jaeger,
Space-time Trade-offs in Cryptography
-
7/25/19:
Marco Carmosino,
The Minimum Circuit Size Problem
-
8/1/19:
Jiapeng Zhang,
Improved Bounds on the Sunlower Lemma
-
8/8/19:
Jiawei Gao,
Fine-grained Complexity of Least-weight Subsequence
-
8/15/19:
Max Hopkins,
High-dimensional Expanders
-
9/5/19:
Jess Sorrell,
Lattice Problems and Subclasses of TFNP
-
9/12/19:
Sam McGuire,
Complexity Lower Bounds on Dense Model Theorems
-
9/19/19:
Ken Hoover,
(RP versus BPP) Versus (Promise-RP versus Promise-BPP)
Spring 2019:
-
4/18/19:
Sam McGuire,
Dense Model Theorems
-
4/25/19:
Max Hopkins,
Reasoning in the Presence of Noise
-
5/2/19:
Jiapeng Zhang,
DNF Sparsification and Sunflowers
-
5/9/19:
Gaurav Mahajan,
Convergence of Gradient-based Methods
-
5/16/19:
Anant Dhayal,
Role of Unambiguity in Time/Space-bounded non-Deterministic Computation
-
5/23/19:
Sasank Mouli,
PIT for Depth-3 Circuits
-
5/30/19:
Mark Schultz,
Entropy-efficient Constant-time Sampling
-
6/6/19:
Nick Genise,
Inference Dimension and the Closest Vector Problem
-
6/13/19:
Jess Sorrell,
Simpler Lattice-based Oblivious Transfer from Ideal Lattices