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

Sanjay Jain

Sanjay Jain contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
nlin.AOComputational ComplexityMolecular NetworksBiological PhysicsComputation and Languagecond-matData Structures and AlgorithmsDigital Librarieshep-phhep-thphysics.hist-phPopulations and EvolutionQuantitative Methods

Trust snapshot

Quick read

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

8 published item(s)

preprint2022arXiv

A Computation Model with Automatic Functions and Relations as Primitive Operations

Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural than single updates of a Turing tape. One finding was that in the numerical setting, addition, subtraction, comparisons and bit-wise Boolean operations of numbers preserve polynomial time while incorporating concatenation or multiplication allows to solve all PSPACE problems in polynomially many steps. Therefore we propose to use updates and comparisons with automatic functions as primitive operations and use constantly many registers; the resulting model covers all primitive operations of Hartmanis and Simon as well as Floyd and Knuth, but the model remains in polynomial time. The present work investigates in particular the deterministic complexity of various natural problems and also gives an overview on the nondeterministic complexity of this model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Alternating Automatic Register Machines

This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional register machine and an alternating Turing machine, but can carry out computations using bounded automatic relations in a single step. One finding is that an AARM can recognise some NP-complete problems, including SAT (using a particular coding), in $\log^* n + O(1)$ steps. On the other hand, if all problems in P can be solved by an AARM in $O(\log^*n)$ rounds, then $\text{P} \subset \text{PSPACE}$. Furthermore, we study an even more computationally powerful machine, called a Polynomial-Size Padded Alternating Automatic Register Machine (PAARM), which allows the input to be padded with a polynomial-size string. It is shown that the polynomial hierarchy can be characterised as the languages that are recognised by a PAARM in $\log^*n + O(1)$ steps. These results illustrate the power of alternation when combined with computations involving automatic relations, and uncover a finer gradation between known complexity classes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Faster Exact Algorithm to Count X3SAT Solutions

The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assigned to be 1 and the other literals in the same clause are set to 0. If we restrict the length of each clause to be at most 3 literals, then it is known as the X3SAT problem. In this paper, we consider the problem of counting the number of satisfying assignments to the X3SAT problem, which is also known as #X3SAT. The current state of the art exact algorithm to solve #X3SAT is given by Dahllöf, Jonsson and Beigel and runs in $O(1.1487^n)$, where $n$ is the number of variables in the formula. In this paper, we propose an exact algorithm for the #X3SAT problem that runs in $O(1.1120^n)$ with very few branching cases to consider, by using a result from Monien and Preis to give us a bisection width for graphs with at most degree 3.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Construction and Usage of a Human Body Common Coordinate Framework Comprising Clinical, Semantic, and Spatial Ontologies

The National Institutes of Health's (NIH) Human Biomolecular Atlas Program (HuBMAP) aims to create a comprehensive high-resolution atlas of all the cells in the healthy human body. Multiple laboratories across the United States are collecting tissue specimens from different organs of donors who vary in sex, age, and body size. Integrating and harmonizing the data derived from these samples and 'mapping' them into a common three-dimensional (3D) space is a major challenge. The key to making this possible is a 'Common Coordinate Framework' (CCF), which provides a semantically annotated, 3D reference system for the entire body. The CCF enables contributors to HuBMAP to 'register' specimens and datasets within a common spatial reference system, and it supports a standardized way to query and 'explore' data in a spatially and semantically explicit manner. [...] This paper describes the construction and usage of a CCF for the human body and its reference implementation in HuBMAP. The CCF consists of (1) a CCF Clinical Ontology, which provides metadata about the specimen and donor (the 'who'); (2) a CCF Semantic Ontology, which describes 'what' part of the body a sample came from and details anatomical structures, cell types, and biomarkers (ASCT+B); and (3) a CCF Spatial Ontology, which indicates 'where' a tissue sample is located in a 3D coordinate system. An initial version of all three CCF ontologies has been implemented for the first HuBMAP Portal release. It was successfully used by Tissue Mapping Centers to semantically annotate and spatially register 48 kidney and spleen tissue blocks. The blocks can be queried and explored in their clinical, semantic, and spatial context via the CCF user interface in the HuBMAP Portal.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The origin of large molecules in primordial autocatalytic reaction networks

Large molecules such as proteins and nucleic acids are crucial for life, yet their primordial origin remains a major puzzle. The production of large molecules, as we know it today, requires good catalysts, and the only good catalysts we know that can accomplish this task consist of large molecules. Thus the origin of large molecules is a chicken and egg problem in chemistry. Here we present a mechanism, based on autocatalytic sets (ACSs), that is a possible solution to this problem. We discuss a mathematical model describing the population dynamics of molecules in a stylized but prebiotically plausible chemistry. Large molecules can be produced in this chemistry by the coalescing of smaller ones, with the smallest molecules, the `food set', being buffered. Some of the reactions can be catalyzed by molecules within the chemistry with varying catalytic strengths. Normally the concentrations of large molecules in such a scenario are very small, diminishing exponentially with their size. ACSs, if present in the catalytic network, can focus the resources of the system into a sparse set of molecules. ACSs can produce a bistability in the population dynamics and, in particular, steady states wherein the ACS molecules dominate the population. However to reach these steady states from initial conditions that contain only the food set typically requires very large catalytic strengths, growing exponentially with the size of the catalyst molecule. We present a solution to this problem by studying `nested ACSs', a structure in which a small ACS is connected to a larger one and reinforces it. We show that when the network contains a cascade of nested ACSs with the catalytic strengths of molecules increasing gradually with their size (e.g., as a power law), a sparse subset of molecules including some very large molecules can come to dominate the system.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Flows in complex biochemical networks: Role of low degree nodes

Metabolic networks have two properties that are generally regarded as unrelated: One, they have metabolic reactions whose single knockout is lethal for the organism, and two, they have correlated sets of reactions forming functional modules. In this review we argue that both essentiality and modularity seem to arise as a consequence of the same structural property: the existence of low degree metabolites. This observation allows a prediction of (a) essential metabolic reactions which are potential drug targets in pathogenic microorganisms and (b) regulatory modules within biological networks, from purely structural information about the metabolic network.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

A model for the emergence of cooperation, interdependence and structure in evolving networks

Evolution produces complex and structured networks of interacting components in chemical, biological, and social systems. We describe a simple mathematical model for the evolution of an idealized chemical system to study how a network of cooperative molecular species arises and evolves to become more complex and structured. The network is modeled by a directed weighted graph whose positive and negative links represent `catalytic' and `inhibitory' interactions among the molecular species, and which evolves as the least populated species (typically those that go extinct) are replaced by new ones. A small autocatalytic set (ACS), appearing by chance, provides the seed for the spontaneous growth of connectivity and cooperation in the graph. A highly structured chemical organization arises inevitably as the ACS enlarges and percolates through the network in a short, analytically determined time scale. This self-organization does not require the presence of self-replicating species. The network also exhibits catastrophes over long time scales triggered by the chance elimination of `keystone' species, followed by recoveries.

0 citations0 reviewsNo code linkedOpen access