13 citations · 32 across the 25 of their papers we have counts for
6 papers · 1 filter
Dense Testers: Almost Linear Time and Locally Explicit Constructions
Nader H. Bshouty
We develop a new notion called -tester for a set of functions . A -tester for maps each element to a finite number of elements $B_a=\{b_1,\…
Linear time Constructions of some -Restriction Problems
Nader H. Bshouty
We give new linear time globally explicit constructions for perfect hash families, cover-free families and separating hash functions.
Learning Boolean Halfspaces with Small Weights from Membership Queries
Hasan Abasi, Ali Z. Abdi, Nader H. Bshouty
We consider the problem of proper learning a Boolean Halfspace with integer weights from membership queries only. The best known algorithm for this problem is an…
On Exact Learning Monotone DNF from Membership Queries
Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi
In this paper, we study the problem of learning a monotone DNF with at most terms of size (number of variables in each term) at most ( term -MDNF) from membership que…
A Simple Algorithm for Hamiltonicity
Hasan Abasi, Nader H. Bshouty
We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit over a field of characteristic of degree~.…
On -Simple -Path
Hasan Abasi, Nader H. Bshouty, Ariel Gabizon +1
An -simple -path is a {path} in the graph of length that passes through each vertex at most times. The -SIMPLE -PATH problem, given a graph as input, asks w…