Episciences.org
Not a member yet
6707 research outputs found
Sort by
Framework for -Completeness of Two-Dimensional Packing Problems
No full textThe aim in packing problems is to decide if a given set of pieces can beplaced inside a given container. A packing problem is defined by the types ofpieces and containers to be handled, and the motions that are allowed to movethe pieces. The pieces must be placed so that in the resulting placement, theyare pairwise interior-disjoint. We establish a framework which enables us toshow that for many combinations of allowed pieces, containers and motions, theresulting problem is -complete. This means that the problemis equivalent (under polynomial time reductions) to deciding whether a givensystem of polynomial equations and inequalities with integer coefficients has areal solution. We consider packing problems where only translations are allowed as themotions, and problems where arbitrary rigid motions are allowed, i.e., bothtranslations and rotations. When rotations are allowed, we show that it is an-complete problem to decide if a set of convex polygons,each of which has at most corners, can be packed into a square. Restrictedto translations, we show that the following problems are -complete: (i) pieces bounded by segments and hyperbolic curves tobe packed in a square, and (ii) convex polygons to be packed in a containerbounded by segments and hyperbolic curves
Quantized collision invariants on the sphere
No full textWe show that a measurable function , with, satisfies the functional relation \begin{equation*}g(\omega)+g(\omega_*)=g(\omega')+g(\omega_*'), \end{equation*} for alladmissible in the sensethat \begin{equation*} \omega+\omega_*=\omega'+\omega_*', \end{equation*} ifand only if it can be written as \begin{equation*} g(\omega)=A+B\cdot\omega,\end{equation*} for some constants and . Such functions form a family of quantized collision invariants which play afundamental role in the study of hydrodynamic regimes of theBoltzmann--Fermi--Dirac equation near Fermionic condensates, i.e., at lowtemperatures. In particular, they characterize the elastic collisional dynamicsof Fermions near a statistical equilibrium where quantum effects arepredominant
Derived -zips
No full textWe define derived versions of -zips and associate a derived -zip to anyproper, smooth morphism of schemes in positive characteristic. We analyze thestack of derived -zips and certain substacks. We make a connection to theclassical theory and look at problems that arise when trying to generalize thetheory to derived -zips and derived -zips associated to lci morphisms. Asan application, we look at Enriques-surfaces and analyze the geometry of themoduli stack of Enriques-surfaces via the associated derived -zips. As thereare Enriques-surfaces in characteristic with non-degenerate Hodge-de Rhamspectral sequence, this gives a new approach, which could previously not beobtained by the classical theory of -zips.Comment: 72 pages. Final versio
On some dynamical features of the complete Moran model for neutral evolution in the presence of mutations
No full textWe present a version of the classical Moran model, in which mutations aretaken into account; the possibility of mutations was introduced by Moran in hisseminal paper, but it is more often overlooked in discussing the Moran model.For this model, fixation is prevented by mutation, and we have an ergodicMarkov process; the equilibrium distribution for such a process was determinedby Moran. The problems we consider in this paper are those of first hittingeither one of the ``pure'' (uniform population) states, depending on theinitial state; and that of first hitting times. The presence of mutations leadsto a nonlinear dependence of the hitting probabilities on the initial state,and to a larger mean hitting time compared to the mutation-free process (inwhich case hitting corresponds to fixation of one of the alleles).Comment: 22 pages, 8 figure
A logical limit law for -avoiding permutations
No full textWe prove that the class of 231-avoiding permutations satisfies a logicallimit law, i.e. that for any first-order sentence , in the language oftwo total orders, the probability that a uniform random231-avoiding permutation of size satisfies admits a limit as islarge. Moreover, we establish two further results about the behavior and valueof : (i) it is either bounded away from , or decaysexponentially fast; (ii) the set of possible limits is dense in . Ourtools come mainly from analytic combinatorics and singularity analysis.Comment: 15 pages; version 3 is the final version, ready for publication in DMTC
Separators in Continuous Petri Nets
No full textLeroux has proved that unreachability in Petri nets can be witnessed by aPresburger separator, i.e. if a marking cannot reach amarking , then there is a formula of Presburgerarithmetic such that: holds; is forwardinvariant, i.e., and imply); and holds. While theseseparators could be used as explanations and as formal certificates ofunreachability, this has not yet been the case due to their worst-case size,which is at least Ackermannian, and the complexity of checking that a formulais a separator, which is at least exponential (in the formula size). We show that, in continuous Petri nets, these two problems can be overcome.We introduce locally closed separators, and prove that: (a) unreachability canbe witnessed by a locally closed separator computable in polynomial time; (b)checking whether a formula is a locally closed separator is in NC (so, simplerthan unreachability, which is P-complete). We further consider the more general problem of (existential) set-to-setreachability, where two sets of markings are given as convex polytopes. We showthat, while our approach does not extend directly, we can efficiently certifyunreachability via an altered Petri net.Comment: Extension of the FoSSaCS'22 conference versio
Roots and right factors of polynomials and left eigenvalues of matrices over Cayley-Dickson algebras
No full textOver a composition algebra , a polynomial has a root if and only for some . Weexamine whether this is true for general Cayley-Dickson algebras. Theconclusion is that it is when is linear or monic quadratic, but it isfalse in general. Similar questions about the connections between and itscompanion are studied. Finally, we computethe left eigenvalues of octonion matrices
Identities among some combinatorial objects involving special values of multiple zeta functions
No full textIn the article, we establish some identities involving special values of multiple zeta functions among the counting functions of number of representations of an integer by a linear combination of figurate numbers such as triangular numbers, square numbers, pentagonal numbers, etc. More precisely, we provide our result for , and (for a fixed ), the number of representations of as a sum of -triangular numbers, as a sum of -square numbers and as a sum of -higher figurate numbers (for a fixed ), respectively. Moreover, these identities also occur when one of , and is replaced by the -colored partition functions
Towards Uniform Certification in QBF
No full textWe pioneer a new technique that allows us to prove a multitude of previouslyopen simulations in QBF proof complexity. In particular, we show that extendedQBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus,Long-Distance Q-Resolution, and Merge Resolution. These results are obtained bytaking a technique of Beyersdorff et al. (JACM 2020) that turns strategyextraction into simulation and combining it with new local strategy extractionarguments. This approach leads to simulations that are carried out mainly inpropositional logic, with minimal use of the QBF rules. Our proofs thereforeprovide a new, largely propositional interpretation of the simulated systems.We argue that these results strengthen the case for uniform certification inQBF solving, since many QBF proof systems now fall into place underneathextended QBF Frege
Infinite families of congruences modulo for -regular partitions
No full textLet denote the number of -regular partition of . Recently, some congruences modulo for -regular partition and modulo , modulo and modulo for -regular partition has been studied. In this paper, we use theta function identities and Newman results to prove some infinite families of congruences modulo for , , -regular partition and modulo for -regular partition