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

Sanjukta Roy

Sanjukta Roy contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryArtificial IntelligenceData Structures and Algorithmsphysics.atom-phComputational ComplexityComputational Geometrycond-mat.stat-mechMultiagent Systems

Trust snapshot

Quick read

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

6 published item(s)

preprint2024arXiv

Gerrymandering Planar Graphs

We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a weighted graph into $k$ connected components (districts) such that its candidate (party) wins as many districts as possible. Prior work has principally concerned the special cases where the graph is a path or a tree. Our focus concerns the realistic case where the graph is planar. We prove that the gerrymandering problem is solvable in polynomial time in $λ$-outerplanar graphs, when the number of candidates and $λ$ are constants and the vertex weights (voting weights) are polynomially bounded. In contrast, the problem is NP-complete in general planar graphs even with just two candidates. This motivates the study of approximation algorithms for gerrymandering planar graphs. However, when the number of candidates is large, we prove it is hard to distinguish between instances where the gerrymanderer cannot win a single district and instances where the gerrymanderer can win at least one district. This immediately implies that the redistricting problem is inapproximable in polynomial time in planar graphs, unless P=NP. This conclusion appears terminal for the design of good approximation algorithms -- but it is not. The inapproximability bound can be circumvented as it only applies when the maximum number of districts the gerrymanderer can win is extremely small, say one. Indeed, for a fixed number of candidates, our main result is that there is a constant factor approximation algorithm for redistricting unweighted planar graphs, provided the optimal value is a large enough constant.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

We investigate the Euclidean $d$-Dimensional Stable Roommates problem, which asks whether a given set~$V$ of $d \cdot n$ points from the 2-dimensional Euclidean space can be partitioned into $n$ disjoint (unordered) subsets $Π=\{V_1,\ldots,V_{n}\}$ with $|V_i|=d$ for each $V_i\in Π$ such that $Π$ is stable. Here, stability means that no point subset $W\subseteq V$ is blocking $Π$ and $W$ is said to be blocking $Π$ if $|W|= d$ such that $\sum_{w&#39;\in W}δ(w,w&#39;) < \sum_{v\in Π(w)}δ(w,v)$ holds for each point $w\in W$, where $Π(w)$ denotes the subset $V_i\in Π$ which contains $w$ and $δ(a,b)$ denotes the Euclidean distance between points $a$ and $b$. Complementing the existing known polynomial-time result for $d=2$, we show that such polynomial-time algorithms cannot exist for any fixed number $d \ge 3$ unless P=NP. Our result for $d=3$ answers a decade-long open question in the theory of Stable Matching and Hedonic Games [17, 1, 9, 25, 20].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule

Answering an open question by Betzler et al. [Betzler et al., JAIR&#39;13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR&#39;83] and the Monroe rule [Monroe, APSR&#39;95]. We show that under both rules, the problem is W[1]-hard with respect to the sum $β$ of misrepresentations, thereby precluding the existence of any $f(β) \cdot |I|^{O(1)}$ -time algorithm, where $|I|$ denotes the size of the input instance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Transition frequency measurement of highly excited Rydberg states of 87Rb for a wide range of principal quantum numbers

We report our measurements of the absolute transition frequencies of 5P_3/2,F = 3 to nS and nD Rydberg states of 87Rb with high principal quantum numbers in a wide range of values (n = 45-124). The measurements were performed using Rydberg Electromagnetically Induced Transparency (EIT) in ladder-type three-level systems. We measure the transition frequencies with an accuracy of less than 2 MHz. We determine the values of the Rydberg-Ritz parameter for 87Rb from our experimental measurements of the transition frequencies. Our measurements of the absolute transition frequencies of the highly excited Rydberg states would be useful for diverse applications in quantum information processing, quantum simulation and quantum sensing with Rydberg atoms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Measurements and analysis of response function of cold atoms in optical molasses

We report our experimental measurements and theoretical analysis of the position response function of a cloud of cold atoms residing in the viscous medium of an optical molasses and confined by a magneto-optical trap (MOT). We measure the position response function by applying a transient homogeneous magnetic field as a perturbing force. We observe a transition from a damped oscillatory motion to an over-damped relaxation, stemming from a competition between the viscous drag provided by the optical molasses and the restoring force of the MOT. Our observations are in both qualitative and quantitative agreement with the predictions of a theoretical model based on the Langevin equation. As a consistency check, and as a prototype for future experiments, we also study the free diffusive spreading of the atomic cloud in our optical molasses with the confining magnetic field of the MOT turned off. We find that the measured value of the diffusion coefficient agrees with the value predicted by our Langevin model, using the damping coefficient. The damping coefficient was deduced from our measurements of the position response function at the same temperature.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the (Parameterized) Complexity of Almost Stable Marriage

In the Stable Marriage problem. when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the &#34;no blocking pair&#34; condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, we find a matching whose size exceeds that of stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is &#34;closest&#34;, in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.

0 citations0 reviewsNo code linkedOpen access