We obtain a description of the Bipartite Perfect Matching decision problem as
a multi-linear polynomial over the Reals. We show that it has full degree and
has $(1-o(1))\cdot 2^{n^2}$ monomials with non-zero coefficients. In contrast,
we show that in the dual representation (switching the roles of 0 and 1) there
are only $2^{\theta(n \log n)}$ monomials with non-zero coefficients. Our proof
relies heavily on the fact that the lattice of graphs which are
``matching-covered'' is Eulerian.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Boolean networks are a general model of interacting entities, with
applications to biological phenomena such as gene regulation. Attractors play a
central role, and the schedule of entities update is a priori unknown. This
article presents results on the computational complexity of problems related to
the existence of update schedules such that some limit-cycle lengths are
possible or not. We first prove that given a Boolean network updated in
parallel, knowing whether it has at least one limit-cycle of length $k$ is
$\text{NP}$-complete. Adding an existential quantification on the
block-sequential update schedule does not change the complexity class of the
problem, but the following alternation brings us one level above in the
polynomial hierarchy: given a Boolean network, knowing whether there exists a
block-sequential update schedule such that it has no limit-cycle of length $k$
is $\Sigma_2^\text{P}$-complete.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

Discrete modelling frameworks of Biological networks can be divided in two
distinct categories: Boolean and Multi-valued. Although Multi-valued networks
are more expressive for qualifying the regulatory behaviours modelled by more
than two values, the ability to automatically convert them to Boolean network
with an equivalent behaviour breaks down the fundamental borders between the
two approaches. Theoretically investigating the conversion process provides
relevant insights into bridging the gap between them. Basically, the conversion
aims at finding a Boolean network bisimulating a Multi-valued one. In this
article, we investigate the bisimilar conversion where the Boolean integer
coding is a parameter that can be freely modified. Based on this analysis, we
define a computational method automatically inferring a bisimilar Boolean
network from a given Multi-valued one.

more |
pdf
| html
None.

BioPapers:
Bisimilar Conversion of Multi-valued Networks to Boolean Networks. https://t.co/0pEcy1PCh5

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 12267

Unqiue Words: 2145

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 257,103 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible