7 Result(s)
within
Raghav Kulkarni
Algorithm Analysis and Problem Complexity
Computation by Abstract Devices
-
Chapter and Conference Paper
A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small
The perfect matching problem for general graphs reduces to the same for regular graphs. Even finding an NC algorithm for the perfect matching problem in cubic (3-regular) or 4-regular graphs will suffice to so...
-
Chapter and Conference Paper
Planarity, Determinants, Permanents, and (Unique) Matchings
We explore the restrictiveness of planarity on the complexity of computing the determinant and the permanent, and show that both problems remain as hard as in the general case, i.e. GapL and #P complete. On the o...
-
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
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can ...
-
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
Upper Bounds on Fourier Entropy
Given a function \(f : {\{0,1\}}^n\rightarrow \mathbb {R}\) ...
-
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...
