Randomized Littlestone dimension

12 March 2024, BGU colloquium: Randomized online learning abstractslides

Littlestone dimension gives the optimal mistake bound in online learning. The randomized Littlestone dimension gives the optimal mistake bound when the learner is randomized.

Whereas the Littlestone dimension is the maximum minimum depth of a shattered tree, the randomized Littlestone dimension is half the maximum expected depth of a shattered tree, where the expectation is with respect to the random process which starts at the root and at each step, chooses a child at random.

Joint work with Steve Hanneke, Idan Mehalel, and Shay Moran.

Boolean function analysis on the symmetric group

24 May 2023, Technion combinatorics seminar: Nearly linear functions on the symmetric group abstractnotes
15 May 2023, AGT online seminar: Orthogonal basis of eigenvectors for the Johnson and Kneser graphs abstractnotes
23 April 2023, Bar-Ilan: "Fourier expansion" for functions on the symmetric group abstractnotes
17 April 2023, HUJI: "Fourier expansion" for functions on the symmetric group abstractnotes
22 November 2021, Technion: Square matrices where a random generalized diagonal is close to 0/1 abstract
18 October 2021, HUJI: When is a linear function on the symmetric group almost Boolean? abstractnotes

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

5 February 2024, Probability and Analysis Webinar: Sparse "juntas" videoabstractslides
28 July 2023, Simons institute: Low degree functions which are almost Boolean videoabstractnotes
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

Approximate polymorphisms

2 May 2022, BGU: Approximate Polymorphisms abstractnotes
3 November 2021, Technion: Approximate Polymorphisms
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.


3 September 2023, IMU: Irreducible subcube partitions abstractslides
28 July 2022, Dagstuhl: Information complexity abstractslides
6 December 2021, AIM: Intersecting families and Hoffman's bound abstractslides
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