Skip to main content

18 Result(s)

within Raghav Kulkarni Remove this filter Computer Science Remove this filter

and

  1. No Access

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

    Rameshwar Pratap, Raghav Kulkarni in Similarity Search and Applications (2023)

  2. No Access

    Chapter and Conference Paper

    \(\mathsf {CrystalBall}\) : Gazing in the Black Box of SAT Solving

    Boolean satisfiability is a fundamental problem in computer science with a wide range of applications including planning, configuration management, design and verification of software/hardware systems

    Mate Soos, Raghav Kulkarni, Kuldeep S. Meel in Theory and Applications of Satisfiability … (2019)

  3. No Access

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

    Rameshwar Pratap, Ishan Sohony… in Advances in Knowledge Discovery and Data M… (2018)

  4. No Access

    Chapter and Conference Paper

    Upper Bounds on Fourier Entropy

    Given a function \(f : {\{0,1\}}^n\rightarrow \mathbb {R}\) ...

    Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam… in Computing and Combinatorics (2015)

  5. No Access

    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

    Raghav Kulkarni, Youming Qiao, **aoming Sun in Theory and Applications of Models of Compu… (2015)

  6. No Access

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

    Samir Datta, Raghav Kulkarni, Anish Mukherjee… in Automata, Languages, and Programming (2015)

  7. No Access

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

    Samir Datta, William Hesse, Raghav Kulkarni in Automata, Languages, and Programming (2014)

  8. No Access

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

    Samir Datta, Raghav Kulkarni in Theory and Applications of Models of Computation (2014)

  9. No Access

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

    Abhishek Bhrushundi, Sourav Chakraborty… in Computer Science - Theory and Applications (2014)

  10. No Access

    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

    Thomas Decker, Gábor Ivanyos… in Mathematical Foundations of Computer Scien… (2014)

  11. No Access

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

    Gábor Ivanyos, Raghav Kulkarni, Youming Qiao… in Automata, Languages, and Programming (2014)

  12. No Access

    Chapter and Conference Paper

    Query Complexity of Matroids

    Let \(\mathcal{M}\) be a bridgeless matroid on ground set {1,...,n} and ...

    Raghav Kulkarni, Miklos Santha in Algorithms and Complexity (2013)

  13. No Access

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

    Raghav Kulkarni, Youming Qiao, **aoming Sun in Theory and Applications of Models of Compu… (2013)

  14. No Access

    Article

    Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

    We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes...

    Samir Datta, Raghav Kulkarni, Sambuddha Roy in Theory of Computing Systems (2010)

  15. No Access

    Article

    Space-Efficient Counting in Graphs on Surfaces

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

    Mark Braverman, Raghav Kulkarni, Sambuddha Roy in computational complexity (2009)

  16. No Access

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

    Samir Datta, Raghav Kulkarni, Nutan Limaye… in Computer Science – Theory and Applications (2007)

  17. No Access

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

    Raghav Kulkarni in Algorithms and Complexity (2006)

  18. No Access

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

    Raghav Kulkarni, Meena Mahajan in Algorithms – ESA 2004 (2004)