Zobrazeno 1 - 10
of 102
pro vyhledávání: '"Omer Reingold"'
Publikováno v:
Theory of Computing. 17:1-35
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph $G$, a positive integer $r$, and a set $S$ of vertices, approximates the conductance of $S$ in the $r$-step random walk on $G$ to within a factor of $1+\epsilo
Publikováno v:
Theory of Computing. 16:1-55
This paper uses a variant of the notion of \emph{inaccessible entropy} (Haitner, Reingold, Vadhan and Wee, STOC 2009), to give an alternative construction and proof for the fundamental result, first proved by Rompel (STOC 1990), that \emph{Universal
Publikováno v:
Proceedings of the National Academy of Sciences of the United States of America
Significance We revisit the problem of ensuring statistically valid inferences across diverse target populations from a single source of training data. Our approach builds a surprising technical connection between the inference problem and a techniqu
Autor:
Omer Reingold
Publikováno v:
Communications of the ACM. 63:25-27
Considering the far-reaching and fundamental implications of computing beyond digital computers.
Publikováno v:
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities" -- what is the probability of 5-year survival after cancer diagnosis? -- and which increasingly form the basis for life-altering decisions
Publikováno v:
Theory of Computing
Publikováno v:
Journal of Cryptology. 31:134-161
Motivated by applications in large storage systems, we initiate the study of incremental deterministic public-key encryption. Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to
Autor:
Omer Reingold, Shai Vardi
Publikováno v:
Journal of Computer and System Sciences. 82:1180-1200
Given an input $x$, and a search problem $F$, local computation algorithms (LCAs) implement access to specified locations of $y$ in a legal output $y \in F(x)$, using polylogarithmic time and space. Mansour et al., (2012), had previously shown how to
Publikováno v:
EC
As algorithmic prediction systems have become widespread, fears that these systems may inadvertently discriminate against members of underrepresented populations have grown. With the goal of understanding fundamental principles that underpin the grow
Publikováno v:
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
FOCS
FOCS
Many selection procedures involve ordering candidates according to their qualifications. For example, a university might order applicants according to a perceived probability of graduation within four years, and then select the top 1000 applicants. I