Author name cluster

Vijay Raghavan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2003 Journal Article

Scalar aggregation in inconsistent databases

Marcelo Arenas
Leopoldo Bertossi
Jan Chomicki
Xin He
Vijay Raghavan
Jeremy Spinrad

We consider here scalar aggregation queries in databases that may violate a given set of functional dependencies. We define consistent answers to such queries to be greatest-lowest/least-upper bounds on the value of the scalar function across all (minimal) repairs of the database. We show how to compute such answers. We provide a complete characterization of the computational complexity of this problem. We also show how tractability can be improved in several special cases (one involves a novel application of Boyce–Codd Normal Form) and present a practical hybrid query evaluation method.

Details DOI

TCS Journal 2002 Journal Article

Decision tree approximations of Boolean functions

Dinesh Mehta
Vijay Raghavan

Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function f, say as a read-once branching program, one can find a decision tree T which approximates f to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent f and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function f instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.

Details DOI

TCS Journal 2001 Journal Article

Monotone term decision lists

David Guijarro
Vı́ctor Lavı́n
Vijay Raghavan

We introduce a new representation class of Boolean functions – monotone term decision lists – which combines compact representation size with tractability of essential operations. We present many properties of the class which make it an attractive alternative to traditional universal representation classes such as DNF formulas or decision trees. We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k⩾0, k-term monotone decision lists are exactly and properly learnable with n O(k) membership queries in n O(k3) time. We also show that n Ω(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k⩾2) and general monotone term decision lists are not learnable with equivalence queries alone. We also show that a subclass of monotone term decision lists (disj-MDL) is learnable with equivalence and membership queries, while neither type of query alone suffices.

Details DOI