Routing complexity of faulty networks

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for the d‐dimensional mesh. We use tools from percolation theory to show that in the d‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph G_n,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Weight choosability of graphs

Suppose the edges of a graph G are assigned 3‐element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K₂). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242–256, 2009     

Average‐case complexity of shortest‐paths problems in the vertex‐potential model

We study the average‐case complexity of shortest‐paths problems in the vertex‐potential model. The vertex‐potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and with respect to this model, the single‐source shortest‐paths problem can be solved in O(n²) expected time, and the all‐pairs shortest‐paths problem can be solved in O(n² log n) expected time. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 33–46, 2000     

The Guessing Secrets problem: a probabilistic approach

We introduce a probabilistic variant of the Guessing Secrets problem proposed by Chung et al. in [Electron. J. Combin. 8 (2001) R13]. In our variation, a player tries to discover the identity of a set S of n unknown secrets drawn by a second player, from a space Ω of N secrets. The first player tries to learn as much as possible about the elements of S by asking binary questions. For each question asked, the second player randomly chooses one of the n secrets of S that he uses in supplying the answer, which in any case must be truthful. We define a simple probabilistic guessing algorithm that allows us to guess all secrets of S with probability one. We show that the expected number of questions needed to guess all secrets is 2n²log₂N and the expected time complexity of the algorithm is . We also propose a generalization of this probabilistic guessing secrets problem, and provide some similar results for this generalization.     

Continuum percolation with steps in the square or the disc

In 1961 Gilbert defined a model of continuum percolation in which points are placed in the plane according to a Poisson process of density 1, and two are joined if one lies within a disc of area A about the other. We prove some good bounds on the critical area A_c for percolation in this model. The proof is in two parts: First we give a rigorous reduction of the problem to a finite problem, and then we solve this problem using Monte‐Carlo methods. We prove that, with 99.99% confidence, the critical area lies between 4.508 and 4.515. For the corresponding problem with the disc replaced by the square we prove, again with 99.99% confidence, that the critical area lies between 4.392 and 4.398. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Existence of a non‐reflexive embedding with birational Gauss map for a projective variety

We study the relationship between the generic smoothness of the Gauss map and the reflexivity (with respect to the projective dual) for a projective variety defined over an algebraically closed field. The problem we discuss here is whether it is possible for a projective variety X in ℙ^N to re‐embed into some projective space ℙ^M so as to be non‐reflexive with generically smooth Gauss map. Our result is that the answer is affirmative under the assumption that X has dimension at least 3 and the differential of the Gauss map of X in ℙ^N is identically zero; hence the projective varietyX re‐embedded in ℙ^M yields a negative answer to Kleiman–Piene's question: Does the generic smoothness of the Gauss map imply reflexivity for a projective variety? A Fermat hypersurface in ℙ^N with suitable degree in positive characteristic is known to satisfy the assumption above. We give some new, other examples of X in ℙ^N satisfying the assumption. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A simple example of two p-groups with the same automorphism group

It is an open problem whether there exist two different p-groups with the same automorphism group. In this paper, we give a positive answer to this problem by constructing a simple example. Received: 30 September 2008     

Rate of convergence of crossover operators

We study the convergence of mating operators on {0, 1}ⁿ. In particular, we answer questions of Rabani, Rabinovich, and Sinclair (1998) by giving tight estimates on the divergence between the finite‐ and infinite‐population processes, thus solving positively the problem of the simulability of such quadratic dynamical systems. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 58–72, 2003     

Some new results on 1‐rotational 2‐factorizations of the complete graph

It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph K_2n+1 under the action of a group G of order 2n is that the involutions of G are pairwise conjugate. Is this condition also sufficient? The complete answer is still unknown. Adapting the composition technique shown in Buratti and Rinaldi, J Combin Des, 16 (2008), 87–100, we give a positive answer for new classes of groups; for example, the groups G whose involutions lie in the same conjugacy class and having a normal subgroup whose order is the greatest odd divisor of |G|. In particular, every group of order 4t+2 gives a positive answer. Finally, we show that such a composition technique provides 2‐factorizations with a rich group of automorphisms. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 237–247, 2010     

On the parallel complexity of hierarchical clustering and CC‐complete problems

Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well‐studied clustering method involving both top‐down and bottom‐up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top‐down and bottom‐up hierarchical clustering. The top‐down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)‐time, n²‐processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom‐up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC‐complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC‐complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top‐down sequential approach, and the result surprisingly shows that the parallel complexities of the top‐down and bottom‐up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC‐complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008     

Nontopological Condensates for the Self‐Dual Chern‐Simons‐Higgs Model

For the abelian self‐dual Chern‐Simons‐Higgs model we address existence issues of periodic vortex configurations—the so‐called condensates—of nontopological type as k → 0, where k > 0 is the Chern‐Simons parameter. We provide a positive answer to the longstanding problem on the existence of nontopological condensates with magnetic field concentrated at some of the vortex points (as a sum of Dirac measures) as k → 0, a question that is of definite physical interest. © 2015 Wiley Periodicals, Inc.     

An application of the greedy heuristic of set cover to traffic checks

Let us suppose that X is a given, finite, not empty set and ${\mathcal F}Let us suppose that X is a given, finite, not empty set and is a given collection of subsets of X such that their union equals X, in other words covers X. Set cover is the problem of selecting as few as possible subsets from such that their union covers X. Max k-cover is the problem of selecting k subsets from such that their union has maximum cardinality. Both problems are NP-hard. There is a polynomial time greedy heuristic that iteratively selects the subset from that covers the largest number of yet uncovered elements. We implemented this greedy algorithm to support the planning of a checking system that is aimed to check the vehicles in a road network. We would like to answer such questions:

–	How many and which links are sufficient to check a given percentage of all traffic flow?
–	What percentage of traffic can be checked with given links?

This paper defines the necessary data and basic knowledge, gives algorithms to answer the previous questions and also shows the results of an implementation in a road network that contains about 11,000 junctions, 3,000 origin–destination junctions and 26,000 links.     

A Categorical View to Structural Complexity

In the present work we are interested in to provide a universal language for supporting formalisms to specify the approximation hierarchy system for an abstract NP‐hard optimization problem. This work grew from the idea of providing a categorical view of structural complexity to optimization problems. The direction is aimed towards actually exploring the connections among the structural complexity aspects and categorical concepts, which may be viewed in a high‐level, in a structuralistic sense. After introducing the optimization problems categories OPTS and OPT, as well as related questions, a formal system modelling the approximation hierarchy of a given optimization problem is provided, based on categorical shape theory. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Zigzag and Breakup Instabilities of Stripes and Rings in the Two-Dimensional Gray–Scott Model

Two different types of instabilities of equilibrium stripe and ring solutions are studied for the singularly perturbed two‐component Gray–Scott (GS) model in a two‐dimensional domain. The analysis is performed in the semi‐strong interaction limit where the ratio O(?^?2) of the two diffusion coefficients is asymptotically large. For ?→ 0 , an equilibrium stripe solution is constructed where the singularly perturbed component concentrates along the mid‐line of a rectangular domain. An equilibrium ring solution occurs when this component concentrates on some circle that lies concentrically within a circular cylindrical domain. For both the stripe and the ring, the spectrum of the linearized problem is studied with respect to transverse (zigzag) and varicose (breakup) instabilities. Zigzag instabilities are associated with eigenvalues that are asymptotically small as ?→ 0 . Breakup instabilities, associated with eigenvalues that are O(1) as ?→ 0 , are shown to lead to the disintegration of a stripe or a ring into spots. For both the stripe and the ring, a combination of asymptotic and numerical methods are used to determine precise instability bands of wavenumbers for both types of instabilities. The instability bands depend on the relative magnitude, with respect to ?, of a nondimensional feed‐rate parameter A of the GS model. Both the high feed‐rate regime A=O(1) , where self‐replication phenomena occurs, and the intermediate regime O(?^1/2) ?A?O(1) are studied. In both regimes, it is shown that the instability bands for zigzag and breakup instabilities overlap, but that a zigzag instability is always accompanied by a breakup instability. The stability results are confirmed by full numerical simulations. Finally, in the weak interaction regime, where both components of the GS model are singularly perturbed, it is shown from a numerical computation of an eigenvalue problem that there is a parameter set where a zigzag instability can occur with no breakup instability. From full‐scale numerical computations of the GS, it is shown that this instability leads to a large‐scale labyrinthine pattern.     

Enumeration and randomized constructions of hypertrees

Over 30 years ago, Kalai proved a beautiful d‐dimensional analog of Cayley's formula for the number of n‐vertex trees. He enumerated d‐dimensional hypertrees weighted by the squared size of their (d ? 1)‐dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of d‐hypertrees, which is our concern here. Our main result, Theorem 1.4, significantly improves the lower bound for the number of d‐hypertrees. In addition, we study a random 1‐out model of d‐complexes where every (d ? 1)‐dimensional face selects a random d‐face containing it, and show that it has a negligible d‐dimensional homology.     

A note on path and cycle decompositions of graphs

In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph G has a smallest path (resp. path-cycle) decomposition P such that every odd vertex of G is the endpoint of exactly one path of P? This note gives a negative answer to both questions.     

Perturbations of C*-Algebraic Invariants

Kadison and Kastler introduced a metric on the set of all C*-algebras on a fixed Hilbert space. In this paper structural properties of C*-algebras which are close in this metric are examined. Our main result is that the property of having a positive answer to Kadison’s similarity problem transfers to close C*-algebras. In establishing this result we answer questions about closeness of commutants and tensor products when one algebra satisfies the similarity property. We also examine K-theory and traces of close C*-algebras, showing that sufficiently close algebras have isomorphic Elliott invariants when one algebra has the similarity property.     

On the existence of smooth self‐similar blowup profiles for the wave map equation

Consider the equivariant wave map equation from Minkowski space to a rotationally symmetric manifold N that has an equator (e.g., the sphere). In dimension 3, this paper presents a necessary and sufficient condition on N for the existence of a smooth self‐similar blowup profile. More generally, we study the relation between

• the minimizing properties of the equator map for the Dirichlet energy corresponding to the (elliptic) harmonic map problem and
• the existence of a smooth blowup profile for the (hyperbolic) wave map problem.

This has several applications to questions of regularity and uniqueness for the wave map equation. © 2008 Wiley Periodicals, Inc.     

A primal‐dual method for the Meyer model of cartoon and texture decomposition

In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l₁‐based TV‐norm and an l_∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods.     

On the Number of 4‐Cycles in a Tournament

If T is an n‐vertex tournament with a given number of 3‐cycles, what can be said about the number of its 4‐cycles? The most interesting range of this problem is where T is assumed to have cyclic triples for some and we seek to minimize the number of 4‐cycles. We conjecture that the (asymptotic) minimizing T is a random blow‐up of a constant‐sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of 4‐cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in T, how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments.