Events and Activities

Explore current and upcoming events and activities happening at the Institute for Advanced Study.

Jan 21

Computer Science/Discrete Mathematics Seminar II

Approximating CSPs on expanding structures, and applications to codes
Madhur Tulsiani
10:30am | Simonyi Hall 101
I will discuss some recent results showing that the sum-of-squares SDP hierarchy can be used to find approximately optimal solutions to k-CSPs, provided that the instance...
Jan 27

Computer Science/Discrete Mathematics Seminar I

Equality Alone Does not Simulate Randomness
Marc Vinyals
11:00am | Simonyi Hall 101
Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is the equality function....
Jan 28

Computer Science/Discrete Mathematics Seminar II

Pseudo-deterministic algorithms
Toniann Pitassi
10:30am | Simonyi Hall 101
A pseudodeterministic algorithm for a search problem (introduced by Goldwasser and Gat) is a randomized algorithm that must output the *same* correct answer with high...
Feb 03

Computer Science/Discrete Mathematics Seminar I

MIP* = RE
Henry Yuen
11:00am | Simonyi Hall 101
MIP* (pronounced “M-I-P star”) denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize...
Feb 04

Computer Science/Discrete Mathematics Seminar II

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory
Robert Robere
10:30am | Simonyi Hall 101
Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this series of...
Feb 06

Computer Science/Discrete Mathematics - Special Seminar

Explicit rigid matrices in P^NP via rectangular PCPs
Prahladh Harsha
2:00pm | Simonyi 101
A nxn matrix M over GF(2) is said to be (r,\delta)-rigid if  every matrix M' within \delta n^2 Hamming distance from M has rank at least r. A long standing open problem is to construct...
Feb 10

Computer Science/Discrete Mathematics Seminar I

Paths and cycles in expanders
Michael Krivelevich
11:00am | Simonyi Hall 101
Expanders have grown to be one of the most central and studied notions in modern graph theory. It is thus only natural to research extremal properties of expanding graphs. In...
Feb 11

Computer Science/Discrete Mathematics Seminar II

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory
Robert Robere
10:30am | Simonyi Hall 101
Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this talk we will continue our...
Feb 18

Computer Science/Discrete Mathematics Seminar II

An invitation to invariant theory
Viswambhara Makam
10:30am | Simonyi Hall 101
This (mostly expository) talk will be about invariant theory viewed through the lens of computational complexity. Invariant theory is the study of symmetries, captured by...
Feb 24

Computer Science/Discrete Mathematics Seminar I

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Lijie Chen
11:00am | Simonyi Hall 101
We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it...