All reports by Author Nader Bshouty:

__
TR18-053
| 19th March 2018
__

Nader Bshouty#### Lower Bound for Non-Adaptive Estimate the Number of Defective Items

__
TR16-083
| 23rd May 2016
__

Nader Bshouty#### Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets

__
TR15-006
| 6th January 2015
__

Nader Bshouty#### Dense Testers: Almost Linear Time and Locally Explicit Constructions

__
TR13-012
| 16th January 2013
__

Hasan Abasi, Nader Bshouty#### A Simple Algorithm for Undirected Hamiltonicity

__
TR13-011
| 10th January 2013
__

Nader Bshouty#### Multilinear Complexity is Equivalent to Optimal Tester Size

__
TR12-011
| 7th February 2012
__

Nader Bshouty#### Testers and their Applications

__
TR11-124
| 15th September 2011
__

Nader Bshouty, Hanna Mazzawi#### Algorithms for the Coin Weighing Problems with the Presence of Noise

Nader Bshouty

We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least $\tilde\Omega((\log n)(\log(1/\delta)))$ tests. This solves the open problem posed by Damaschke and Sheikh Muhammad.

more >>>Nader Bshouty

Derandomization of Chernoff bound with union bound is already proven in many papers.

We here give another explicit version of it that obtains a construction of size

that is arbitrary close to the probabilistic nonconstructive size.

We apply this to give a new simple polynomial time constructions of

almost $k$-wise ...
more >>>

Nader Bshouty

We develop a new notion called {\it $(1-\epsilon)$-tester for a

set $M$ of functions} $f:A\to C$. A $(1-\epsilon)$-tester

for $M$ maps each element $a\in A$ to a finite number of

elements $B_a=\{b_1,\ldots,b_t\}\subset B$ in a smaller

sub-domain $B\subset A$ where for every $f\in M$ if

$f(a)\not=0$ then $f(b)\not=0$ for at ...
more >>>

Hasan Abasi, Nader Bshouty

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>

Nader Bshouty

In this paper we first show that Tester for an $F$-algebra $A$

and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear

algorithm for the product of elements in $A$

(see Algebraic

complexity theory. vol. 315, Springer-Verlag). Our

result is constructive in deterministic polynomial time. ...
more >>>

Nader Bshouty

We develop a new notion called {\it tester of a class $\cM$ of

functions} $f:\cA\to \cC$ that maps the elements $\bfa\in \cA$ in

the domain $\cA$ of the function to a finite number (the size of

the tester) of elements $\bfb_1,\ldots,\bfb_t$ in a smaller

sub-domain $\cB\subset \cA$ where the property ...
more >>>

Nader Bshouty, Hanna Mazzawi

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was ... more >>>