Algorítmica y Complejidad Computacional. Recopilación de enlaces, noviembre 2016: Redes de Interconexión, Grafos de Cayley, Recorridos Hamiltonianos, Permutaciones y otros. 

Una recopilación de artículos sobre los temas que aparecen en el título, realizada en fechas varias, la última esta misma mañana (por el lunes), en la cual he encontrado cosas muy interesantes con respecto a potenciales aplicaciones. Aunque ya se sabe que entre la ingeniería apegada a la tierra y las elevadas matemáticas se encuentra el limbo de potenciales aplicaciones que nunca terminarán de concretarse en sistemas reales.

Antes de empezar con los enlaces un extracto de una muy reciente entrada en un blog de un experto en complejidad computacional. Creo que es reseñable ya que la declaración es sorprendente, contundente y va contracorriente:

The bottom line of this post is that we can’t prove lower bounds because they are false, and it is a puzzle to me why some people appear confident that P is different from NP.

Añadido a última hora.

On the Complexity of the Word Problem of Automaton Semigroups and Automaton Groups

I. Enfoque de ingeniería de redes: redes de interconexión (supercomputadores, NoC´s, Data Center Networks).

Data center interconnection networks are not hyperbolic

David Coudert1,2 and Guillaume Ducoffe2,1 1 Inria, France 2Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, 06900 Sophia Antipolis, France

Abstract Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

–Muy interesante. Y muy reciente, de 2016.

The Influence of Datacenter Usage on Symmetry in Datacenter Network Design

Alejandro Ericksona , Iain A. Stewarta,∗ aSchool of Engineering and Computing Sciences, Durham University, South Road, Durham DH1 3LE, U.K.

Abstract We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multi-tenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning-trees, pancyclicity, and variations of Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graphtheoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.


Whilst the design of DCNs is more recent, it has much in common with general interconnection network design yet there are profound differences too, prompted by, for example, usage, scale, and packaging. Hitherto, the most common metrics used for DCN evaluation are the availability of routing algorithms, hardware cost (e.g., number of servers and switches), hardware complexity (e.g., number of server-ports), diameter, bisection width, connectivity, and shortest-path lengths. It is probably fair to say that the development of appropriate topological metrics for DCNs is not as advanced as it is for distributed-memory multiprocessors and networks-onchips, and that the validity of these topological metrics within a datacenter environment is not as well established. Our paper seeks to strengthen the role of topological metrics in DCN design.

Our work sits between the engineering process of building datacenters and the theoretical consideration of abstractions of DCNs as discrete structures; that is, it is graph theory targetted towards a practical application area.

Data center network architecture in cloud computing: review, taxonomy, and open research issues

Han QI†1, Muhammad SHIRAZ1, Jie-yao LIU1, Abdullah GANI†1, Zulkanain ABDUL RAHMAN2, Torki A. ALTAMEEM3 (1Mobile Cloud Computing Research Lab, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur 50603, Malaysia) (2Department of History, Faculty of Arts and Social Sciences, University of Malaya, Kuala Lumpur 50603, Malaysia) (3Department of Computer Science, Riyadh Community College, King Saud University, Riyadh 11533, Saudi Arabia) †E-mail:; Received Jan. 9, 2014; Revision accepted May 10, 2014; Crosschecked Aug. 13, 2014

Abstract: The data center network (DCN), which is an important component of data centers, consists of a large number of hosted servers and switches connected with high speed communication links. A DCN enables the deployment of resources centralization and on-demand access of the information and services of data centers to users. In recent years, the scale of the DCN has constantly increased with the widespread use of cloud-based services and the unprecedented amount of data delivery in/between data centers, whereas the traditional DCN architecture lacks aggregate bandwidth, scalability, and cost effectiveness for coping with the increasing demands of tenants in accessing the services of cloud data centers. Therefore, the design of a novel DCN architecture with the features of scalability, low cost, robustness, and energy conservation is required. This paper reviews the recent research findings and technologies of DCN architectures to identify the issues in the existing DCN architectures for cloud computing. We develop a taxonomy for the classification of the current DCN architectures, and also qualitatively analyze the traditional and contemporary DCN architectures. Moreover, the DCN architectures are compared on the basis of the significant characteristics, such as bandwidth, fault tolerance, scalability, overhead, and deployment cost. Finally, we put forward open research issues in the deployment of scalable, low-cost, robust, and energy-efficient DCN architecture, for data centers in computational clouds.

Interconnection Networks Based on Gaussian and Eisenstein-Jacobi Integers by Arash Shamaei

Presented December 10, 2015 Commencement June 2016

Supercomputers and parallel computers consist of many individual nodes connected by edges in an interconnection network. The nodes communicate with each other by passing messages along the edges of the network using a standard message passing mechanism such as the Message Passing Interface (MPI) [10]. The topology chosen for the interconnection network therefore plays an integral role in the performance of the computer. One of the more popular choices is the toroidal topology, which includes toroidal meshes and the k-ary n-cube. For example, the IBM BlueGene/Q [10], the Cray XE6 and XK7 (3D torus gemini interconnect [3]), the HP GS1280 multiprocessor [14], the K-computer [1], and the Intel Ivy bridge [18] all use a toroidal topology. Eisenstein-Jacobi networks (often abbreviated as EJ networks) are an alternative to 2D tori. Originally developed over two decades ago [30], an EJ network is a 2D wraparound network of degree six. Many topological properties of these networks were explored in [37], [24]. It is shown in [2] that EJ networks are a generalization of the hexagonal torus networks developed earlier in [31], [11], and [22]. In particular, the hexagonal torus topology was used in the design of the Hexagonal Architecture for Real-Time Systems (HARTS) machine at the University of Michigan [31]. The Mayfly [19] designed at HP laboratories is another example of a parallel system that uses a hexagonal torus topology and a hexagonal topology has been proposed for cellular networks [27]. In Chapter 2 we develop two deadlock-free routing algorithms for hexagonal torus interconnection networks. Gaussian networks [38] were proposed as another alternative to toroidal networks. Both a 2D torus and a Gaussian network are of degree four whereas the latter has smaller diameter than a torus with an approximately the same number of nodes. A smaller diameter directly translates to a smaller average message latency, the average time of arrival and departure of messages in the network. Su- 2 percomputers with large number of nodes usually employ n-dimensional tori. For example, the IBM BlueGene/Q [10] uses a 5D torus. Gaussian networks are 2D. In Chapter 3 we develop higher dimensional Gaussian networks as an alternative to higher dimensional tori and many topological properties of higher dimensional Gaussian networks are proved


The hexagonal torus topology was used in the design of the Hexagonal Architecture for Real-Time Systems (HARTS) machine at the University of Michigan [31]. The Mayfly [19] designed at HP laboratories is another example of a parallel system that uses a hexagonal torus topology. In addition, the hexagonal topology has been proposed for cellular networks [27].

Shortest path routing algorithms for hexagonal tori were originally proposed in [31], [11], and [22]. These original algorithms used a three-component addressing scheme based on the decomposition of the network into three edge-disjoint Hamiltonian cycles. Each of the components specifies the order of a node in one of the three Hamiltonian cycles. This was improved in [27] to require fewer bits in each component. Here the node addresses (x, y, z) represent the corresponding position along the angles 0, 60 and 120 degrees from the horizontal axis. It is shown in [27] that under this representation, a node can be represented in more than one possible way and so the representation has some redundancy. Later on, an improved two-component addressing scheme was given [37] and [2]. Under this addressing scheme, each component of the address represents the position of a the node at angles of 0 and 60 degrees from the horizontal axis. (This is summarized in Section 2.2.) This scheme was proved in [2] to have a minimal number of addressing bits.

Conditional diagnosability of bubble-sort star graphs

A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square


Recursive cube of rings (RCR) networks [Y. Sun, P. Cheung, X. Lin, Recursive cube of rings: a new topology for interconnection networks, IEEE Trans. Parallel Dist. Syst. 11 (3) (2000) 275–286] can be widely used in the design and implementation of parallel processing architectures. In this paper, we investigate the routing of a message on RCR networks, that is a key to the performance of this network. We would like to transmit k+1 packets from a source node to a destination node simultaneously along paths on RCR networks, the ith packet will traverse along the i  th path (1⩽i⩽k+1). In order for all packets to arrive at a destination node quickly and securely, the i  th path must be node-disjoint from all other paths. For construction of these paths, employing Hamiltonian circuit Latin square (HCLS), we present O(n2) parallel routing algorithm on RCR networks.

Fault-tolerant Hamiltonian-connectivity of 2-tree generated networks

Abdallah, Mohamad Kassem. Oakland University, ProQuest Dissertations Publishing, 2015. 10108645.

Interconnection networks are often modeled by finite graphs. The vertices of the graph represent the nodes of the network (processing elements, memory modules or switches), and the edges correspond to communication lines. There are many advantages in using Cayley graphs as models for interconnection networks. In this dissertation we consider a class of Cayley graphs that are generated by certain 3-cycles on the alternating group An. These graphs are generalizations of the alternating group graph AGn. We look at the case when the 3-cycles form a “tree-like structure”, and analyze the fault-tolerant Hamiltonian-connectivity of such graphs. We prove that these graphs are (2n-7)-fault-tolerant Hamiltonian connected.

II. Grafos de Cayley, enfoque matemático y otras aplicaciones.

–Grafos  de Cayley de Monoides y Semigrupos.

Cayley graphs as classifiers for data mining: The influence of asymmetries


This demonstrates that Cayley graphs happen to be general enough to accomplish all tasks performed by the finite state automata. Without going into all the details, we refer the readers to [26,36,38,47,90,96] for preliminaries on automata theory.

Optimal Networks from Error Correcting Codes

Ratko V. Tomic
Infinetics Technologies, Inc.

To address growth challenges facing large Data Centers and supercomputing clusters a new construction is presented for scalable, high throughput, low latency networks. The resulting networks require 1.5-5 times fewer switches, 2-6 times fewer cables, have 1.2-2 times lower latency and correspondingly lower congestion and packet losses than the best present or proposed networks providing the same number of ports at the same total bisection. These advantage ratios increase with network size.

The key new ingredient is the exact equivalence discovered between the problem of maximizing network bisection for large classes of practically interesting Cayley graphs and the problem of maximizing codeword distance for linear error correcting codes. Resulting translation recipe converts existent optimal error correcting codes into optimal throughput networks.

Ethernet implementation was developed and a prototype built using managed COTS switches. Integrated control plane handles topology, distribution of forwarding tables and fault recovery. Scalable routing uses stretch-free topological addressing. Local load balancing distributes flows at the source over multiple, nonminimal, edge disjoint paths. Path selection does not use tunneling or overlays but embeds path selectors in the topological addresses resulting in wire-speed forwarding and allowing for cut-through switching where available.

Diametro en grafos de Cayley.

A note on Hamiltonian decomposition of Bubble-Sort graphs

Hamilton paths in Cayley graphs on Coxeter groups. 

Brian Alspach School of Mathematical and Physical Sciences, University of Newcastle Callaghan, NSW 2308, Australia Received 11 July 2013, accepted 7 January 2014, published online 18 April 2014

Abstract We consider several families of Cayley graphs on the finite Coxeter groups An, Bn, and Dn with regard to the problem of whether they are Hamilton-laceable or Hamiltonconnected. It is known that every connected bipartite Cayley graph on An, n ≥ 2, whose connection set contains only transpositions and has valency at least three is Hamiltonlaceable. We obtain analogous results for connected bipartite Cayley graphs on Bn, and for connected Cayley graphs on Dn. Non-bipartite examples arise for the latter family

Automorphisms generating disjoint hamilton cycles in star graphs.

The presence of edge-disjoint Hamilton cycles is a desirable feature for an interconnection network topology. The reason for this is that in multiport systems, where nodes communicate with neighbours in unit time, messages can be broken down into small units and sent along disjoint Hamilton cycles to improve performance. The Hamilton decomposition of a k-regular graph G is the partitioning of its edge set into Hamiltonian cycles, i.e. if k is even, the edge set can be partitioned into k/2 Hamiltonian cycles, and if k is odd, the edge set can be partitioned into (k −1)/2 Hamiltonian cycles and a perfect matching. Several results concerning the existence of disjoint Hamilton cycles on graphs, in particular hypercubes, are known. One of the most interesting properties of the hypercube is that it is Hamilton decomposable [35]. It is known that there are bn/2c disjoint Hamiltonian cycles on a hypercube of dimension n

Vertex-transitive graphs and their arc-types

Marston Conder, Tomaˇz Pisanski, and Arjana Zitnik ˇ6 May 2015

Abstract Let X be a finite vertex-transitive graph of valency d, and let A be the full automorphism group of X. Then the arc-type of X is defined in terms of the sizes of the orbits of the action of the stabiliser Av of a given vertex v on the set of arcs incident with v. Specifically, the arc-type is the partition of d as the sum n1 +n2 +· · ·+nt + (m1 +m1)+ (m2 +m2)+· · ·+ (ms +ms), where n1, n2, . . . , nt are the sizes of the self-paired orbits, and m1, m1, m2, m2, . . . , ms, ms are the sizes of the non-self-paired orbits, in descending order. In this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two ‘relatively prime’ graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of 1 + 1 and (1 + 1), every partition as defined above is realisable, in the sense that there exists at least one graph with the given partition as its arc-type.

–Cayley isomorphism problem.

Edward Dobson

We give a necessary condition to reduce the Cayley isomorphism problem for Cayley objects of a nilpotent or abelian group GG whose order satisfies certain arithmetic properties to the Cayley isomorphism problem of Cayley objects of the Sylow subgroups of GG in the case of nilpotent groups, and in the case of abelian groups to certain natural subgroups. As an application of this result, we show that Zq×Z2p×ZmZq×Zp2×Zm is a CI-group with respect to digraphs, where qq and pp are primes with p2<qp2<q and mm is a square-free integer satisfying certain arithmetic conditions (but there are no other restrictions on qq and pp).

–Ted Dobson: The Cayley Isomorphism Problem

Date: 12. 12. 2008
Source: Mathematics colloquium
Četrtek, 18. 12. 2008, ob 18.15 v predavalnici 2.02 na Jadranski 21.

In its most general form, the Cayley Isomorphism Problem asks for necessary and sufficient conditions for two Cayley graphs of a group Gto be isomorphic.  Usually, the “necessary and sufficient conditions” consist of an explicit list of permutations of G such that two Cayley graphs of G are isomorphic if and only if they are isomorphic by one of the permutations on the list.  If this list is always as short as possible — that is, it only consists of automorphisms of G — we say that G is a CI-group with respect to graphs.  Determining whether or not a group is a CI-group with respect to graphs has received considerable attention over the last 40 or so years.  In this talk, we will present an overview of this problem, as well as discussing various generalizations of the problem.

III. Varios surveys más o menos recientes sobre recorridos hamiltonianos grafos y digrafos generales.

2014. Hamilton cycles in graphs and hypergraphs: an extremal perspective

Abstract. As one of the most fundamental and well-known NP-complete problems, the Hamilton cycle problem has been the subject of intensive research. Recent developments in the area have highlighted the crucial role played by the notions of expansion and quasi-randomness. These concepts and other recent techniques have led to the solution of several long-standing problems in the area. New aspects have also emerged, such as resilience, robustness and the study of Hamilton cycles in hypergraphs. We survey these developments and highlight open problems, with an emphasis on extremal and probabilistic approaches.

–Recent Advances on the Hamiltonian Problem: Survey III. R. Gould.

ArticleinGraphs and Combinatorics 30(1) · January 2014with44 Reads

Se centra sobre todo en grafos. A nosotros nos interesan más los digrafos, objeto sobre el que trata el siguiente survey.

–2012. 90] D. Kuhn and D. Osthus, A survey on Hamilton cycles in directed graphs, European J. Combinatorics 33 (2012), 750–766.

Abstract. We survey some recent results on long-standing conjectures regarding Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly’s conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are ‘almost’ edge-disjoint. We also highlight the role that the notion of ‘robust expansion’ plays in several of the proofs. New and old open problems are discussed.

IV. Expansion and hamiltonicity.





This thesis contains four results in extremal graph theory relating to the recent notion of robust expansion, and the classical notion of Hamiltonicity. In Chapter 2 we prove that every sufficiently large ‘robustly expanding’ digraph which is dense and regular has an approximate Hamilton decomposition. This provides a common generalisation of several previous results and in turn was a crucial tool in Ku¨hn and Osthus’s proof that in fact these conditions guarantee a Hamilton decomposition, thereby proving a conjecture of Kelly from 1968 on regular tournaments. In Chapters 3 and 4, we prove that every sufficiently large 3-connected D-regular graph on n vertices with D ≥ n/4 contains a Hamilton cycle. This answers a problem of Bolloba´s and H¨aggkvist from the 1970s. Along the way, we prove a general result about the structure of dense regular graphs, and consider other applications of this. Chapter 5 is devoted to a degree sequence analogue of the famous P´osa conjecture. Our main result is the following: if the i th largest degree in a sufficiently large graph G on n vertices is at least a little larger than n/3+i for i ≤ n/3, then G contains the square of a Hamilton cycle.

Relacionado 1.

Relacionado 2.

Y un artículo que aunque de 2007 creo que no hemos  citado nunca:

Hamilton cycles in highly connected and expanding graphs

Dan Hefetz ∗ Michael Krivelevich † Tibor Szab´o ‡ February 14, 2007

Abstract In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on only two properties: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.

Fine-Grained Complexity and Conditional Hardness for Sparse Graphs

Udit Agarwal⋆ and Vijaya Ramachandran∗ November 22, 2016


There is a large class of path and cycle problems on graphs that currently have O˜(n 3 ) 1 time algorithms. Graphs encountered in practice are typically sparse, with the number of edges m being close to linear in n, the number of vertices, or at least with m << n2 . When considering sparsity, the current time complexities of these problems split into two classes: the Θ( ˜ mn) class, which includes APSP, Betweenness Centrality, and Minimum-Weight-Cycle, among several other problems, and the Θ(m3/2 ) class, which includes all problems relating to enumerating and detecting triangles. Here n and m are the number of vertices and edges in the graph. We investigate the fine-grained complexity of these problems on sparse graphs, and our main results are the following: 1. Reductions and Algorithms. We define the notion of a sparse reduction that preserves graph sparsity, and we present several such reductions for graph problems in the O˜(mn) class. This gives rise to a rich partial order on graph problems with O˜(mn) time algorithms, with the Minimum-Weight-Cycle problem as a major source in this partial order, and APSP a major sink. Surprisingly, very few of the known subcubic results are sparse reductions (outside of a few reductions that place Centrality problems in the sub-cubic equivalence class [1]). We develop new techniques in order to preserve sparsity in our reductions, many of which are nontrivial and intricate. Some of our reductions also lead to improved algorithms for various problems on finding simple cycles in undirected graphs. 2. Conditional Hardness. We establish a surprising conditional hardness result for sparse graphs: We show that if the Strong Exponential Time Hypothesis (SETH) holds, then several problems in the O˜(mn) class, including certain problems that are also in the sub-cubic equivalence class such as Betweenness Centrality and Eccentricities, cannot have ‘sub-mn’ time algorithms, i.e., algorithms that run in O(mα · n 2−α−ǫ ) time, for constants α ≥ 0, ǫ > 0. In particular, this result means that under SETH, the sub-cubic equivalence class is split into at least two classes when sparsity is taken into account, with triangle finding problems having faster algorithms than Eccentricities or Betweenness Centrality. This hardness result for the O˜(mn) class is also surprising because a similar hardness result for the sub-cubic class is considered unlikely [5] since this would falsify NSETH (Nondeterministic SETH).

Deconstructing 1-local expanders


Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular N-vertex graph with spectral gap that is (1log2N) , and similarly a O(1)-regular N-vertex graph with spectral gap 1\tildeO(logN)Starting from a generic candidate for a 1-local expander, we formulate a natural problem regarding coordinated random walks (CRW) on the corresponding relocation graph (which has size that is logarithmic in the size of the candidate 1-local graph), and observe that any solution to the CRW problem yields 1-local expanders, and any constant-size expanding set of generators for the symmetric group yields a solution to the CRW problem.

This yields an alternative construction and different analysis than the one used by Viola and Wigderson. Furthermore, we show that solving the CRW problem is equivalent to constructing 1-local expanders.

–Mixing in groups

Non-abelian groups behave in ways that are useful in computer science. Barrington’s famous result [Bar89] shows that we can write efficiently an arbitrary low-depth computation as a group product over any non-solvable group. (Being non-solvable is a certain strengthening of being non-abelian which is not important now.) His result, which is false for abelian groups, has found myriad applications in computer science. And it is amusing to note that actually results about representing computation as group products were obtained twenty years before Barrington, see [KMR66]; but the time was not yet ripe.

This post is about a different property that certain non-abelian groups have and that is also useful. Basically, these groups ”mix” in the sense that if you have several distributions over the group, and the distributions have high entropy, then the product distribution (i.e., sample from each distribution and output the product) is very close to uniform.

[Bar89]    David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. of Computer and System Sciences, 38(1):150–164, 1989.

[KMR66]   Kenneth Krohn, W. D. Maurer, and John Rhodes. Realizing complex Boolean functions with simple groups. Information and Control, 9:190–195, 1966.

–Expanders y juegos. 

Multiplayer parallel repetition for expander games

Authors: ContactIrit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen
Publication: 26th October 2016 17:02
Downloads: 37


We investigate the value of parallel repetition of one-round games with any number of players k2. It has been an open question whether an analogue of Raz’s Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games.

Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense.

We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

V. Criptografía. 

Diffie-Hellman key exchange.

Criptographic hash functions.

Near Optimal Bounds for Collision in Pollard Rho for Discrete Log

Random Cayley Digraphs and the Discrete Logarithm

Extended Abstract Jeremy Horwitz1 and Ramarathnam Venkatesan2 1 Stanford University, Stanford, CA 94305, USA 2 Microsoft Research, Redmond, WA 98052, USA

¿ 2003 ?


We formally show that there is an algorithm for dlog over all abelian groups that runs in expected optimal time (up to logarithmic factors) and uses only a small amount of space. To our knowledge, this is the first such analysis. Our algorithm is a modification of the classic Pollard rho, introducing explicit randomization of the parameters for the updating steps of the algorithm, and is analyzed using random walks with limited independence over abelian groups (a study which is of its own interest). Our analysis shows that finding cycles in such large graphs over groups that can be efficiently locally navigated is as hard as dlog.


While finding paths and cycles efficiently in the usual graphs is well-understood, finding paths and cycles in succinct graphs using only small space may be hard (though, in some cases, such as hypercubes, this is trivial). Indeed, one may view the classic Pollard rho for solving y = g x as a method both to define (using y and g) a succinctly presented graph together with its navigation algorithm h and to find a cycle in the succinct graph (then solve a linear equation to find dlog). Our modification to Pollard rho differs only in the definition step and is aimed at bounding the run time and the success probability in the cycle-finding step.

Una tesis de uno de los autores con un contenido similar (2004).

Discrete log con curvas elípticas. Uno de los autores es el director de la tesis anterior (2005).

Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?

David Jao1 , Stephen Miller⋆,2,3 , and Ramarathnam Venkatesan1 1 Microsoft Research, 1 Microsoft Way, Redmond WA 98052 {davidjao,venkie} 2 Department of Mathematics, Rutgers University 110 Frelinghuysen Rd, Piscataway, NJ 08854-8019 3 Einstein Institute of Mathematics, Edmond J. Safra Campus, Givat Ram The Hebrew University of Jerusalem, Jerusalem 91904 Israel

Abstract. The aim of this paper is to justify the common cryptographic practice of selecting elliptic curves using their order as the primary criterion. We can formalize this issue by asking whether the discrete log problem (dlog) has the same difficulty for all curves over a given fi- nite field with the same order. We prove that this is essentially true by showing polynomial time random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). We do so by constructing certain expander graphs, similar to Ramanujan graphs, with elliptic curves as nodes and low degree isogenies as edges. The result is obtained from the rapid mixing of random walks on this graph. Our proof works only for curves with (nearly) the same endomorphism rings. Without this technical restriction such a dlog equivalence might be false; however, in practice the restriction may be moot, because all known polynomial time techniques for constructing equal order curves produce only curves with nearly equal endomorphism rings. Keywords: random reducibility, discrete log, elliptic curves, isogenies, modular forms, L-functions, generalized Riemann hypothesis, Ramanujan graphs, expanders, rapid mixing.

Este parece ser el mismo que el anterior, aunque tiene otro título:

Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves

David Jao, Stephen D. Miller∗
, and Ramarathnam Venkatesan
November 13, 2004


Cryptographic applications using an elliptic curve over a finite field
filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (dlog) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare “random” type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.

Indirectamente relacionado.

On graph-based cryptographic hash functions

Permutaciones y computación cuántica. 

Imprimitive Permutations in Primitive Groups

The goal of this paper is to study primitive groups that are contained in the union of maximal (in the symmetric group) imprimitive groups. The study of types of permutations that appear inside primitive groups goes back to the origins of the theory of permutation groups. However, this is another instance of a situation common in mathematics in which a very natural problem turns out to be extremely difficult. Fortunately, the enormous progresses of the last few decades seem to allow a new momentum on the attack to this problem. In this paper we prove that there are infinite families of primitive groups contained in the union of imprimitive groups and propose a new hierarchy for primitive groups based on that fact. In addition to the previous results and hierarchy, we introduce some algorithms to handle permutations, provide the corresponding GAP implementation, solve some open problems, and propose a large list of open problems.

El siguiente artículo me llamó la atención y lo he incluido para dedicarle más  tiempo en otra ocasión. Realmente no se si tiene mucho  que ver con los temas sobre los que hemos  tratado en los otros puntos.

–The Computational Complexity of Ball Permutations

Scott Aaronson*1 , Adam Bouland†2, Greg Kuperberg‡3, and Saeed Mehraban§2 1Department of Computer Science, University of Texas at Austin 2CSAIL, Massachusetts Institute of Technology, Cambridge, MA 3Department of Mathematics, UC Davis, Davis, CA


Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.

Permutational Quantum Computing

Stephen P. Jordan Institute for Quantum Information, California Institute of Technology.


In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and simulate certain processes in the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.

Computing Spin Networks

Annalisa Marzuoli Dipartimento di Fisica Nucleare e Teorica, Universit`a degli Studi di Pavia and Istituto Nazionale di Fisica Nucleare, Sezione di Pavia, via A. Bassi 6, 27100 Pavia (Italy) and Mario Rasetti Dipartimento di Fisica and Istituto Nazionale di Fisica della Materia, Politecnico di Torino, corso Duca degli Abruzzi 24, 10129 Torino (Italy)


We expand a set of notions recently introduced providing the general setting for a universal representation of the quantum structure on which quantum information stands. The dynamical evolution process associated with generic quantum information manipulation is based on the (re)coupling theory of SU(2) angular momenta. Such scheme automatically incorporates all the essential features that make quantum information encoding much more efficient than classical: it is fully discrete; it deals with inherently entangled states, naturally endowed with a tensor product structure; it allows for generic encoding patterns. The model proposed can be thought of as the non–Boolean generalization of the quantum circuit model, with unitary gates expressed in terms of 3nj coefficients connecting inequivalent binary coupling schemes of n + 1 angular momentum variables, as well as Wigner rotations in the eigenspace of the total angular momentum. A crucial role is played by elementary j–gates (6j symbols) which satisfy algebraic identities that make the structure of the model similar to ′′state sum models′′ employed in discretizing Topological Quantum Field Theories and quantum gravity. The spin network simulator can thus be viewed also as a Combinatorial QFT model for computation. The semiclassical limit (large j) is discussed.



Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: