BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraph that asks almost optimal number of queries.
We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit f over a field of characteristic 2 of degree~d. Decide whether f, expressed as an equivalent multivariate polynomial, contains a multilinear monomial of degree d. This problem was solved by Williams \cite{W} and Björklund et. al. \cite{BHKK} for a white box (the circuit is given as an input) that contains arithmetic circuit. We show a simple black box algorithm that solves the problem with the same time complexity. This gives a simple randomized algorithm for the simple k-path problem for directed graphs of the same time complexity\footnote{O∗(f(k)) is O(poly(n)⋅f(k))} O∗(2k) as in \cite{W} and with reusing the same ideas from \cite{BHKK} with the above gives another algorithm (probably not simpler) for undirected graphs of the same time complexity O∗(1.657k) as in \cite{B10,BHKK}.
We consider the problem of proper learning a Boolean Halfspace with integer weights {0,1,…,t} from membership queries only. The best known algorithm for this problem is an adaptive algorithm that asks nO(t5) membership queries where the best lower bound for the number of membership queries is nt [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 nO(t) membership queries. We also give a non-adaptive proper learning algorithm that asks nO(t3) membership queries.
An r-simple k-path is a {path} in the graph of length k that passes through each vertex at most r times. The r-SIMPLE k-PATH problem, given a graph G as input, asks whether there exists an r-simple k-path in G. We first show that this problem is NP-Complete. We then show that there is a graph G that contains an r-simple k-path and no simple path of length greater than 4logk/logr. So this, in a sense, motivates this problem especially when one's goal is to find a short path that visits many vertices in the graph while bounding the number of visits at each vertex. We then give a randomized algorithm that runs in time poly(n)⋅2O(k⋅logr/r) that solves the r-SIMPLE k-PATH on a graph with n vertices with one-sided error. We also show that a randomized algorithm with running time poly(n)⋅2(c/2)k/r with c<1 gives a randomized algorithm with running time $\poly(n)\cdot 2^{cn}$ for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an O(logr) factor.
In this paper, we study the problem of learning a monotone DNF with at most s terms of size (number of variables in each term) at most r (s term r-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing. We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with query complexities that are almost optimal. All the algorithms we present in this paper run in time linear in the query complexity and the number of variables n. In addition, all of the algorithms we present in this paper are asymptotically tight for fixed r and/or s.
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.