Bounded indistinguishability for simple sources

6 April 2021, TAU Theory Seminar abstractslides
25 March 2021, Dagstuhl complexity wokshop abstractslides
11 March 2021, Oxford–Warwick Complexity Meetings abstractslides

Let $X,Y$ be $\mathrm{polylog}(n)$-indistinguishable. Braverman famously showed that if $Y$ is uniform then $X,Y$ fool $\mathsf{AC^0}$. In contrast, there exists a pair of $\Theta(\sqrt{n})$-indistinguishable distributions which do not even fool OR.

Under what conditions on $X,Y$ can we recover a Braverman-style theorem?

Joint work with Andrej Bogdanov, K. Dinesh, Yuval Ishai, Avi Kaplan, and Akshay Srinivasan.

Analysis of Boolean function on exotic domains

22 January 2019, CAALM (CMI): Discrete harmonic analysis: beyond the Boolean hypercube abstractslides
6 March 2018, IAS: Boolean function analysis: beyond the Boolean cube (2/2) videoabstractnotes
5 March 2018, IAS: Boolean function analysis: beyond the Boolean cube (1/2) videoabstractslides
9 June 2016, Bar Ilan: Fourier analysis on the slice (?)
8 March 2016, Tel Aviv: Analysis on the slice abstractnotes
7 December 2015, CMS winter meeting (Montréal) abstractslides
27 February 2015, Toronto notes
23 September 2014, IAS: Analysis of Boolean functions on association schemes videoabstract

Structure theorems for low-degree functions

10 January 2019, Bar Ilan: Almost Boolean functions of degree 1 on the symmetric group abstractnotes
24 March 2019, Tel Aviv: Structure of almost Boolean low degree functions abstract
11 March 2019, Hebrew University: Structure of (almost) low-degree Boolean functions abstract
8 April 2014, Columbia: Structure theorems for almost low degree functions abstractslides
2 December 2013, Simons institute: Friedgut–Kalai–Naor for Boolean functions on $S_n$ videoabstractnotes

AND testing

13 Aug 2021, CU Boulder: Approximate Polymorphisms abstractslides
27 May 2021, Bar-Ilan: Approximate Polymorphisms abstractnotes
12 April 2021, MIT online seminar videoabstractslides
7 March 2021, Tel Aviv: Approximate Polymorphisms abstractslides
25 May 2020, HUJI: Oligarchy testing abstractnotes
17 March 2020, Technion: Property Testing meets Universal Algebra: Oligarchy Testing slides
28 February 2020, TIFR: Universal Algebra meets Property Testing: Oligarchy Testing abstractnotes
9 October 2019, Warwick: One-sided linearity testing
27 September 2019, Oxford: One-sided linearity testing abstractnotes

Linearity testing states that if $\Pr[f(x \oplus y) = f(x) \oplus f(y)] \approx 1$ then $f \approx \mathsf{XOR}$.

Together with Noam Lifshitz, Dor Minzer and Elchanan Mossel, we showed that if $\Pr[f(x \land y) = f(x) \land f(y)] \approx 1$ then $f \approx \mathsf{AND}$.

Together with Gilad Chase, Dor Minzer and Nitin Saurabh, we extended this for arbitrary inner functions (replacing $\oplus$ or $\land$).

Twenty (simple) questions

26 April 2021, HUJI Computer Science seminar videoabstractslides
10 June 2019, Weizmann Institute abstract
29 January 2019, TIFR: Twenty Questions: Distributional Search Theory abstract
6 June 2018, HALG (Amsterdam) slides
13 June 2017, TAU abstract
4 June 2017, Ariel abstract
28 May 2017, IMU abstract
29 March 2017, Open University abstract
2 March 2017, MIT abstractnotes
23 September 2016, Toronto: Complexity-aware encoding abstractnotes

Based on our work with Yuval Dagan, Ariel Gabizon and Shay Moran, and on our work with Yuval Dagan, Daniel Kane and Shay Moran.

Limitations of the Coppersmith–Winograd technique

10 May 2016, Ben-Gurion University: On the Coppersmith–Winograd approach to matrix multiplication abstract
6 April 2016, Ariel: On the Coppersmith–Winograd approach to matrix multiplication abstract
4 January 2015, Tel Aviv
31 December 2014, Technion abstractslides
24 December 2014, Hebrew University

Based on our work together with Andris Ambainis and François Le Gall.

Monotone submodular maximization via non-oblivious local search

15 January 2020, FeigeFest: Foresight in submodular optimization abstractslides
8 June 2016, Ben-Gurion University abstract
5 October 2015, HIM (Bonn) videoslides
7 October 2014, IAS videonotes
22 January 2014, DIMACS summary
10 October 2011, China Theory Week (Aarhus) abstractslides

Maximizing a monotone submodular function over a matroid constraint is a fundamental combinatorial optimization problem, generalizing problems such as Maximum Coverage and MAX-SAT.

Calienscu, Chekuri, Pál and Vondrák devised the continuous greedy algorithm, which gives the optimal $1-1/e$ approximation ratio.

Together with Justin Ward, we have come up with an alternative algorithm which is more combinatorial in nature. We first devised an algorithm for the special case of maximum coverage, and then extended it to the general case.

Triangle-intersecting families of graphs

20 February 2019, TIFR: Applications of the Hoffman/Lovász bound abstractnotes
5 December 2015, CMS winter meeting (Montréal) slides
29 January 2015, Yale
4 February 2014, Rutgers notes
8 November 2013, Simons institute notes
6 May 2011, Ontario Combinatorics Workshop (Ryerson) abstractslides

An exposition of Triangle-intersecting families of graphs, our joint work with David Ellis and Ehud Friedgut, in which we show that if $\mathcal{F}$ is a family of graphs on $n$ points such that any two graphs in $\mathcal{F}$ contain a triangle, then $\mathcal{F}$ contains at most $1/8$ of the graphs.

The proof uses the spectral approach of Hoffman and Lovász.


24 November 2020, UCLA: Sauer–Shelah–Perles lemma for lattices videoabstractslides
24 June 2020, HUJI: Degree and sensitivity on the symmetric group abstractnotes
30 January 2020, Princeton: Hoffman bound for complexes abstractnotes
27 December 2018, Bar Ilan: Information complexity: a random walk perspective abstractnotes
2 December 2015, Technion: An instance of subset sum hard for cutting planes abstractnotes
4 March 2014, IAS: Fast matrix multiplication (2/2) videoabstractnoteshandout
25 February 2014, IAS: Fast matrix multiplication (1/2) videoabstractnoteshandout
25 June 2011, LCC (part of LICS): Monotone feasible interpolation as games abstractslidesnotes

Talks in Hebrew

23 December 2018, Technion: Intro to research abstractslides
19 December 2018, Technion Math Club: Complexity of graph coloring abstractnotes