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

Sourav Chakraborty

Sourav Chakraborty contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Complexitycond-mat.mtrl-scicond-mat.str-elArtificial IntelligenceComputational GeometryComputer Science and Game TheoryData Structures and AlgorithmsLogic in Computer Sciencequant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
9topics
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

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