5 Result(s)
-
Chapter and Conference Paper
Dynamic Complexity of Directed Reachability and Other Problems
We report progress on dynamic complexity of well-known graph problems such as reachability and matching. In this model, edges are dynamically added and deleted and we measure the complexity of each update/quer...
-
Chapter and Conference Paper
On the Complexity of Trial and Error for Constraint Satisfaction Problems
In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle wh...
-
Chapter and Conference Paper
Reachability is in DynFO
We consider the dynamic complexity of some central graph problems such as Reachability and Matching and linear algebraic problems such as Rank and Inverse. As elementary change operations we allow insertion and d...
-
Chapter and Conference Paper
Efficient Compression Technique for Sparse Sets
Recent growth in internet has generated large amount of data over web. Representations of most of such data are high-dimensional and sparse. Many fundamental subroutines of various data analytics tasks such as...
-
Chapter and Conference Paper
Minwise-Independent Permutations with Insertion and Deletion of Features
The seminal work of Broder et al. [5] introduces the \(\textrm{minHash}\) minHash ...
