All reports by Author Tomer Grossman:

__
TR23-207
| 13th December 2023
__

Omri Ben-Eliezer, Tomer Grossman, Moni Naor#### Does Prior Knowledge Help Detect Collisions?

__
TR21-152
| 8th November 2021
__

Gal Arnon, Tomer Grossman#### Min-Entropic Optimality

__
TR19-113
| 5th September 2019
__

Tomer Grossman, Ilan Komargodski, Moni Naor#### Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Omri Ben-Eliezer, Tomer Grossman, Moni Naor

Suppose you are given a function $f\colon [n] \to [n]$ via (black-box) query access to the function. You are looking to find something local, like a collision (a pair $x \neq y$ s.t.\ $f(x)=f(y)$). The question is whether knowing the `shape' of the function helps you or not (by shape ... more >>>

Gal Arnon, Tomer Grossman

We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is $k(n)$ Min-Entropic Optimal if for every distribution $D$ with min-entropy at least $k(n)$, its expected running time when its input is drawn ... more >>>

Tomer Grossman, Ilan Komargodski, Moni Naor

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>