BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nutan Limaye

Nutan Limaye appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingFormal Languages and Automata TheoryNetworking and Internet Architecture

Catalog footprint

What is connected

7works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2026arXiv

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems

In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). Separation theorems are well-studied in the context of classical complexity theory, Boolean circuit complexity, and algebraic complexity. In an important work of Forbes, Shpilka, Tzameret, and Wigderson (ToC, 2021), two proof techniques were introduced to prove lower bounds for subsystems of the IPS, namely the functional method and the multiples method. We use these techniques and obtain the following results. Hierarchy theorem for constant-depth IPS: Recently, Limaye, Srinivasan, and Tavenas (J. ACM 2025) proved a hierarchy theorem for constant-depth algebraic circuits. We adapt the result and prove a hierarchy theorem for constant-depth $\mathsf{IPS}$. We show that there is an unsatisfiable multilinear instance refutable by a depth-$Δ$ $\mathsf{IPS}$ such that any depth-($Δ/10)$ $\mathsf{IPS}$ refutation for it must have superpolynomial size. This result is proved by building on the multiples method. Separation theorems for multilinear IPS: In an influential work, Raz (ToC, 2006) unconditionally separated two algebraic complexity classes, namely multilinear $\mathsf{NC}^{1}$ from multilinear $\mathsf{NC}^{2}$. In this work, we prove a similar result for a well-studied fragment of multilinear-$\mathsf{IPS}$. Specifically, we present an unsatisfiable instance such that its functional refutation, i.e., the unique multilinear polynomial agreeing with the inverse of the polynomial over the Boolean cube, has a small multilinear-$\mathsf{NC}^{2}$ circuit. However, any multilinear-$\mathsf{NC}^{1}$ $\mathsf{IPS}$ refutation ($\mathsf{IPS}_{\mathsf{LIN}}$) for it must have superpolynomial size. This result is proved by building on the functional method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms

We consider optimal distributed computation of a given function of distributed data. The input (data) nodes and the sink node that receives the function form a connected network that is described by an undirected weighted network graph. The algorithm to compute the given function is described by a weighted directed acyclic graph and is called the computation graph. An embedding defines the computation communication sequence that obtains the function at the sink. Two kinds of optimal embeddings are sought, the embedding that---(1)~minimizes delay in obtaining function at sink, and (2)~minimizes cost of one instance of computation of function. This abstraction is motivated by three applications---in-network computation over sensor networks, operator placement in distributed databases, and module placement in distributed computing. We first show that obtaining minimum-delay and minimum-cost embeddings are both NP-complete problems and that cost minimization is actually MAX SNP-hard. Next, we consider specific forms of the computation graph for which polynomial time solutions are possible. When the computation graph is a tree, a polynomial time algorithm to obtain the minimum delay embedding is described. Next, for the case when the function is described by a layered graph we describe an algorithm that obtains the minimum cost embedding in polynomial time. This algorithm can also be used to obtain an approximation for delay minimization. We then consider bounded treewidth computation graphs and give an algorithm to obtain the minimum cost embedding in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Small Depth Proof Systems

A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by bounded fanin circuits of constant depth (NC^0), or of O(log log n) depth but with O(1) alternations (polylog AC^0). Each output bit depends on very few input bits; thus such proof systems correspond to a kind of local error-correction on a theorem-proof pair. We identify exactly how much power we need for proof systems to capture all regular languages. We show that all regular language have polylog AC^0 proof systems, and from a previous result (Beyersdorff et al, MFCS 2011, where NC^0 proof systems were first introduced), this is tight. Our technique also shows that MAJ has polylog AC^0 proof system. We explore the question of whether TAUT has NC^0 proof systems. Addressing this question about 2TAUT, and since 2TAUT is closely related to reachability in graphs, we ask the same question about Reachability. We show that both Undirected Reachability and Directed UnReachability have NC^0 proof systems, but Directed Reachability is still open. In the context of how much power is needed for proof systems for languages in NP, we observe that proof systems for a good fraction of languages in NP do not need the full power of AC^0; they have SAC^0 or coSAC^0 proof systems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

In-Network Estimation of Frequency Moments

We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of non-linear functions of the distributed data which is over a large alphabet. We consider three types of networks: point-to-point networks with gossip based communication, random planar networks in the connectivity regime and random planar networks in the percolating regime both of which use the slotted Aloha communication protocol. For each network type, we estimate the scaled $k$-th frequency moments, for $k \geq 2$. Specifically, for every $k \geq 2,$ we give a distributed randomized algorithm that computes, with probability $(1-δ),$ an $ε$-approximation of the scaled $k$-th frequency moment, $F_k/N^k$, using time $O(M^{1-\frac{1}{k-1}} T)$ and $O(M^{1-\frac{1}{k-1}} \log N \log (δ^{-1})/ε^2)$ bits of transmission per communication step. Here, $N$ is the number of nodes in the network, $T$ is the information spreading time and $M=o(N)$ is the alphabet size.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Streaming algorithms for recognizing nearly well-parenthesized expressions

We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x' in 1-turn-Dyck2 such that x is obtained by flipping at most $k$ locations of x' using: - O(k log n) space, O(k log n) randomness, and poly(k log n) time per item and with error at most 1/poly(n). - O(k^{1+epsilon} + log n) space for every 0 <= epsilon <= 1, O(log n) randomness, O(polylog(n) + poly(k)) time per item, with error at most 1/8. Here, we also prove that any randomized one-pass algorithm that makes error at most k/n requires at least Omega(k log(n/k)) space to accept strings which are exactly k-away from strings in 1-turn-Dyck2 and to reject strings which are exactly (k+2)-away from strings in 1-turn-Dyck2. Since 1-turn-Dyck2 and the Hamming Distance problem are closely related we also obtain new upper and lower bounds for this problem. Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x' in Dyck2 such that x is obtained from x' by changing (in some restricted manner) at most k positions using: - O(k log n + sqrt(n log n)) space, O(k log n) randomness, poly(k log n) time per element and with error at most 1/poly(n). - O(k^(1+epsilon)+ sqrt(n log n)) space for every 0 <= epsilon <= 1, O(log n) randomness, O(polylog(n) + poly(k)) time per element, with error at most 1/8.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Streaming algorithms for language recognition problems

We study the complexity of the following problems in the streaming model. Membership testing for \DLIN We show that every language in \DLIN\ can be recognised by a randomized one-pass $O(\log n)$ space algorithm with inverse polynomial one-sided error, and by a deterministic p-pass $O(n/p)$ space algorithm. We show that these algorithms are optimal. Membership testing for \LL$(k)$ For languages generated by \LL$(k)$ grammars with a bound of $r$ on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass $O(r\log n)$ space algorithm with inverse polynomial (in $n$) one-sided error. Membership testing for \DCFL We show that randomized algorithms as efficient as the ones described above for \DLIN\ and $\LL(k)$ (which are subclasses of \DCFL) cannot exist for all of \DCFL: there is a language in \VPL\ (a subclass of \DCFL) for which any randomized p-pass algorithm with error bounded by $ε< 1/2$ must use $Ω(n/p)$ space. Degree sequence problem We study the problem of determining, given a sequence $d_1, d_2,..., d_n$ and a graph $G$, whether the degree sequence of $G$ is precisely $d_1, d_2,..., d_n$. We give a randomized one-pass $O(\log n)$ space algorithm with inverse polynomial one-sided error probability. We show that our algorithms are optimal. Our randomized algorithms are based on the recent work of Magniez et al. \cite{MMN09}; our lower bounds are obtained by considering related communication complexity problems.

0 citations0 reviewsNo code linkedOpen access