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

Sourav Chakraborty

Sourav Chakraborty 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 AlgorithmsComputational Geometrycond-mat.mtrl-scicond-mat.str-elArtificial IntelligenceComputer Science and Game TheoryLogic in Computer Sciencemath.PRmath.STquant-phStatistics Theory

Catalog footprint

What is connected

11works
12topics
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

11 published item(s)

preprint2022arXiv

Itinerant ferromagnetism in a spin-fermion model for diluted spin systems

We investigate the itinerant ferromagnetism using a diluted spin-fermion model, derived from a repulsive Hubbard model, where itinerant fermions are coupled antiferromagnetically to auxiliary fields in a three-dimensional simple cubic lattice. We focus, in particular, on understanding the spin-dependent transport properties of the itinerant fermions in the impurity band by taking positional disorder of the auxiliary fields into account. For on-site repulsion $U$ $\sim$ bandwidth the density of the itinerant carriers confined to the impurity band, play a key role in determining the kinetic energy of the system and consequently the carrier spin polarization. Our semi-classical Monte Carlo calculations show that the ferromagnetic transition temperature of the carrier spins indeed shows an optimization behavior with the carrier density. We calculate the transport properties in details to establish a one-to-one correspondence between the magnetic and transport properties of the carriers. Our results obtained beyond the perturbative regime are significant for understanding the ferromagnetism in diluted magnetic semiconductors.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On verifying expectations and observations of intelligent agents

Public observation logic (POL) is a variant of dynamic epistemic logic to reason about agent expectations and agent observations. Agents have certain expectations, regarding the situation at hand, that are actuated by the relevant protocols, and they eliminate possible worlds in which their expectations do not match with their observations. In this work, we investigate the computational complexity of the model checking problem for POL and prove its PSPACE-completeness. We also study various syntactic fragments of POL. We exemplify the applicability of POL model checking in verifying different characteristics and features of an interactive system with respect to the distinct expectations and (matching) observations of the system. Finally, we provide a discussion on the implementation of the model checking algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Property Testing of Joint Distributions using Conditional Samples

In this paper, we consider the problem of testing properties of joint distributions under the Conditional Sampling framework. In the standard sampling model, the sample complexity of testing properties of joint distributions is exponential in the dimension, resulting in inefficient algorithms for practical use. While recent results achieve efficient algorithms for product distributions with significantly smaller sample complexity, no efficient algorithm is expected when the marginals are not independent. We initialize the study of conditional sampling in the multidimensional setting. We propose a subcube conditional sampling model where the tester can condition on an (adaptively) chosen subcube of the domain. Due to its simplicity, this model is potentially implementable in many practical applications, particularly when the distribution is a joint distribution over $Σ^n$ for some set $Σ$. We present algorithms for various fundamental properties of distributions in the subcube-conditioning model and prove that the sample complexity is polynomial in the dimension $n$ (and not exponential as in the traditional model). We present an algorithm for testing identity to a known distribution using $\tilde{\mathcal{O}}(n^2)$-subcube-conditional samples, an algorithm for testing identity between two unknown distributions using $\tilde{\mathcal{O}}(n^5)$-subcube-conditional samples and an algorithm for testing identity to a product distribution using $tilde{\mathcal{O}}(n^5)$-subcube-conditional samples. The central concept of our technique involves an elegant chain rule which can be proved using basic techniques of probability theory yet powerful enough to avoid the curse of dimensionality.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Antiferromagnetism beyond classical percolation threshold in the site-diluted half-filled one-band Hubbard model in three dimensions

We investigate the impact of site dilution by setting the on-site repulsion strength ($U$) to zero at a fraction of sites in the half-filled Hubbard model on a simple cubic lattice. We employ a semi-classical Monte-Carlo approach first to recover the zero dilution (undiluted $x=1$) properties, including $U$ dependence of insulator to metal crossover temperature scale $T^*$ and long-range staggered antiferromagnetic ordering temperature ($T_N$). For the non-perturbative regime of $U \sim$ bandwidth, we find a rapid suppression of $T^*$ with reducing $x$ from 1 to 0.7. However, $T_N$ remains unchanged in this dilution range, showing a weakening of the insulating state but not of the magnetic order. At $x \leq 0.7$, $T^*$ and $T_N$ coincide and are suppressed together with further increase in site-dilution. Finally, the system loses the magnetic order and the insulating state for $x=0.15$, significantly below the classical percolation threshold $x_p^{sc} (\sim 0.31$). We show that the induced moments on $U=0$ sites drive the magnetic order below the classical percolation limit by studying local moment systematics and finite-size analysis of magnetic order. At the end, we show that either increasing $U$ to large values or raising temperature beyond a $U$ dependent critical value, suppresses the induced local moments of the $U=0$ sites and recovers the classical percolation threshold.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $Θ(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik-Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. In this paper, we construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $\widetildeΘ\left(d\log \left( n/d \right)\right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Θ\left( d\log \left( n/d \right) \right)$, and this is tight among all set systems of VC dimension $d$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Testing Uniformity of Stationary Distribution

A random walk on a directed graph gives a Markov chain on the vertices of the graph. An important question that arises often in the context of Markov chain is whether the uniform distribution on the vertices of the graph is a stationary distribution of the Markov chain. Stationary distribution of a Markov chain is a global property of the graph. In this paper, we prove that for a regular directed graph whether the uniform distribution on the vertices of the graph is a stationary distribution, depends on a local property of the graph, namely if (u,v) is an directed edge then outdegree(u) is equal to indegree(v). This result also has an application to the problem of testing whether a given distribution is uniform or "far" from being uniform. This is a well studied problem in property testing and statistics. If the distribution is the stationary distribution of the lazy random walk on a directed graph and the graph is given as an input, then how many bits of the input graph do one need to query in order to decide whether the distribution is uniform or "far" from it? This is a problem of graph property testing and we consider this problem in the orientation model (introduced by Halevy et al.). We reduce this problem to test (in the orientation model) whether a directed graph is Eulerian. And using result of Fischer et al. on query complexity of testing (in the orientation model) whether a graph is Eulerian, we obtain bounds on the query complexity for testing whether the stationary distribution is uniform.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Power of Conditional Samples in Distribution Testing

In this paper we define and examine the power of the {\em conditional-sampling} oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $μ$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $μ$, conditioned on $S$ (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals $[n]$. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample-complexity remains near-maximal even with conditional sampling.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Counting Popular Matchings in House Allocation Problems

We study the problem of counting the number of popular matchings in a given instance. A popular matching instance consists of agents A and houses H, where each agent ranks a subset of houses according to their preferences. A matching is an assignment of agents to houses. A matching M is more popular than matching M' if the number of agents that prefer M to M' is more than the number of people that prefer M' to M. A matching M is called popular if there exists no matching more popular than M. McDermid and Irving gave a poly-time algorithm for counting the number of popular matchings when the preference lists are strictly ordered. We first consider the case of ties in preference lists. Nasre proved that the problem of counting the number of popular matching is #P-hard when there are ties. We give an FPRAS for this problem. We then consider the popular matching problem where preference lists are strictly ordered but each house has a capacity associated with it. We give a switching graph characterization of popular matchings in this case. Such characterizations were studied earlier for the case of strictly ordered preference lists (McDermid and Irving) and for preference lists with ties (Nasre). We use our characterization to prove that counting popular matchings in capacitated case is #P-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Helly-Type Theorems in Property Testing

Helly's theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If $S$ is a set of $n$ points in $R^d$, we say that $S$ is $(k,G)$-clusterable if it can be partitioned into $k$ clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object $G$. In this paper, as an application of Helly's theorem, by taking a constant size sample from $S$, we present a testing algorithm for $(k,G)$-clustering, i.e., to distinguish between two cases: when $S$ is $(k,G)$-clusterable, and when it is $ε$-far from being $(k,G)$-clusterable. A set $S$ is $ε$-far $(0<ε\leq1)$ from being $(k,G)$-clusterable if at least $εn$ points need to be removed from $S$ to make it $(k,G)$-clusterable. We solve this problem for $k=1$ and when $G$ is a symmetric convex object. For $k>1$, we solve a weaker version of this problem. Finally, as an application of our testing result, in clustering with outliers, we show that one can find the approximate clusters by querying a constant size sample, with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Market Equilibrium with Transaction Costs

Identical products being sold at different prices in different locations is a common phenomenon. Price differences might occur due to various reasons such as shipping costs, trade restrictions and price discrimination. To model such scenarios, we supplement the classical Fisher model of a market by introducing {\em transaction costs}. For every buyer $i$ and every good $j$, there is a transaction cost of $\cij$; if the price of good $j$ is $p_j$, then the cost to the buyer $i$ {\em per unit} of $j$ is $p_j + \cij$. This allows the same good to be sold at different (effective) prices to different buyers. We provide a combinatorial algorithm that computes $ε$-approximate equilibrium prices and allocations in $O\left(\frac{1}ε(n+\log{m})mn\log(B/ε)\right)$ operations - where $m$ is the number goods, $n$ is the number of buyers and $B$ is the sum of the budgets of all the buyers.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

New Results on Quantum Property Testing

We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $\PP_f(j)$ of an outcome $j\in[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $ε$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $\sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $\sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.

0 citations0 reviewsNo code linkedOpen access