Explanipedia

A LYM Inequality For Product Measures Open

Gal Yehuda, Amir Yehudayoff · 2025

This note proves a version of Lubell-Yamamoto-Meshalkin inequality for general product measures.

Geometric covering using random fields Open

Amit Shahar, Daniel Keren, Felipe Gonçalves, Gal Yehuda · 2025

Subgroups of a free group with every growth rate Open

Michail Louvaris, Gal Yehuda, Daniel T. Wise · 2025

For every $α\in [1,2r-1]$, we show there exists a subgroup $H

Density of growth-rates of subgroups of a free group and the non-backtracking spectrum of the configuration model Open

Michail Louvaris, Daniel T. Wise, Gal Yehuda · 2024

We prove the set of growth-rates of subgroups of a rank~$r$ free group is dense in $[1,2r-1]$. Our main technical contribution is a concentration result for the leading eigenvalue of the non-backtracking matrix in the configuration model.

Geometric Covering using Random Fields Open

Felipe Gonçalves, Daniel Keren, Amit Shahar, Gal Yehuda · 2023

A set of vectors $S \subseteq \mathbb{R}^d$ is $(k_1,\varepsilon)$-clusterable if there are $k_1$ balls of radius $\varepsilon$ that cover $S$. A set of vectors $S \subseteq \mathbb{R}^d$ is $(k_2,δ)$-far from being clusterable if there ar…

Probabilistic Invariant Learning with Randomized Linear Classifiers Open

Leonardo Cotta, Gal Yehuda, Assaf Schuster, Chris J. Maddison · 2023

Designing models that are both expressive and preserve known invariances of tasks is an increasingly hard problem. Existing solutions tradeoff invariance for computational or memory resources. In this work, we show how to leverage randomne…

Coin Flipping Neural Networks Open

Yuval Sieradzki, Nitzan Hodos, Gal Yehuda, Assaf Schuster · 2022

We show that neural networks with access to randomness can outperform deterministic networks by using amplification. We call such networks Coin-Flipping Neural Networks, or CFNNs. We show that a CFNN can approximate the indicator of a $d$-…

A lower bound for essential covers of the cube Open

Gal Yehuda, Amir Yehudayoff · 2021

Essential covers were introduced by Linial and Radhakrishnan as a model that captures two complementary properties: (1) all variables must be included and (2) no element is redundant. In their seminal paper, they proved that every essentia…

Slicing the hypercube is not easy Open

Gal Yehuda, Amir Yehudayoff · 2021

We prove that at least $Ω(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover nu…

The complexity of computing (almost) orthogonal matrices with ε-copies of the Fourier transform Open

Nir Ailon, Gal Yehuda · 2020

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numer…

It's Not What Machines Can Learn, It's What We Cannot Teach Open

Gal Yehuda, Moshe Gabel, Assaf Schuster · 2020

Can deep neural networks learn to solve any task, and in particular problems of high complexity? This question attracts a lot of interest, with recent works tackling computationally hard tasks such as the traveling salesman problem and sat…

The Complexity of Computing a Fourier Perturbation. Open

Nir Ailon, Gal Yehuda · 2016

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numer…

The Complexity of Computing (Almost) Unitary Matrices With $\eps$-Copies of the Fourier Transform Open

Nir Ailon, Gal Yehuda · 2016

The complexity of computing the Fourier transform is a longstanding open problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of papers that, roughly speaking, a speedup of the Fourier transform computation implies numer…

Gal Yehuda YOU? Author Swipe