Search

We outline recent trends in capacity-based aggregation in large universes. Capacities (fuzzy measures) model dependencies among the inputs, and aggregation by the discrete Choquet, Sugeno and other fuzzy integrals accounts for synergies and redundancies. For large number of inputs the exponential complexity of all interactions is a major obstacle. We exemplify the need for aggregation of a large number of dependent inputs on several applications and discuss the challenges and approaches to reducing the complexity of capacity-based aggregation. We also state which mathematical and computational tools are required for large scale capacity modelling.

By the Pieri rule, the tensor product of an exterior power and a finite-dimensional irreducible representation of a general linear group has a multiplicity-free decomposition. The embeddings of the constituents are called Pieri inclusions and were first studied by Weyman in his thesis and described explicitly by Olver. More recently, these maps have appeared in the work of Eisenbud, Fløystad, and Weyman and of Sam and Weyman to compute pure free resolutions for classical groups. In this paper, we give a new closed form, non-recursive description of Pieri inclusions. For partitions with a bounded number of distinct parts, the resulting algorithm has polynomial time complexity whereas the previously known algorithm has exponential time complexity.

A great many problems in network information theory, both fundamental and applied, involve determining a minimal set of inequalities linking the Shannon entropies of a certain collection of subsets of random variables. In principle this minimal set of inequalities could be determined from the entropy region, whose dimensions are all the subsets of random variables, by projecting out dimensions corresponding to the irrelevant subsets. As a general solution technique, however, this method is plagued both by the incompletely known nature of the entropy region as well as the exponential complexity of its bounds. Even worse, for four or more random variables, it is known that the set of linear information inequalities necessary to completely describe the entropy region must be uncountably infinite. A natural question arises then, if there are certain nontrivial collections of subsets where the inequalities linking only these subsets is both completely known, and have inequality descriptions that are linear in the number of random variables. This paper answers this question in the affirmative. A decomposition expressing the collection of inequalities linking a larger collection of subsets from that of smaller collections of subsets is first proven. This decomposition is then used to provide systems of subsets for which it both exhaustively determines the complete list of inequalities, which is linear in the number of variables.

The diagnosability of discrete event systems has been a topic of interest to many researchers. The diagnosability conditions for various systems have evolved based on a regularity condition that is imposed on faulty traces with respect to their observable continuations. Improving upon this weak but necessary condition, a new model of diagnosability that is based on sensor outputs, which are called observations, upon a command input is proposed in this paper. Necessary and sufficient conditions are derived for the proposed diagnosability model. The search performance of the proposed diagnosability condition is of linear complexity in terms of the power set of the system events and observations, compared to the exponential complexity of the search with the existing diagnosability regularity condition. Moreover, a system that is not diagnosable according to the existing diagnosability condition may be diagnosable in the proposed diagnosability model, which includes observations.

SummaryMission planning is a complex motion planning problem specified by using Temporal Logic constituting of Boolean and temporal operators, typically solved by model verification algorithms with an exponential complexity. The paper proposes co-evolutionary optimization thus building an iterative solution to the problem. The language for mission specification is generic enough to represent everyday missions, while specific enough to design heuristics. The mission is broken into components which cooperate with each other. The experiments confirm that the robot is able to outperform the search, evolutionary and model verification techniques. The results are demonstrated by using a Pioneer LX robot.

Latest studies have shown that Long Noncoding RNAs corresponds to a crucial factor in neurodegenerative diseases and next-generation therapeutic targets. A wide range of advanced computational methods for the analysis of Noncoding RNAs mainly includes the prediction of RNA and miRNA structures. The problems that concern representations of specific biological structures such as secondary structures are either characterized as NP-complete or with high complexity. Numerous algorithms and techniques related to the enumeration of sequential terms of biological structures and mainly with exponential complexity have been constructed until now. While BACE1-AS, NATRad18, 17A, and hnRNP Q lnRNAs have been found to be associated with Alzheimer's disease, in this research study the significance of the most known β-turn-forming residues between these proteins is computationally identified and discussed, as a potentially crucial factor on the regulation of folding, aggregation and other intermolecular interactions.

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.

Efficient robotic exploration of unknown sensor limited global-information-deficient environments poses unique challenges to path planning algorithms. In these difficult environments, no deterministic guarantees on path completion and mission success can be made in general. Integrated exploration (IE), which strives to combine localization and exploration, must be solved in order to create an autonomous robotic system capable of long-term operation in new and challenging environments. This paper formulates a probabilistic framework that allows the creation of exploration algorithms providing probabilistic guarantees of success. A novel connection is made between the Hamiltonian path problem and exploration. The guaranteed probabilistic information explorer (G-PIE) is developed for the IE problem, providing a probabilistic guarantee on path completion, and asymptotic optimality of exploration. A receding horizon probabilistic information explorer (RH-PIE) is presented, which addresses the exponential complexity present in G-PIE. Finally, RH-PIE planner is verified via autonomous hardware-in-the-loop experiments.

Rough set reducts are irreducible attribute subsets preserving discernibility information of a decision system. Computing all reducts has exponential complexity regarding the number of attributes in the decision system. Given the high computational cost of this task, computing only the reducts of minimum length (the shortest reducts) becomes relevant for a wide range of applications. Two recent algorithms have been reported, almost simultaneously, for computing these irreducible attribute subsets with minimum length: MiLIT and MinReduct. MiLIT was designed at the top of the Testor Theory while MinReduct comes from the Rough Set Theory. Thus, in this paper, we present a comparative study of these algorithms in terms of asymptotic complexity and runtime performance.

In multi-class classification tasks, like human activity recognition, it is often assumed that classes are separable. In real applications, this assumption becomes strong and generates inconsistencies. Besides, the most commonly used approach is to learn classes one-by-one against the others. This computational simplification principle introduces strong inductive biases on the learned theories. In fact, the natural connections among some classes, and not others, deserve to be taken into account. In this paper, we show that the organization of overlapping classes (multiple inheritances) into hierarchies considerably improves classification performances. This is particularly true in the case of activity recognition tasks featured in the SHL dataset. After theoretically showing the exponential complexity of possible class hierarchies, we propose an approach based on transfer affinity among the classes to determine an optimal hierarchy for the learning process. Extensive experiments show improved performances and a reduction in the number of examples needed to learn.

We argue that novel (highly nonclassical) quantum extremal surfaces play a crucial role in reconstructing the black hole interior even for isolated, single-sided, non-evaporating black holes (i.e. with no auxiliary reservoir). Specifically, any code subspace where interior outgoing modes can be excited will have a quantum extremal surface in its maximally mixed state. We argue that as a result, reconstruction of interior outgoing modes is always exponentially complex. Our construction provides evidence in favor of a strong Python's lunch proposal: that nonminimal quantum extremal surfaces are the exclusive source of exponential complexity in the holographic dictionary. We also comment on the relevance of these quantum extremal surfaces to the geometrization of state dependence in the typicality arguments for firewalls., Comment: 43 pages, 13 figures

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.

International audience; We present a new methodology for decision-making support based on belief functions thanks to a new theoretical canonical decomposition of dichotomous basic belief assignments (BBAs) that has been developed recently. This decomposition based on proportional conflict redistribution rule no 5 (PCR5) always exists and is unique. This new PCR5-based decomposition method circumvents the exponential complexity of the direct fusion of BBAs with PCR5 rule and it allows to fuse quickly many sources of evidences. The method we propose in this paper provides both a decision and an estimation of the quality of the decision made, which is appealing for decision-making support systems.

Software diagnosis is the process of locating and characterizing a defect in a failing chip. It is the cornerstone of failure analysis that consequently enables yield learning and monitoring. However, multiple-defect diagnosis is challenging due to error masking and unmasking effects, and exponential complexity of the solution search process. This paper describes a three-phase, physically-aware diagnosis methodology called MDLearnX to effectively diagnose multiple defects, and in turn, aid in accelerating the design and process development. The first phase identifies a defect that resembles traditional fault models. The second and the third phases utilize the X-fault model and machine learning to identify correct candidates. Results from a thorough fault injection and simulation experiment demonstrate that MD-LearnX returns an ideal diagnosis 2X more often than commercial diagnosis. Its effectiveness is further evidenced through a silicon experiment, where, on average, MD-LearnX returns 5.3 fewer candidates per diagnosis as compared to state-of-the-art commercial diagnosis without losing accuracy.

Multiple sequences alignment is an essential task in many bioinformatics analyses. However, it is a challenging problem due to its exponential complexity. Although many approaches have been proposed for solving the MSA problem, finding the best alignment of the MSA remains an open problem. In this work, we propose a new multiobjective optimization approach based on the Artificial Bee Colony (ABC) algorithm to solve the MSA problem. The ABC algorithm is inspired by the intelligent behavior of honey bee swarms. Our proposed approach optimizes two objective functions; the sum-of-pairs (SP) function and entropy. Optimizing these objective functions represents a trade off between maximizing the SP function and minimizing the entropy to choose the most suitable alignment. Experiments are conducted on 12 datasets from BAliBASE 3.0. The experimental results show that our proposed approach achieves better alignments than Clustal in four of the tested datasets. In general, the proposed approach performs better on RV12 datasets.

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.

This paper attempts to identify recent trends in counteraction to the intruder’s penetration into the system at reconnaissance stage as the sphere of information security. The problem of actions interrelation, agents’ information awareness and system transition from one state into another is formulated.Based on the functional model, formalization of the three tasks is presented. The first task formulates the conditions in which the system can not transform into undesirable state for a given set of indiscernible elements. The second task formalizes the way to achieve a safe state in the system and allows one to formulate the optimization problem. The third task formalises the conditions under which the system agents actions may be indiscernible to each other.The scope of study for functional steganography is defined. Exponential complexity of agents actions factorization in a system is proved. The definition of absolutely indiscernible actions is provided

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.

The 2.4 GHz band is still heavily used for domestic wireless networks. As the band offers only three non-overlapping channels, in crowded environments, users can suffer from high interference level. To minimize the total interference, an exhaustive channel assignment algorithm, able to find the optimal assignment, can be considered. However, its exponential complexity makes it impractical for sets larger than just several access points (APs). In this paper, a few modifications are introduced which speed up the basic algorithm execution without deteriorating its optimality. The modifications are divided into implementation-related and algorithm-related. Introduced improvements result in over 20 times speed-up of the algorithm execution making it possible to find the optimal channel assignments for over 20-AP sets in minutes instead of hours.

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption. In this paper, we model the behaviors of general OpenMP task systems with non-well-nested branching structures and study the problem of how to bound their worst-case response times (WCRT). A naive solution is to apply the established WCRT bound for DAG tasks without conditional branches to the exponentially many possible execution flows, which has exponential time complexity. In this paper, we develop a linear-time algorithm to efficiently calculate WCRT bounds for OpenMP task systems with non-well-nested branching structures. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Graph databases and distributed graph computing systems have traditionally abstracted the design and execution of algorithms by encouraging users to take the perspective of lone graph objects, like vertices and edges. In this paper, we introduce the SmartGraph, a graph database that instead relies upon thinking like a smarter device often found in real-life computer networks, the router. Unlike existing methodologies that work at the subgraph level, the SmartGraph is implemented as a network of artificially intelligent Communicating Sequential Processes. The primary goal of this design is to give each “router” a large degree of autonomy. We demonstrate how this design facilitates the formulation and solution of an optimization problem which we refer to as the “router representation problem”, wherein each router selects a beneficial graph data structure according to its individual requirements (including its local data structure, and the operations requested of it). We demonstrate a solution to the router representation problem wherein the combinatorial global optimization problem with exponential complexity is reduced to a series of linear problems locally solvable by each AI router.

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

Pattern-based change detectors (PBCDs) are non-parametric unsupervised change detection methods that are based on observed changes in sets of frequent patterns over time. In this paper we study PBCDs for dynamic networks; that is, graphs that change over time, represented as a stream of snapshots. Accurate PBCDs rely on exhaustively mining sets of patterns on which a change detection step is performed. Exhaustive mining, however, has worst case exponential time complexity, rendering this class of algorithms inefficient in practice. Therefore, in this paper we propose non-exhaustive PBCDs for dynamic networks. The algorithm we propose prunes the search space following a beam-search approach. The results obtained on real-world and synthetic dynamic networks, show that this approach is surprisingly effective in both increasing the efficiency of the mining step as in achieving higher detection accuracy, compared with state-of-the-art approaches.

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.

Formal concept analysis is able to visualize and represent knowledge using concept lattice and (attribute) implication. Decision implication is a counterpart of implication in the setting of decision-making. Decision implication canonical basis is a complete, non-redundant and optimal set of decision implications. At present, decision implication canonical basis can be generated with the help of minimal generators; however, this method is not efficient because of its exponential complexity. To solve this problem, we propose an algorithm to generate decision implication canonical basis based on true premises and analyze its time complexity. Experimental results verify the efficiency of this algorithm.

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.