Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

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

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 >>>

TR13-168 | 29th November 2013
Raghav Kulkarni, Avishay Tal

On Fractional Block Sensitivity

Revisions: 1 , Comments: 1

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 >>>

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

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 >>>

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

{Upper Bounds on Fourier Entropy

Revisions: 2

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 >>>

TR12-063 | 17th May 2012
Raghav Kulkarni, Miklos Santha

Query complexity of matroids

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 >>>

TR10-201 | 21st December 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari

Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

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 >>>

TR10-079 | 28th April 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

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 >>>

TR09-024 | 26th February 2009
Raghav Kulkarni

On the Power of Isolation in Planar Structures

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 >>>

TR07-035 | 3rd April 2007
Mark Braverman, Raghav Kulkarni, Sambuddha Roy

Parity Problems in Planar Graphs

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 >>>

ISSN 1433-8092 | Imprint