All reports by Author Raghav Kulkarni:

__
TR14-061
| 21st April 2014
__

Raghav Kulkarni, Youming Qiao, Xiaoming Sun#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

__
TR14-034
| 3rd March 2014
__

GĂˇbor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram#### On the complexity of trial and error for constraint satisfaction problems

__
TR13-168
| 29th November 2013
__

Raghav Kulkarni, Avishay Tal#### On Fractional Block Sensitivity

Revisions: 1
,
Comments: 1

__
TR13-142
| 11th October 2013
__

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni#### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

Revisions: 2

__
TR13-052
| 3rd April 2013
__

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh#### {Upper Bounds on Fourier Entropy

Revisions: 2

__
TR12-063
| 17th May 2012
__

Raghav Kulkarni, Miklos Santha#### Query complexity of matroids

__
TR10-201
| 21st December 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

__
TR10-079
| 28th April 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

__
TR09-024
| 26th February 2009
__

Raghav Kulkarni#### On the Power of Isolation in Planar Structures

__
TR07-035
| 3rd April 2007
__

Mark Braverman, Raghav Kulkarni, Sambuddha Roy#### Parity Problems in Planar Graphs

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

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 Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

GĂˇbor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

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 which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and

Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed

that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ...
more >>>

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

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 be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>

Raghav Kulkarni, Miklos Santha

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is ``evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon

the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space

complexity bounds for some related problems. Summarizing, we show that, constructing:

1. a Perfect Matching in bipartite planar graphs is in ...
more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam

We investigate the space complexity of certain perfect matching

problems over bipartite graphs embedded on surfaces of constant genus

(orientable or non-orientable). We show that the problems of deciding

whether such graphs have (1) a perfect matching or not and (2) a

unique perfect matching or not, are in the ...
more >>>

Raghav Kulkarni

The purpose of this paper is to study the deterministic

{\em isolation} for certain structures in directed and undirected

planar graphs.

The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and

\cite{dkr08} isolate a perfect matching in ...
more >>>

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. ... more >>>