اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInteger matrices that are not copositive have certificates of less than quadratic complexity
51
0
0.0
(
0
)
تأليف
Timo Hirscher
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A real symmetric n times n matrix is called copositive if the corresponding quadratic form is non-negative on the closed first orthant. If the matrix fails to be copositive there exists some non-negative certificate for which the quadratic form is negative. Due to the scaling property, we can find such certificates in every neighborhood of the origin but their properties depend on the matrix of course and are hard to describe. If it is an integer matrix however, we are guaranteed certificates of a complexity that is at most a constant times the binary encoding length of the matrix raised to the power 3/2.
قيم البحث
اقرأ أيضاً
In this paper, the construction of finite-length binary sequences whose nonlinear complexity is not less than half of the length is investigated. By characterizing the structure of the sequences, an algorithm is proposed to generate all binary sequen
ces with length $n$ and nonlinear complexity $c_{n}geq n/2$, where $n$ is an integer larger than $2$. Furthermore, a formula is established to calculate the exact number of these sequences. The distribution of nonlinear complexity for these sequences is thus completely determined.
The standard way to construct a path integral is to use a Legendre transformation to find the hamiltonian, to repeatedly insert complete sets of states into the time-evolution operator, and then to integrate over the momenta. This procedure is simple
when the action is quadratic in its time derivatives, but in most other cases Legendres transformation is intractable, and the hamiltonian is unknown. This paper shows how to construct path integrals when one cant find the hamiltonian because the first time derivatives of the fields occur in ways that make a Legendre transformation intractable; it focuses on scalar fields and does not discuss higher-derivative theories or those in which some fields lack time derivatives.
A computable structure A is x-computably categorical for some Turing degree x, if for every computable structure B isomorphic to A there is an isomorphism f:B -> A with f computable in x. A degree x is a degree of categoricity if there is a computabl
e A such that A is x-computably categorical, and for all y, if A is y-computably categorical then y computes x. We construct a Sigma_2 set whose degree is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity.
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to ex
act copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method --- which is valid only in the case of continuous uncertainty --- is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
Sela proved every torsion-free one-ended hyperbolic group is coHopfian. We prove that there exist torsion-free one-ended hyperbolic groups that are not commensurably coHopfian. In particular, we show that the fundamental group of every simple surface amalgam is not commensurably coHopfian.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
