13 Result(s)
within
Conference Paper
Raghav Kulkarni
Algorithm Analysis and Problem Complexity
-
Chapter and Conference Paper
Seeking a Vertex of the Planar Matching Polytope in NC
For planar graphs, counting the number of perfect matchings (and hence determining whether there exists a perfect matching) can be done in NC [4,10]. For planar bipartite graphs, finding a perfect matching whe...
-
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
Query Complexity of Matroids
Let \(\mathcal{M}\) be a bridgeless matroid on ground set {1,...,n} and ...
-
Chapter and Conference Paper
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuil...
-
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
Space Complexity of Optimization Problems in Planar Graphs
We initiate the study of space complexity of certain optimization problems restricted to planar graphs. We provide upper bounds and hardness results in space complexity for some of these well-studied problems ...
-
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
An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group
In the theory of algebraic groups, parabolic subgroups form a crucial building block in the structural studies. In the case of general linear groups over a finite field
-
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
On the Power of Parity Queries in Boolean Decision Trees
In an influential paper, Kushilevitz and Mansour (1993) introduced a natural extension of Boolean decision trees called parity decision tree (PDT) where one may query the sum modulo
-
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...
