اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHow to Integrate a Polynomial over a Simplex
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This paper settles the computational complexity of the problem of integrating a polynomial function f over a rational simplex. We prove that the problem is NP-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We conclude the article with extensions to other polytopes, discussion of other available methods and experimental results.
قيم البحث
اقرأ أيضاً
Recently, it was found that a new set of simple techniques allow one to conveniently express ordinary integrals through differentiation. These techniques add to the general toolbox for integration and integral transforms such as the Fourier and Lapla
ce transforms. The new methods also yield new perturbative expansions when the integrals cannot be solved analytically. Here, we add new results, for example, on expressing the Laplace transform and its inverse in terms of derivatives. The new methods can be used to express path integrals in terms of functional differentiation, and they also suggest new perturbative expansions in quantum field theory.
In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Un
ique Games, then she chooses an epsilon-fraction of all edges, and finally replaces (corrupts) the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon) satisfiable instance, so then the problem is as hard as in the worst case. In our semi-random model, one of the steps is random, and all other steps are adversarial. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semi-random instances of Unique Games. We present an algorithm that with high probability finds a solution satisfying a (1-delta) fraction of all constraints in semi-random instances (we require that the average degree of the graph is Omega(log k). To this end, we consider a new non-standard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest. Our result holds only for epsilon less than some absolute constant. We prove that if epsilon > 1/2, then the problem is hard in one of the models, the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that with high probability, distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1-delta) satisfiable instance if epsilon > c delta.
To every finite metric space $X$, including all connected unweighted graphs with the minimum edge-distance metric, we attach an invariant that we call its blowup-polynomial $p_X({ n_x : x in X })$. This is obtained from the blowup $X[{bf n}]$ - which
contains $n_x$ copies of each point $x$ - by computing the determinant of the distance matrix of $X[{bf n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X({bf n})$ is a polynomial, is multi-affine, and is real-stable. This naturally associates a delta-matroid to each metric space $X$ (and another delta-matroid to every tree), which also seem to be hitherto unexplored. We moreover show that the homogenization at $-1$ of $p_X({bf n})$ is Lorentzian (or strongly/completely log-concave), if and only if the normalization of $p_X(-{bf n})$ is strongly Rayleigh, if and only if a modification of the distance matrix of $X$ is positive semidefinite. We next specialize to the case of $X = G$ a connected unweighted graph - so $p_G$ is partially symmetric in ${ n_v : v in V(G) }$ - and show two further results: (a) We show that the univariate specialization $u_G(x) := p_G(x,dots,x)$ is a transform of the characteristic polynomial of the distance matrix $D_G$; this connects the blowup-polynomial of $G$ to the well-studied distance spectrum of $G$. (b) We show that the polynomial $p_G$ is indeed a graph invariant, in that $p_G$ and its symmetries recover the graph $G$ and its isometries, respectively.
In this paper, we present a new methodology to evaluate whether a business process model is fully compliant with a regulatory framework composed of a set of conditional obligations. The methodology is based failure delta-constraints that are evaluate
d on bottom-up aggregations of a tree-like representation of business process models. While the generic problem of proving full compliance is in coNP-complete, we show that verifying full compliance can be done in polynomial time using our methodology, for an acyclic structured process model given a regulatory framework composed by a set of conditional obligations, whose elements are restricted to be represented by propositional literals
In this paper, we examine how far a polynomial in $mathbb{F}_2[x]$ can be from a squarefree polynomial. For any $epsilon>0$, we prove that for any polynomial $f(x)inmathbb{F}_2[x]$ with degree $n$, there exists a squarefree polynomial $g(x)inmathbb{F
}_2[x]$ such that $mathrm{deg} (g) le n$ and $L_{2}(f-g)<(ln n)^{2ln(2)+epsilon}$ (where $L_{2}$ is a norm to be defined). As a consequence, the analogous result holds for polynomials $f(x)$ and $g(x)$ in $mathbb{Z}[x]$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
