Seminars Sorted by Series
Computer Science/Discrete Mathematics Seminar I
Apr
04
2016
Computer Science/Discrete Mathematics Seminar I
An average-case depth hierarchy theorem for Boolean circuits I
Li-Yang Tan
11:15am|S-101
Sep
26
2016
Computer Science/Discrete Mathematics Seminar I
Counting solutions to random constraint satisfaction problems
Allan Sly
11:15am|S-101
Oct
17
2016
Computer Science/Discrete Mathematics Seminar I
Matrix invariants and algebraic complexity theory
Harm Derksen
11:15am|S-101
Oct
24
2016
Computer Science/Discrete Mathematics Seminar I
On the query complexity of Boolean monotonicity testing
11:15am|S-101
Oct
31
2016
Computer Science/Discrete Mathematics Seminar I
Communication complexity of approximate Nash equilibria
Aviad Rubinstein
11:15am|West Building Lecture Hall
Nov
07
2016
Computer Science/Discrete Mathematics Seminar I
Non-unique games over compact groups and orientation estimation in cryo-EM
Amit Singer
11:15am|S-101
Nov
14
2016
Nov
21
2016
Computer Science/Discrete Mathematics Seminar I
On the effect of randomness on planted 3-coloring models
Uri Feige
11:15am|S-101
Nov
28
2016
Computer Science/Discrete Mathematics Seminar I
Stochastic block models and probabilistic reductions
11:15am|S-101
Dec
05
2016
Computer Science/Discrete Mathematics Seminar I
On the number of ordinary lines determined by sets in complex space
11:15am|S-101
Dec
12
2016
Computer Science/Discrete Mathematics Seminar I
On gradient complexity of measures on the discrete cube
Ronen Eldan
11:15am|S-101
Jan
17
2017
Computer Science/Discrete Mathematics Seminar I
The polynomial method and the cap set problem
Jordan Ellenberg
10:30am|S-101
Jan
23
2017
Computer Science/Discrete Mathematics Seminar I
Active learning with \"simple\" membership queries
11:15am
Jan
30
2017
Computer Science/Discrete Mathematics Seminar I
Quantifying tradeoffs between fairness and accuracy in online learning
Aaron Roth
11:15am
Feb
06
2017
Computer Science/Discrete Mathematics Seminar I
Strongly Refuting Random CSPs below the spectral threshold
Prasad Raghavendra
11:15am
Feb
13
2017
Computer Science/Discrete Mathematics Seminar I
Nearest neighbor search for general symmetric norms via embeddings into product spaces
Ilya Razenshteyn
11:30am
Feb
27
2017
Computer Science/Discrete Mathematics Seminar I
New insights on the (non)-hardness of circuit minimization and related problems
Eric Allender
11:15am
Mar
06
2017
Computer Science/Discrete Mathematics Seminar I
Interactive coding with nearly optimal round and communication blowup
Yael Kalai
11:15am
Mar
13
2017
Computer Science/Discrete Mathematics Seminar I
On the cryptographic hardness of finding a Nash equilibrium
Nir Bitansky
11:15am
Mar
20
2017
Computer Science/Discrete Mathematics Seminar I
Approximate counting and the Lovasz local lemma
11:15am
Mar
27
2017
Computer Science/Discrete Mathematics Seminar I
Applications of monotone constraint satisfaction
11:15am
Apr
03
2017
Computer Science/Discrete Mathematics Seminar I
A time-space lower bound for a large class of learning problems
11:15am
Apr
10
2017
Apr
17
2017
Computer Science/Discrete Mathematics Seminar I
Efficient empirical revenue maximization in single-parameter auction environments
Yannai Gonczarowski
11:15am
Sep
18
2017
Computer Science/Discrete Mathematics Seminar I
Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems
Umesh Vazirani
11:00am
Sep
18
2017
Computer Science/Discrete Mathematics Seminar I
Rigorous RG: A Provably Efficient and Possibly Practical Algorithm for Simulating 1D Quantum Systems
Umesh Vazirani
11:00am
Oct
02
2017
Computer Science/Discrete Mathematics Seminar I
Crossing the logarithmic barrier for dynamic boolean data structure lower bounds
Omri Weinstein
11:00am
Oct
09
2017
Computer Science/Discrete Mathematics Seminar I
Barriers for rank methods in arithmetic complexity
Rafael Oliveira
11:00am
Oct
16
2017
Oct
23
2017
Computer Science/Discrete Mathematics Seminar I
A nearly optimal lower bound on the approximate degree of AC$^0$
Mark Bun
11:00am
Oct
30
2017
Computer Science/Discrete Mathematics Seminar I
Fooling intersections of low-weight halfspaces
Rocco Servedio
11:00am
Nov
06
2017
Computer Science/Discrete Mathematics Seminar I
Language edit distance, $(min,+)$-matrix multiplication & beyond
Barna Saha
11:00am
Nov
13
2017
Computer Science/Discrete Mathematics Seminar I
Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity I
11:00am|S-101
Nov
20
2017
Nov
27
2017
Computer Science/Discrete Mathematics Seminar I
Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
11:00am|S-101
Dec
04
2017
Computer Science/Discrete Mathematics Seminar I
General strong polarization
Madhu Sudan
11:00am|S-101
Dec
11
2017
Computer Science/Discrete Mathematics Seminar I
Recent advances in high dimensional robust statistics
Daniel Kane
11:00am|S-101
Jan
22
2018
Computer Science/Discrete Mathematics Seminar I
The Matching Problem in General Graphs is in Quasi-NC
Ola Svensson
11:00am|S-101
Jan
29
2018
Computer Science/Discrete Mathematics Seminar I
Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound
Amnon Ta-Shma
11:00am|S-101
Feb
05
2018
Computer Science/Discrete Mathematics Seminar I
Locally Repairable Codes, Storage Capacity and Index Coding
Arya Mazumdar
11:00am|Simonyi Hall 101
Feb
12
2018
Computer Science/Discrete Mathematics Seminar I
Nonlinear dimensionality reduction for faster kernel methods in machine learning.
Christopher Musco
11:00am|Simonyi Hall 101
Feb
26
2018
Computer Science/Discrete Mathematics Seminar I
A Tight Bound for Hypergraph Regularity
11:00am|Simonyi Hall 101
Mar
05
2018
Computer Science/Discrete Mathematics Seminar I
Boolean function analysis: beyond the Boolean cube
11:00am|West Building Lecture Hall
Mar
19
2018
Computer Science/Discrete Mathematics Seminar I
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Yuanzhi Li
11:00am|Simonyi Hall 101
Mar
26
2018
Computer Science/Discrete Mathematics Seminar I
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray
11:00am|Simonyi Hall 101
Apr
09
2018
Computer Science/Discrete Mathematics Seminar I
Large deviations in random graphs
Eyal Lubetzky
11:00am|West Building Lecture Hall
Apr
16
2018
Computer Science/Discrete Mathematics Seminar I
Sums of Squares Over k-Subset Hypercubes
Annie Raymond
11:00am|Simonyi Hall 101
Sep
24
2018
Computer Science/Discrete Mathematics Seminar I
Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem.
2:00pm|Simonyi Hall 101
Oct
01
2018
Computer Science/Discrete Mathematics Seminar I
Oracle Separation of Quantum Polynomial time and the Polynomial Hierarchy
11:15am|Simonyi Hall 101