Zobrazeno 1 - 10
of 130
pro vyhledávání: '"Fischer, Eldar"'
We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for $n$-dimensional distributions that is quasi-linear in $n$, improving the previously known $\tilde{
Externí odkaz:
http://arxiv.org/abs/2408.02347
Autor:
Fischer, Eldar
An $\epsilon$-test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at least inversely proportional in $\epsilon$. However, to the best
Externí odkaz:
http://arxiv.org/abs/2403.04999
Autor:
Fischer, Eldar
We investigate models of relations over a bounded continuous segment of real numbers, along with the natural linear order over the reals being provided as a "hard-coded" relation. This paper presents a generalization of a lemma from [Ben-Eliezer, Fis
Externí odkaz:
http://arxiv.org/abs/2401.08082
The Huge Object model is a distribution testing model in which we are given access to independent samples from an unknown distribution over the set of strings $\{0,1\}^n$, but are only allowed to query a few bits from the samples. We investigate the
Externí odkaz:
http://arxiv.org/abs/2308.15988
Autor:
Adar, Tomer, Fischer, Eldar
The Huge Object model for distribution testing, first defined by Goldreich and Ron in 2022, combines the features of classical string testing and distribution testing. In this model we are given access to independent samples from an unknown distribut
Externí odkaz:
http://arxiv.org/abs/2306.16129
Autor:
Fischer, Eldar, Makowsky, Johann A.
In this paper we study the number of finite topologies on an $n$-element set subject to various restrictions.
Comment: 12 pages
Comment: 12 pages
Externí odkaz:
http://arxiv.org/abs/2303.11903
A sequence $s(n)$ of integers is MC-finite if for every $m \in \mathbb{N}^+$ the sequence $s^m(n) = s(n) \bmod{m}$ is ultimately periodic. We discuss various ways of proving and disproving MC-finiteness. Our examples are mostly taken from set partiti
Externí odkaz:
http://arxiv.org/abs/2302.08265
The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science. The original distribution testing model relies on samples d
Externí odkaz:
http://arxiv.org/abs/2207.12514
Autor:
Fischer, Eldar, Makowsky, Johann A.
The original Specker-Blatter Theorem (1983) was formulated for classes of structures $\mathcal{C}$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modul
Externí odkaz:
http://arxiv.org/abs/2206.12135
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a dis
Externí odkaz:
http://arxiv.org/abs/2110.09972