BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Kashyap Dixit

Kashyap Dixit contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational ComplexityCryptography and Securitymath.CO

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 published item(s)

preprint2016arXiv

Erasure-Resilient Property Testing

Property testers form an important class of sublinear algorithms. In the standard property testing model, an algorithm accesses the input function via an oracle that returns function values at all queried domain points. In many realistic situations, the oracle may be unable to reveal the function values at some domain points due to privacy concerns, or when some of the values get erased by mistake or by an adversary. We initiate a study of property testers that are resilient to the presence of adversarially erased function values. An alpha-erasure-resilient epsilon-tester for a property P is given parameters alpha, epsilon in (0,1), along with oracle access to a function f such that at most an alpha fraction of the function values have been erased. The tester does not know whether a point is erased unless it queries that point. The tester has to accept with high probability if there is a way to assign values to the erased points such that the resulting function satisfies P. It has to reject with high probability if, for all assignments of values to the erased points, the resulting function has to be changed in at least an epsilon-fraction of the nonerased domain points to satisfy P. We design erasure-resilient property testers for a large class of properties. For some properties, it is possible to obtain erasure-resilient testers by using standard testers as a black box. But there are more challenging properties for which all known testers rely on querying a specific point. If this point is erased, all these testers break. We give efficient erasure-resilient testers for several classes of such properties including monotonicity, the Lipschitz property, and convexity. Finally, we describe a property that can be epsilon-tested with O(1/epsilon) queries in the standard model, whereas testing it in the erasure-resilient model requires number of queries polynomial in the input size.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Counting cliques and clique covers in random graphs

We study the problem of counting the number of {\em isomorphic} copies of a given {\em template} graph, say $H$, in the input {\em base} graph, say $G$. In general, it is believed that polynomial time algorithms that solve this problem exactly are unlikely to exist. So, a lot of work has gone into designing efficient {\em approximation schemes}, especially, when $H$ is a perfect matching. In this work, we present efficient approximation schemes to count $k$-Cliques, $k$-Independent sets and $k$-Clique covers in random graphs. We present {\em fully polynomial time randomized approximation schemes} (fpras) to count $k$-Cliques and $k$-Independent sets in a random graph on $n$ vertices when $k$ is at most $(1+o(1))\log n$, and $k$-Clique covers when $k$ is a constant. [Grimmett and McDiarmid, 1975] present a simple greedy algorithm that {\em detects} a clique (independent set) of size $(1+o(1))\log_2 n$ in $G\in \mathcal{G}(n,\frac{1}{2})$ with high probability. No algorithm is known to detect a clique or an independent set of larger size with non-vanishing probability. Furthermore, [Coja-Oghlan and Efthymiou, 2011] present some evidence that one cannot hope to easily improve a similar, almost 40 years old bound for sparse random graphs. Therefore, our results are unlikely to be easily improved. We use a novel approach to obtain a recurrence corresponding to the variance of each estimator. Then we upper bound the variance using the corresponding recurrence. This leads us to obtain a polynomial upper bound on the critical ratio. As an aside, we also obtain an alternate derivation of the closed form expression for the $k$-th moment of a binomial random variable using our techniques. The previous derivation [Knoblauch (2008)] was based on the moment generating function of a binomial random variable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

$L_p$-Testers for Bounded Derivative Properties on Product Distributions

We consider the problem of $L_p$-testing of class of bounded derivative properties over hypergrid domain with points distributed according to some product distribution. This class includes monotonicity, the Lipschitz property, $(α,β)$-generalized Lipschitz and many more properties. Previous results for $L_p$ testing on $[n]^d$ for this class were known for monotonicity and $c$-Lipschitz properties over uniformly distributed domains. \medskip Our results imply testers that give the same upper bound for arbitrary product distributions as the hitherto known testers, which use uniformly randomly chosen samples from $[n]^d$, for monotonicity and Lipschitz testing. Also, our testers are \emph{optimal} for a large class of bounded derivative properties, that includes $(α, β)$-generalized Lipschitz property, over uniform distributions. Infact, each edge in $[n]^d$ is allowed to have it's own left and right Lipschitz constants. The time complexity is \emph{same} for arbitrary product distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. This restriction to uniformity is more a matter of convenience than of necessity, and it is important to investigate distances induced by more general distributions. In this paper, we make significant strides in this direction. We give simple and optimal testers for {\em bounded derivative properties} over {\em arbitrary product distributions}. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A fundamental technical contribution of this work is an {\em optimal dimension reduction theorem} for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity for the past 15 years, and our theorem is an exponential improvement to the previous best known result.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Testing Lipschitz Property over Product Distribution and its Applications to Statistical Data Privacy

In this work, we present a connection between Lipschitz property testing and a relaxed notion of differential privacy, where we assume that the datasets are being sampled from a domain according to some distribution defined on it. Specifically, we show that testing whether an algorithm is private can be reduced to testing Lipschitz property in the distributional setting. We also initiate the study of distribution Lipschitz testing. We present an efficient Lipschitz tester for the hypercube domain when the "distance to property" is measured with respect to product distribution. Most previous works in property testing of functions (including prior works on Lipschitz testing) work with uniform distribution.

0 citations0 reviewsNo code linkedOpen access