Algorithms and Complexity Seminars

Clément Canonne: Fifty Shades of Adaptivity (in Property Testing)
Wednesday, April 5, 2017 - 4:00pm to 5:00pm
Adaptivity is known to play a crucial role in property testing. In
particular, there exist properties for which there is an exponential gap
Dean Doron: Explicit two-source extractors for near-logarithmic min-entropy
Wednesday, March 15, 2017 - 4:00pm to 5:00pm

In this talk, we show an explicit construction of extractors for two independent sources of near-logarithmic min-entropy.
Previous constructions required either polylog(n) min-entropy or more than two sources.

Yuval Filmus: Twenty (simple) questions
Thursday, March 2, 2017 - 4:00pm to 5:00pm
Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average.
Nika Haghtalab: Opting Into Optimal Matchings
Wednesday, March 1, 2017 - 4:00pm to 5:00pm

Kidney transplant is sometimes the best treatment for people who suffer from chronic kidney disease.

Ilias Diakonikolas: A New Approach for Distribution Testing
Wednesday, October 12, 2016 - 4:00pm to 5:00pm

We study problems in distribution property testing: Given sample access to one or more unknown discrete distributions, we want to determine whether they have some global property or are

A Nearly Tight Sum of Squares Lower Bound for Planted Clique
Wednesday, April 27, 2016 - 4:00pm to 5:00pm

Abstract: We prove that with high probability over the draw of a graph from the Erdos-Renyi distribution G(n,1/2), the ~n^d time, degree d sum of squares relaxation for the clique problem gives a value of ~n^{1/2-o(1)} for any d = o(\log(n)).

Rati Gelashvili: Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
Wednesday, May 20, 2015 - 4:00pm to 5:00pm

Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules.

Shay Solomon: Dynamic Maximum Matching and Related Problems
Thursday, May 7, 2015 - 4:00pm to 5:00pm

Graph matching is one of the most well-studied problems in combinatorial optimization, with applications ranging from scheduling and object recognition to numerical analysis and computational chemistry.

TALK: JM Landsberg: Geometry and the Complexity of Matrix Multiplication
Wednesday, April 29, 2015 - 4:00pm to 5:00pm

Ever since Strassen showed that nxn matrices can be multiplied using O(n^2.81) arithmetic operations as opposed to the usual

Sergey Gorbunov: Leveled Fully Homomorphic Signatures from Standard Lattices
Wednesday, April 22, 2015 - 4:00pm to 5:00pm

Abstract: In a homomorphic signature scheme, a user Alice signs some large dataset $x$ using her secret signing key and uploads the signed data to an untrusted remote server.


Subscribe to Algorithms and Complexity Seminars