اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputing linear extensions for polynomial posets subject to algebraic constraints
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we consider the classical problem of computing linear extensions of a given poset which is well known to be a difficult problem. However, in our setting the elements of the poset are multivariate polynomials, and only a small admissible subset of these linear extensions, determined implicitly by the evaluation map, are of interest. This seemingly novel problem arises in the study of global dynamics of gene regulatory networks in which case the poset is a Boolean lattice. We provide an algorithm for solving this problem using linear programming for arbitrary partial orders of linear polynomials. This algorithm exploits this additional algebraic structure inherited from the polynomials to efficiently compute the admissible linear extensions. The biologically relevant problem involves multilinear polynomials and we provide a construction for embedding it into an instance of the linear problem.
قيم البحث
اقرأ أيضاً
We study minimization of a parametric family of relative entropies, termed relative $alpha$-entropies (denoted $mathscr{I}_{alpha}(P,Q)$). These arise as redundancies under mismatched compression when cumulants of compressed lengths are considered in
stead of expected compressed lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative $alpha$-entropies behave like squared Euclidean distance and satisfy the Pythagorean property. Minimization of $mathscr{I}_{alpha}(P,Q)$ over the first argument on a set of probability distributions that constitutes a linear family is studied. Such a minimization generalizes the maximum R{e}nyi or Tsallis entropy principle. The minimizing probability distribution (termed $mathscr{I}_{alpha}$-projection) for a linear family is shown to have a power-law.
Linear-Optical Passive (LOP) devices and photon counters are sufficient to implement universal quantum computation with single photons, and particular schemes have already been proposed. In this paper we discuss the link between the algebraic structu
re of LOP transformations and quantum computing. We first show how to decompose the Fock space of N optical modes in finite-dimensional subspaces that are suitable for encoding strings of qubits and invariant under LOP transformations (these subspaces are related to the spaces of irreducible unitary representations of U(N)). Next we show how to design in algorithmic fashion LOP circuits which implement any quantum circuit deterministically. We also present some simple examples, such as the circuits implementing a CNOT gate and a Bell-State Generator/Analyzer.
Motivated by generalizing Khovanovs categorification of the Jones polynomial, we study functors $F$ from thin posets $P$ to abelian categories $mathcal{A}$. Such functors $F$ produce cohomology theories $H^*(P,mathcal{A},F)$. We find that CW posets,
that is, face posets of regular CW complexes, satisfy conditions making them particularly suitable for the construction of such cohomology theories. We consider a category of tuples $(P,mathcal{A},F,c)$, where $c$ is a certain ${1,-1}$-coloring of the cover relations in $P$, and show the cohomology arising from a tuple $(P,mathcal{A},F,c)$ is functorial, and independent of the coloring $c$ up to natural isomorphism. Such a construction provides a framework for the categorification of a variety of familiar topological/combinatorial invariants: anything expressible as a rank-alternating sum over a thin poset.
Results of Koebe (1936), Schramm (1992), and Springborn (2005) yield realizations of $3$-polytopes with edges tangent to the unit sphere. Here we study the algebraic degrees of such realizations. This initiates the research on constrained realization spaces of polytopes.
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is an
alogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
