Search

The units forms are algebraic expressions that have important role in representation theory of algebras. We identified that existing algorithms have exponential time complexity for weakly nonnegative and weakly positive types. In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The related algorithm identifies hypercritical restrictions in a given unit form, testing every subgraph of 9 vertices of the unit form associated graph. By adding Depth First Search approach, a similar strategy could be used in the recognition of weakly positive unit forms. We also present the most popular methods to decide whether or not a unit form is weakly nonnegative or weakly positive, we analyze their time complexity and we compare the results with our algorithms.

Cryptographic designs are vulnerable to side-channel analysis attacks. Evaluating their security during design stages is of crucial importance. The latter is achieved by very expensive (slow) analog transient-noise simulations over advanced fabrication process technologies. The main challenge of such rigorous security-evaluation analysis lies in the fact that technologies are becoming more and more complex and the physical properties of manufactured devices vary significantly due to process variations. In turn, a detailed security evaluation process imposes exponential time complexity with the circuit-size, the number of physical implementation corners (statistical variations) and the accuracy of the circuit-simulator. Given these circumstances, what is the cost of not exhausting the entire implementation space? In terms of simulation-time complexity, the benefits would clearly be significant, however, we are interested in evaluating the security implications. This question can be formulated for many other interesting side-channel contexts such as for example, how would an attack-outcome vary when the adversary is building a leakage template over one device, i.e., one physical corner, and it performs an evaluation (attack) phase of a device drawn from a different statistical corner? Alternatively, is it safe to assume that a typical (average) corner would represent the worst case in terms of security evaluation or would it be advisable to perform a security evaluation over another specific view? Finally, how would the outcome vary concretely? We ran in-depth experiments to answer these questions in the hope of finding a nice tradeoff between simulation efforts and expertise, and security-evaluation degradation. We evaluate the results utilizing methodologies such as template-attacks with a clear distinction between profiling and attack-phase statistical views. This exemplary view of what an adversary might capture in these scenarios is followed by a more complete statistical evaluation analysis utilizing tools such as the Kullback&ndash, Leibler (KL) divergence and the Jensen-Shannon (JS) divergence to draw conclusions.

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. All previous algorithms solving this problem have doubly exponential complexity (and this is so for almost all input data). Our algorithm thus represents an exponential acceleration over state-of-the-art algorithms for all input data outside a set that vanishes exponentially fast., 43 pages

In rule-based classifiers, calculating all possible rules of a learning sample consumes many resources due to its exponential complexity. Therefore, finding ways to reduce the number and length of the rules without affecting the efficacy of a classifier remains an interesting problem. Reducts from rough set theory have been used to build rule-based classifiers by their conciseness and understanding. However, the accuracy of the classifiers based on these rules depends on the selected rule subset. In this work, we focus on analyzing three different options for using reducts for building decision rules for rule-based classifiers .

Converting a Boolean mask to an arithmetic mask, and vice versa, is often required in implementing side-channel-resistant instances of cryptographic algorithms that mix Boolean and arithmetic operations. In this paper, we describe a method for converting a Boolean mask to an arithmetic mask that runs in constant time for a fixed order and has quadratic complexity as the security order increases, a significant improvement in previous work that has exponential complexity. We propose explicit algorithms for a second-order secure Boolean-to-arithmetic mask conversion that uses 31 instructions and for a third-order secure mask conversion that uses 74 instructions. We show that our second-order secure algorithm is at least an order of magnitude faster and our third-order secure algorithm is more than twice as fast as other algorithms in the literature.

In this paper, we introduce topological entropy (TE) based on time series, which characterizes the total exponential complexity of a quantified system with a single number. Combined with multiscale theory, we propose geometric entropy (GE), aiming to examine the correlation among different time series. In order to detect the properties of TE and GE, we apply them to an original symbolic method utilized to measure time series irreversibility, namely horizontal visibility algorithm. On this basis, we propose a time series irreversibility measure, i.e., normalized index. Then, we employ TE and GE based on the horizontal visibility graph symbolic algorithm to simulated time series, which is generated by the logistic map with different parameters. Through the comparison of the results, we find out that different simulated data have the same variation tendency of TE, which means that TE is capable of reflecting the similarity among different time series. On the basic of these results, we further analyze the irreversibility of simulated data and also get some interesting findings. From the GE results comparison, we conclude that the GE method can distinguish different time series and expose their correlation efficiently. As a farther validation, we explore the effects of these methods on the analysis of different stock time series. Results show that they can reflect a large number of interrelationships, and successfully quantify the changes in the complexity of different stock market data.

The main goal of the paper was to develop algorithms and methods for computation of basic sums, the mathematical objects of great importance in computational materials science having applications to description of the representative volume element (RVE) and to the effective properties of 2D composites. The previously used algorithm had the exponential complexity. We propose a linearly complex algorithm. All the presented algorithms can be easily implemented in modern scientific computing packages, while maintaining both efficient calculations and a high level of abstraction. The proposed approach is applied to derivation of a polynomial approximation of the effective conductivity formula for 2D random material with non-overlapping circular inclusions with normally distributed radii. The obtained formulas are applied to the optimal packing problem of disks on the plane.

Proceedings of the VLDB Endowment 12(11), 1526-1538 (2019). doi:10.14778/3342263.3342631, Published by Assoc. of Computing Machinery, [New York, NY]

Many graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy for such problems, classifying which target graphs render the problem polynomial-time solvable or \(\#\mathrm {P}\)-hard. In this paper, we give a new and shorter proof of this theorem, with previously unknown tight lower bounds under the exponential-time hypothesis. We similarly strengthen complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs. Both results crucially rely on our main contribution, a complexity dichotomy for evaluating linear combinations of homomorphism numbers to fixed graphs. In the terminology of Lovasz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.

We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show under some polynomial-time reductions that there are complete sets for NEXP that are not autoreducible. We obtain the following main results: —For any positive integers s and k such that 2 s − 1 > k , there is a ≤ s-T p -complete set for NEXP that is not ≤ k-tt p -autoreducible. —For every constant c > 1, there is a ≤ 2-T p -complete set for NEXP that is not autoreducible under nonadaptive reductions that make no more than three queries, such that each of them has a length between n 1/c and n c , where n is input size. —For any positive integer k , there is a ≤ k-tt p -complete set for NEXP that is not autoreducible under ≤ k-tt p -reductions whose truth table is not a disjunction or a negated disjunction. Finally, we show that settling the question of whether every ≤ dtt p -complete set for NEXP is ≤ NOR-tt p -autoreducible either positively or negatively would lead to major results about the exponential time complexity classes.

We study the exponential time complexity of approximate counting satisfying assignments of CNFs. We reduce the problem to deciding satisfiability of a CNF. Our reduction preserves the number of variables of the input formula and thus also preserves the exponential complexity of approximate counting. Our algorithm is also similar to an algorithm which works particular well in practice for which however no approximation guarantee was known. Towards an analysis of our reduction we provide a new inequality similar to the Bonami-Beckner hypercontractive inequality.

We prove an effective integrability criterion for differential-algebraic Pfaffian systems leading to a decision method of consistency with a triple exponential complexity bound. As a byproduct, we obtain an upper bound for the order of differentiations in the differential Nullstellensatz for these systems. Fil: D'Alfonso, Lisi. Universidad de Buenos Aires. Ciclo Básico Común; Argentina Fil: Jeronimo, Gabriela Tali. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Solernó, Pablo Luis. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina

Part 2: Track B: Logic, Semantics, Specification and Verification; International audience; In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.

Consider uniprocessor platforms, the scheduling of synchronous implicit deadline periodic task sets and the dual priority scheme where each task is assigned two fixed priorities. That is, at run time each task starts executing using its primary priority and is promoted if not completed at an intermediate deadline. We present counter-intuitive examples illustrating how difficult this scheduling problem is. We propose a preprocessing approach to remove from the scheduling problem lowest priority viable tasks as defined by Audsley's procedure. We revisit one solution called RM + RM conjectured optimal. We propose a procedure to compute promotion deadlines based on multiple simulations over an hyperperiod called FDMS. That solution has an exponential time complexity but an experimental success ratio of 100%. Then we propose a new sub-optimal solution to assign priorities called 1 /RM + RM along with a very simple promotion deadline assignment scheme called RML for which no simulation are required, the procedure is simple and the success ratio is close to 99.99%. We show that the method is fast and scalable to very large task sets which makes it ideal for practical applications., info:eu-repo/semantics/published

We show that, by an appropriate choice of auxiliary fields and exact integration of the phonon degrees of freedom, it is possible to define a 'sign-free' path integral for the so called Hubbard-Holstein model at half-filling. We use a statistical method, based on an accelerated and efficient Langevin dynamics, for evaluating all relevant correlation functions of the model. Preliminary calculations at $U/t=4$ and $U/t=1$, for $\omega_0/t=1$, indicate a quite extended region around $U \simeq {g^2 \over \omega_0}$ without either antiferromagnetic or charge-density-wave orders, separating two quantum critical points at zero temperature. The elimination of the sign problem in a model without explicit particle-hole symmetry may open new perspectives for strongly correlated models, even away from the purely attractive or particle-hole symmetric cases., Comment: 5 pages, 2 figures

We introduce and compare three different Monte Carlo determinantal algorithms that allow one to compute dynamical quantities, such as the self-energy, of fermionic systems in their thermodynamic limit. We show that the most efficient approach expresses the sum of a factorial number of one-particle-irreducible diagrams as a recursive sum of determinants with exponential complexity. By comparing results for the two-dimensional Hubbard model with those obtained from state-of-the-art diagrammatic Monte Carlo, we show that we can reach higher perturbation orders and greater accuracy for the same computational effort.

Local layout effects create pattern dependencies at the 16nm node and below that make prediction of functional and parametric yield increasingly challenging. For logic design, precharacterizing all possible neighboring patterns is impractical due to exponential complexity, and silicon characterization is practically impossible. In this paper we propose a virtual characterization vehicle (VCV) methodology that can exhaustively identify all unique occurring layout patterns as a function of a radius of influence. VCVs compile the pattern frequency and enable exposure of hotspot patterns created by cell abutment. The VCV results can be used to guide the design and selection of cell library patterns and composition based on the corresponding impact on DFM metrics. Our results are demonstrated on a 14nm commercial cell library and results show how DFM quality can be improved with minimal impact on performance.

Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing: the variable ordering for a CAD problem, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions., Comment: 18 pages, 8 figures, 11 puzzles. Journal version of FUN 2012 paper

International audience; Traditional algorithms to solve the problem of sorting by signed reversals output just one optional solution while the space of optimal solutions can be huge. Algorithms for enumerating the complete set of solutions traces were developed aiming to support biologists studies of alternative evolutionary scenarios. Due to the exponential complexity of the algorithms, their practical use is limited to small permutations. In this work, we propose and evaluate three di erent approaches to producing a partial enumeration of the complete set of traces to transform a given permutation to another one.

A preliminary version of this work appeared in the proceedings of Combinatorial Pattern Matching (CPM) 2009. See arXiv:0901.2847; Discrete Mathematics, Algorithms and Applications, vol. 3(3), 2011; International audience; Perfect sorting by reversals, a problem originating in computational genomics, is the process of sorting a signed permutation to either the identity or to the reversed identity permutation, by a sequence of reversals that do not break any common interval. Bérard et al. (2007) make use of strong interval trees to describe an algorithm for sorting signed permutations by reversals. Combinatorial properties of this family of trees are essential to the algorithm analysis. Here, we use the expected value of certain tree parameters to prove that the average run-time of the algorithm is at worst, polynomial, and additionally, for sufficiently long permutations, the sorting algorithm runs in polynomial time with probability one. Furthermore, our analysis of the subclass of commuting scenarios yields precise results on the average length of a reversal, and the average number of reversals. A preliminary version of this work appeared in the proceedings of Combinatorial Pattern Matching (CPM) 2009, Lectures Notes in Computer Science, vol. 5577, pp. 314--325, Springer.

In this paper, we show that special instances of parameterized NP-hard problems are as difficult as the general instances in terms of their subexponential time computability. For example, we show that the Planar Dominating Set problem on degree-3 graphs can be solved in $2^{o(\sqrt{k})} p(n)$ parameterized time if and only if the general Planar Dominating Set problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well.

International audience; Constraint Handling Rules (CHR) is a concurrent, committed- choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. We first prove its exponential complexity in time and space for non-flat equations and deduce from this proof a quadratic complexity for flat equations. We then present an extended CHR solver for solving existentially quantified conjunctions of non-flat equations in the theory of finite or infinite trees. We reach a quadratic complexity by first flattening the equations and introducing new existentially quantified variables, then using the classic solver, and finally eliminating particular equations and quantified variables.

This chapter elaborates various transformations of the set functions. Measures in a finite setting are positive-valued set functions with some characteristic properties. It is found that although the finiteness of the universe considerably restricts the interest of the measure concept, it also allows other viewpoints coming from various fields of mathematics—suchas combinatorics, game theory, and complexity—when viewing measures as particular set functions or pseudo-Boolean functions. There is a general formula for the inverse of cardinality operators. The formalism permits to compute easily, simply by combining and inversing operators, all formulas between the different representations of set functions. It is found that any set function can be decomposed on the set of unanimity games or their conjugate. The k-order additive measures or k-additive measures decrease the exponential complexity of fuzzy measures in practical applications. The ordinal interaction transform of a fuzzy measure is also elaborated in the chapter.