BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Ali Z. Abdi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let ${\cal F}$ be a set of blocks of a $t$-set $X$. $(X,{\cal F})$ is called $(w,r)$-cover-free family ($(w,r)-$CFF) provided that, the intersection of any $w$ blocks in ${\cal F}$ is not contained in the union of any other $r$ blocks in ${\cal F}$. We give new asymptotic lower bounds for the number of minimum points $t$ in a $(w,r)$-CFF when $w\le r=|{\cal F}|^ε$ for some constant $ε\ge 1/2$.
We consider the problem of proper learning a Boolean Halfspace with integer weights $\{0,1,\ldots,t\}$ from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$ membership queries where the best lower bound for the number of membership queries is $n^t$ [Learning Threshold Functions with Small Weights Using Membership Queries. COLT 1999] In this paper we close this gap and give an adaptive proper learning algorithm with two rounds that asks $n^{O(t)}$ membership queries. We also give a non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membership queries.