Добірка наукової літератури з теми "Signed hypercubes"

One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, you can use the apparatus of graph theory. Minimal edge extensions of a graph are considered, which are a model for studying the failure of links in a computing system. A graph G* = (V*,α*) with n vertices is called a minimal k-edge extension of an n-vertex graph G = (V, α) if the graph G is embedded in every graph obtained from G* by deleting any of its k edges and has the minimum possible number of edges. The hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. The hypercube is a common topology for building computing systems. Previously, a family of graphs Q*n was described, whose representatives for n>1 are minimal edge 1-extensions of the corresponding hypercubes. In this paper, we obtain an analytical proof of the uniqueness of minimal edge 1-extensions of hypercubes for n≤4 and establish a general property of an arbitrary minimal edge 1-extension of a hypercube Qn for n>2: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to 2.

The controllability for complex network system is to find the minimum number of leaders for the network system to achieve effective control of the global networks. In this paper, the problem of controllability of the directed network for a family of matrices carrying the structure under directed hypercube is considered. The relationship between the minimum number of leaders for the directed network system and the number of the signed zero forcing set is established. The minimum number of leaders of the directed networks system under a directed hypercube is obtained by computing the zero forcing number of a signed graph.

Graphs are used as models to solve problems in fields such as mathematics, computer science, physics, and chemistry. In particular, torus, hypercube, and star graphs are popular when modeling the connection structure of processors in parallel computing because they are symmetric and have a low network cost. Whereas a hypercube has a substantially smaller diameter than a torus, star graphs have been presented as an alternative to hypercubes because of their lower network cost. We propose a novel log star (LS) that is symmetric and has a lower network cost than a star graph. The LS is an undirected, recursive, and regular graph. In LSn, the number of nodes is n! while the degree is 2log2n − 1 and the diameter is 0.5n(log2n)2 + 0.75nlog2n. In this study, we analyze the basic topological properties of LS. We prove that LSn is a symmetrical connected graph and analyzed its subgraph characteristics. Then, we propose a routing algorithm and derive the diameter and network cost. Finally, the network costs of the LS and star graph-like networks are compared.

Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles
Complexity measures of Boolean functions capture various aspects of the hardness of computing a function and their study is about finding connections between different complexity measures. In the first part of this thesis, we introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game in which two players are given inputs with different function values and are asked to output some index i where their inputs differ, in a zero-communication setting. We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is bounded above by Randomised query and Certificate complexities. On the other hand, it is bounded below by fractional certificate complexity, making it a good candidate to prove strong lower bounds on randomised query complexity. Complexity in the private coin model is bounded below by zero-error randomised query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. While public coin certificate game complexity is bounded above by randomised query complexity, quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of n on the quantum certificate game complexity of the OR function, whose quantum query complexity is Θ(√n) and then go on to show that this "non-signaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to λ2, where λ is the spectral sensitivity. In the second part of this thesis, we revisit the celebrated proof of the sensitivity conjecture by Hao Huang. Using spectral techniques, Huang proved that every subgraph of the hypercube Hn of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with earlier work, this completed a proof of the sensitivity conjecture. We show an alternate proof of Huang's result using only linear dependency of vectors associated with the vertices of the hypercube. Our approach helps gain insight on more structural properties of the induced subgraph in addition to the largest degree. In particular, we prove that in any induced subgraph of Hn with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application, we show that for any Boolean function f, the polynomial degree is bounded above by the product of 0-sensitivity and 1-sensitivity, s0(f)s1(f), a strictly stronger statement which implies Huang's theorem. We also obtain structural relations for induced subgraphs at distance 3. A key implement in Huang's proof was signed hypercubes with the property that every cycle of length 4 is assigned a negative sign. We take a detailed look at this signature and give a nearly optimal signature that uses the minimum number of negative edges while ensuring that every 4-cycle is negative. This problem turns out to be related to one of Erdös' problems on the largest 4-cycle free subgraph of the hypercube

Cette thèse est consacrée à la modélisation markovienne et l'optimisation numérique pour la restauration des signaux en (1D) et (2D) bruités par un bruit blanc gaussien centré. Le principe du modèle markovien exploite le champ de Markov et de Gibbs sur des graphes finis via le théorème d'Hammersley Clifford. Le signal restauré est estimé au sens du critère du maximum a posteriori (MAP), qui conduit à un problème d'optimisation globale mixte, non convexe et de très grande taille, réputé très difficile. Plusieurs méthodes ont été proposées notamment le recuit simulé (SA), le graduted non convexity (GNC) et le recuit par champ moyen (MFA) introduits respectivement par (GG84), (BLA87) et (GEI89). Nous proposons des variantes de GNC 1er et 2eme ordre et surtout un nouvel algorithme que nous appelons balayage par position de discontinuité (BPD). Ce nouvel algorithme s'inspire des méthodes de coupe énumérative en optimisation combinatoire. Il se démarque des autres algorithmes cités par sa nature parallélisable, sa rapidité et sa facilite pour le choix des paramètres de lissage et de sensibilité. Ainsi, par exemple, dans le cas du signal en (1D) un traitement assisté ou automatique est proposé selon le degré de connaissance du signal à restaurer. De plus la souplesse de l'algorithme BPD permet d'introduire d'autres types de fonctions d'énergie élargissant le champ des applications (applications contour-image).

A single-instruction machine is generally considered to be impractical in electronics because it may lead to excessively complex programs. In digital optical cellular image processors (DOCIPs), the single-instruction machine is well suited to the system architecture. The reason for this is that the optical parallelism and global interconnection capabilities of DOCIP also contribute to parallel optical control signal flow. We show that two DOCIP architectures, DOCIP array and DOCIP hypercube, have a simple organization, low cell complexity, and (with external memory) the ability to simulate random access machines and Turing machines. Both of them have a simple control structure: (1) a single instruction that includes fetch, execute, store, and pipelines the three fundamental operations of binary image algebra1; (2) a single control level that has only one higher control level for interpretation between program and data. The DOCIP array, a nearest-neighbor connected cellular array, has an extremely simple organization due to its O(1) interconnectivity. The DOCIP hypercube increases the interconnectivity to O(log N) and combines features of conventional cellular logic and conventional hypercube architectures for 2-D computational cells. The programming and instruction set of the DOCIP array and the DOCIP hypercube are illustrated and compared.

As VLSI chip sizes and device densities increase, signal communication limitations begin to dominate system perfomance1,2. By replacing particular electronic transmission lines with optical signal paths, perfomance can be improved in terms of speed, alleviation of clock skew and a reduction in silicon area devoted to interconnects. These improvements can be achieved for on chip or chip-to-chip communication, but become dramatically evident for wafer scale communication. At the wafer scale level, global interconnections are infeasible to perform electronically due to the line lengths and complexity involved. In addition, arrays of parallel processing elements are utilized in order to alleviate problems of yield. The use of optical interconnections would allow for the interconnection of these processing elements in a global highly parallel manner (such as hypercube and butterfly machines) that are difficult to achieve electronically3. However, in this case the optical system must be able to handle a large number of sources, each requiring a large fanout. Highly complex interconnection schemes can be achieved with the use of a holographic optical element (HOE) for free space optical interconnections.

Free-space optical interconnects can be used to provide communication between sources and detectors (in the same or different planes) in a digital optical processor. Diffractive optics are particularly well suited to perform this interconnection because of their high efficiency, computerized design, and microelectronics fabrication compatibility. Free-space optical interconnection systems can be classified by their degree of space-variance. Space-invariant systems make use of one point spread function for all sources. Space-variant systems, on the other hand, use one point spread function per source. In between these two extremes, there are systems that divide the sources between several point spread functions. Which one of these systems will be best suited depends on the given interconnection pattern, e.g., perfect shuffle, hypercube, or twin butterfly. The design of all of these systems is studied from a practical fabrication standpoint. System volume is calculated in terms of parameters such as the f/No. of the diffractive lens, the wavelength of light, and the total number, size, and separation of the optical sources and detectors. Performance issues such as interconnection complexity, diffraction efficiency, aberrations, and signal to noise ratio are discussed. Tradeoffs between parameters such as volume, hologram complexity, and performance are determined and discussed.

Abstract This paper describes the development plan optimization and probabilistic uncertainty study using Latin Hypercube Experimental design constrained to production performance in Lower Miocene (LM) reservoirs of the Shenzi Field in deepwater Gulf of Mexico (DW GOM). The purpose of the development plan optimization was to identify, rank, and characterize future development opportunities i.e. infills and injectors in the LM reservoirs to arrest the field decline. The study uses history matched dynamic simulation models. Uncertainty parameters were identified and ranked through single variate sensitivity analysis with consideration of impact on history match quality. Top ranking uncertainty parameters were then characterized using probability distribution functions. Latin Hypercube Experimental design was then used to generate vectors of uncertainty parameters to be used in running many simulation cases. The simulation results from experimental design were filtered based on history match quality to 200 cases, a more manageable number for visualization and further simulation study. The 200 cases were then used to identify development opportunities and characterize their resource range. Identification and proper characterization of uncertainty parameters were essential to attain reliable estimates of resource range and opportunity ranking, and for gaining insights into the downside risks of each development opportunity. This is especially the case for scenario-based uncertainty parameters with discrete distributions e.g., geologic scenarios. Application of simple data analytics techniques and powerful visualization tools was important in thoroughly analyzing the results of many simulation cases, understanding key uncertainty parameters and interdependencies for each development opportunity. For most opportunities the incremental Estimated Ultimate Recoveries (EURs) calculated from the reference case model were optimistic compared to the P50 incremental EUR from the uncertainty study, highlighting the risks involved in making development decisions based on only reference case model results. A two well development concept with the minimum downside resource risk was identified. This was the case because the incremental EUR from the two wells was strongly correlated to a key uncertainty parameter but with opposite signs, thus reducing the downside resource risk. Development plan optimization and ranking of development opportunities were performed using hundreds of history-matched simulation cases to properly capture the subsurface uncertainties in the estimated resource range for each opportunity. This methodology resulted in identifying development concepts with minimum low case resource risk and largest mid case resource.