Explore the vast range of titles available.

Simulating physical dynamics to solve hard combinatorial optimization has proven effective for medium- to large-scale problems. The dynamics of such systems is continuous, with no guarantee of finding optimal solutions of the original discrete problem. We investigate the open question of when simulated physical solvers solve discrete optimizations correctly, with a focus on coherent Ising machines (CIMs). Having established the existence of an exact mapping between CIM dynamics and discrete Ising optimization, we report two fundamentally distinct bifurcation behaviors of the Ising dynamics at the first bifurcation point: either all nodal states simultaneously deviate from zero (synchronized bifurcation) or undergo a cascade of such deviations (retarded bifurcation). For synchronized bifurcation, we prove that when the nodal states are uniformly bounded away from the origin, they contain sufficient information for exactly solving the Ising problem. When the exact mapping conditions are violated, subsequent bifurcations become necessary and often cause slow convergence. Inspired by those findings, we devise a trapping-and-correction (TAC) technique to accelerate dynamics-based Ising solvers, including CIMs and simulated bifurcation. TAC takes advantage of early bifurcated “trapped nodes” which maintain their sign throughout the Ising dynamics to reduce computation time effectively. Using problem instances from open benchmark and random Ising models, we validate the superior convergence and accuracy of TAC. Physical and physics-inspired computation is emerging as a new paradigm for tackling hard optimization problems. In this work, the authors establish rigorous mathematical conditions together with new design principles for physical as well as simulated dynamical systems to solve general Ising models.

An amendment to this paper has been published and can be accessed via a link at the top of the paper.An amendment to this paper has been published and can be accessed via a link at the top of the paper.

This paper establishes a Markov chain model as a unified framework for describing the evolution processes in complex networks. The unique feature of the proposed model is its capability in addressing the formation mechanism that can reflect the “trichotomy” observed in degree distributions, based on which closed-form solutions can be derived. Important special cases of the proposed unified framework are those classical models, including Poisson, Exponential, Power-law distributed networks. Both simulation and experimental results demonstrate a good match of the proposed model with real datasets, showing its superiority over the classical models. Implications of the model to various applications including citation analysis, online social networks, and vehicular networks design, are also discussed in the paper.

Providing performance reliability in uncertain environments is an important task, yet a crucial challenge, in many engineering problems. Particularly for today’s high speed wireless communication systems (WCSs), obtaining accurate channel state information at the transmitter (CSIT) for scheduler design is a difficult task; hence robust design is of critical concern. In this thesis, we study how to achieve various design objectives in such adverse scenarios by modeling different Chance Constrained Stochastic Optimization (CCSO) problems; in particular, we introduce three novel problems and their corresponding solutions as follows. First we study throughput optimization under heterogeneous delay constraints via our proposed simple queueing theoretical formula for rate equivalence of delay performance. Second we provide distributive implementation and feedback reduction techniques via a statistical tool called extreme value theory. While the first two problems are studied under the classical error distribution model approach, our third contribution proposes a new CCSO framework, which allows one to get rid of the Cumulative Distribution Function (CDF) assumption of the uncertainty. Our approach further provides significant performance enhancement over classical CCSO by introducing an information-adaptive procedure that distinguishes uncertainty into useful information and noise, instead of the single type of uncertainty presented in the existing literature. We focus on demonstrating the applicability of these three solutions through a widely deployed example of a WCS called Orthogonal Frequency Division Multiple Access (OFDMA) system. In particular, we are the first to provide an optimal joint-subcarrier encoding design, with a jointly optimal subcarrier and power allocation which satisfies the outage constraint. Furthermore, both in simulation and theory, we demonstrate the performance enhancements of our schemes over existing CSIT-error inconsiderate schemes, and their capability to provide the aforementioned novel functionality: providing delay constraints satisfaction, distributive design with low feedback overhead, and online design in the absence of CSIT error statistics, without incurring extra complexity, and with convergence proof for the proposed algorithms.

Ising machines, which are dynamical systems designed to operate in a parallel and iterative manner, have emerged as a new paradigm for solving combinatorial optimization problems. Despite computational advantages, the quality of solutions depends heavily on the form of dynamics and tuning of parameters, which are in general set heuristically due to the lack of systematic insights. Here, we focus on optimal Ising machine design by analyzing phase diagrams of spin distributions in the Sherrington-Kirkpatrick model. We find that that the ground state can be achieved in the phase where the spin distribution becomes binary, and optimal solutions are produced where the binary phase and gapless phase coexist. Our analysis shows that such coexistence phase region can be expanded by carefully placing a digitization operation, giving rise to a family of superior Ising machines, as illustrated by the proposed algorithm digCIM.

This paper establishes a Markov chain model as a unified framework for understanding information consumption processes in complex networks, with clear implications to the Internet and big-data technologies. In particular, the proposed model is the first one to address the formation mechanism of the \"trichotomy\" in observed probability density functions from empirical data of various social and technical networks. Both simulation and experimental results demonstrate a good match of the proposed model with real datasets, showing its superiority over the classical power-law models.