Computer Vision (CV) labeling problems play a pivotal role in low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy-minimization problems derived from probabilistic graphical models such as Markov Random Fields (MRFs). Despite recent advances in MRF inference algorithms (such as graph-cut and message-passing methods), the resulting energy-minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), hoping to provide a credible alternative/assistant to deep learning solutions. This study investigates a new Quantum Annealing-based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum–classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature. Our results show that Quantum Annealing can yield promising results for Stereo Matching problems, with improved accuracy on certain stereo images and competitive performance on others.

A physical system is determined by a finite set of initial conditions and “laws” represented by equations. The system is computable if we can solve the equations in all instances using a “finite body of mathematical knowledge”. In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30–40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.

Many membrane systems (e.g. P System), including cP systems (P Systems with compound terms), have been used to solve efficiently many NP-hard problems, often in linear time. However, these solutions have been independent of each other and have not utilised the theory of reductions. This work presents a sublinear solution to k-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time. This work demonstrates that traditional reductions are efficient in cP systems and that they can sometimes produce more efficient solutions than the previous problem-specific solutions.

Nondeterminism in neural network optimization produces uncertainty in performance, making small improvements difficult to discern from run-to-run variability. While uncertainty can be reduced by training multiple model copies, doing so is time-consuming, costly, and harms reproducibility. In this work, we establish an experimental protocol for understanding the effect of optimization nondeterminism on model diversity, allowing us to isolate the effects of a variety of sources of nondeterminism. Surprisingly, we find that all sources of nondeterminism have similar effects on measures of model diversity. To explain this intriguing fact, we identify the instability of model training, taken as an end-to-end procedure, as the key determinant. We show that even one-bit changes in initial parameters result in models converging to vastly different values. Last, we propose two approaches for reducing the effects of instability on run-to-run variability.

This paper proposes an efficient method for the weighted region problem (WRP) on the surface of three-dimensional terrains. WRP is a classical path planning problem, asking for the minimum cost path between two given points crossing different regions in which each region is assigned a traversal cost per unit distance. Although WRP has been studied for decades, the exact solution for WRP, even in a two-dimensional environment, is unknown. Thus, the existing solutions for WRP are all approximations with decomposition-based and heuristic methods being the most widely-used in practice. However, when a very-close to optimal path is required, especially on real terrains with many regions, these approaches are not guaranteed or cannot return a satisfactory result in reasonable time. In this paper, we first present a new algorithm of finding a very-close optimal path, based on a user-defined parameter δ, between two points, crossing the surface of a sequence of regions in 3D, using Snell's law of physical refraction. We then show how to combine this algorithm with one existing decomposition-based method to compute a close optimal path over the whole terrain. In addition to a theoretical analysis, with an extensive set of test cases, the practicality and feasibility of our method are confirmed by that, our method always runs faster and returns closer to optimal paths in comparison with the existing ones.

In order to reduce overfitting, neural networks are typically trained with data augmentation, the practice of artificially generating additional training data via label-preserving transformations of existing training examples. While these types of transformations make intuitive sense, recent work has demonstrated that even non-label-preserving data augmentation can be surprisingly effective, examining this type of data augmentation through linear combinations of pairs of examples. Despite their effectiveness, little is known about why such methods work. In this work, we aim to explore a new, more generalized form of this type of data augmentation in order to determine whether such linearity is necessary. By considering this broader scope of "mixed-example data augmentation", we find a much larger space of practical augmentation techniques, including methods that improve upon previous state-of-the-art. This generalization has benefits beyond the promise of improved performance, revealing a number of types of mixed-example data augmentation that are radically different from those considered in prior work, which provides evidence that current theories for the effectiveness of such methods are incomplete and suggests that any such theory must explain a much broader phenomenon.

A Memetic Algorithm is an Evolutionary Algorithm augmented with local searches. The dynamic mutation approach has been studied extensively in experiments of Memetic Algorithms, but only a few studies in theory. We previously defined a metric BLOCKONES to estimate the difficulty of escaping from a local optima, and showed that the algorithm's ability of escaping from a local optima, that has a large BLOCKONES, is very important, because it dominates the time complexity of finding a global optimal solution. In this paper, we will use the same metric and show the benefits of hybridizing the dynamic mutation approach with one of two local searches, best-improvement and first-improvement. In short, this hybridization greatly enhances the algorithm's ability to escape from any local optima.

It is commonly accepted that a proper fitness function can guide the algorithm to find a global optimum solution faster. This paper will use the runtime analysis to provide the theoretical evidence that a small change of the fitness function (additional one step looking forward) can result in a huge performance gap in terms of finding a global optimum solution. It also shows that the fitness function that gives the best results in an Memetic Algorithm on the Clique Problem is entirely instance specific. In detail, we will formalize a (1+1) Restart Memetic Algorithm with a Best-Improvement Local Search, and run them on two different fitness functions, fOLand fOPL, to solve the Clique Problem respectively. We then construct two families of graphs, G1and G2, and show that, for the first family of graphs G1, the (1+1) RMA on the fitness function fOPLdrastically outperforms the (1+1) RMA on the fitness function fOL, and vice versa for the second family of graphs G2.

In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm (MA) to solve one problem (a single fitness function), has been verified in many successful experiments. These experiments also give the observation that the local search operator that gives the best results in an MA on the same fitness function for solving a NP-hard problem is instance specific. This paper will pro- vide a theoretical evidence for this observation. In this pa- per, we will formalize the (1+1) Restart Memetic Algorithms applying two different local searches, the first-improvement and the best-improvement, respectively. We will then run them on a single fitness function to solve the Clique Prob- lem. We then show that there are two families of graphs such that, for the first family of graphs, MAs with one local search drastically outperform MAs with the other local search, and vice versa for the second family of graphs. Our study explains why using multiple local searches can outperform using a single local search in Memetic Algorithms.

A memetic algorithm (MA) is an Evolutionary Algorithm (EA) augmented with a local search. We previously defined a (1+1) Adaptive Memetic Algorithm (AMA) with two different local searches, and the comparison with the well-known (1+1) EA, Dynamic (1+1) EA and (1+1) MA on some toy functions showed promise for our proposed algorithm. In this paper we focus on the NP-hard Maximum Clique Problem, and show the success of our proposed (1+1) AMA. We propose a new metric (expected running time to escape a local optimal), and show how this metric dominates the expected running time of finding a maximum clique. Then based on this new metric, we show the above analyzed algorithms are expected to find a maximum clique on graphs, bipartite graphs and sparse random graphs in a polynomial time in the number of vertices. Also based on our new metric, we will show that if an algorithm takes an exponential time to find a maximum clique of a graph, it must have been trapped into at least one local optimal that is extremely hard to escape. Furthermore, we will show that our proposed (1+1) AMA with a random permutation local search is expected to escape these (hard to escape) local optimal cliques drastically faster than the well-known basic (1+1) EA. The success of our experimental results also shows the benefit of our adaptive strategy combined with the random permutation local search.

Abstract We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. This paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks. © 2002 Wiley Periodicals, Inc.

Abstract The results of computer searches for large graphs with given (small) degree and diameter are presented. The new graphs are Cayley graphs of semidirect products of cyclic groups and related groups. One fundamental use of our “dense graphs” is in the design of efficient communication network topologies. © 1994 by John Wiley & Sons, Inc.

A report is presented on a collection of constructions of symmetric networks that provide the largest known values for the number of nodes that can be placed in a network of a given degree and diameter. Some of the constructions are in the range of current potential engineering significance. The constructions are Cayley graphs of linear groups obtained by experimental computation.>