Events

Agreement testing (aka direct product testing), checks if consistent local information reveals global structure. Beyond its theoretical connections to probabilistic checkable proofs (PCPs), constructing agreement testers is a fundamental combinatorial question that has exciting applications in coding theory and hardness amplification.

In recent work we construct new derandomized `1%-regime' agreement tests. Derandomization of these tests is an important stepping stone towards derandomizing many PCPs, such as the parallel repetition PCP.

We will define agreement tests and give some background on their importance. Then we will see a surprising connection between agreement testing to a problem in algebraic topology. Finally, we will discuss how strong group theoretic tools solve this problem and lead to our construction.

Based on joint work with Irit Dinur and Alex Lubotzky.

LLMs offer users intuitive interfaces for interacting with textual information. The integration of vision into LLMs through VLMs has enabled these models to "see" and reason over visual content. However, these VLMs possess generic knowledge, lacking a personal touch. This raises an intriguing question: can we equip these models with the ability to comprehend and utilize user-specific concepts, tailored specifically to you? Can we ask the model questions about you, such as what you are wearing or what your friend is doing in the image? In this talk, we will explore how we can personalize VLMs to each user, offering more meaningful interactions that better reflect individual experiences and relationships.

Bio:

Yuval is a PhD student at Tel Aviv University under the supervision of Prof. Daniel Cohen-Or. His research centers around leveraging generative models to give users greater control and creative freedom when interacting with visual content. Currently interning at Snap Research under Kfir Aberman, Yuval is also exploring new approaches for personalizing generative models.

TBA

TBA

Vizing’s Theorem provides an algorithm that edge colors any graph of maximum degree Δ using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1+o(1))Δ colors suffice online. This would make edge coloring a rare problem, for which "online is (nearly) as easy as offline". In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and “local” edge-coloring.

Talk based in part on joint works with many wonderful and colorful collaborators, including Sayan Bhattacharya, Joakim Blikstad, Ilan R. Cohen, Fabrizio Grandoni, Seffi Naor, Binghui Peng, Amin Saberi, Aravind Srinivasan, Ola Svensson and Radu Vintan.

TBA

TBA

TBA

TBA

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy (Hastad, Impagliazzo, Levin, and Luby [SICOMP 99]), and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

Joint work with Iftach Haitner and Jad Silbak.