2 citations · 2 across the 4 of their papers we have counts for
5 papers
On the Shortest Lattice Vector vs. the Shortest Basis
Yael Eisenberg, Itamar Rot, Muli Safra
Given an arbitrary basis for a mathematical lattice, to find a ``good" basis for it is one of the classic and important algorithmic problems. In this note, we give a new and simple…
Towards a Proof of the Fourier--Entropy Conjecture?
Esty Kelman, Guy Kindler, Noam Lifshitz +2
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental…
On the Converse of Talagrand's Influence Inequality
Saleet Klein, Amit Levi, Muli Safra +2
In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of nu…
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Dana Ron, Ronitt Rubinfeld, Muli Safra +1
The {\em Total Influence} ({\em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monot…
On Planning while Learning
S. Safra, M. Tennenholtz
This paper introduces a framework for Planning while Learning where an agent is given a goal to achieve in an environment whose behavior is only partially known to the agent. We di…