The Experts below are selected from a list of 25776 Experts worldwide ranked by ideXlab platform
Marc Mézard - One of the best experts on this subject based on the ideXlab platform.
-
Susceptibility Propagation for Constraint Satisfaction Problems
Journal of Physics, 2010Co-Authors: Saburo Higuchi, Marc MézardAbstract:We study the susceptibility propagation, a message-passing algorithm to compute correlation functions. It is applied to Constraint satisfaction problems and its accuracy is examined. As a heuristic method to find a satisfying assignment, we propose susceptibility-guided decimation where correlations among the variables play an important role. We apply this novel decimation to locked occupation problems, a class of Hard Constraint satisfaction problems exhibited recently. It is shown that the present method performs better than the standard belief-guided decimation.
-
Decimation flows in Constraint satisfaction problems
Journal of Statistical Mechanics: Theory and Experiment, 2009Co-Authors: Saburo Higuchi, Marc MézardAbstract:We study Hard Constraint satisfaction problems with a decimation approach based on message passing algorithms. Decimation induces a renormalization flow in the space of problems, and we exploit the fact that this flow transforms some of the Constraints into linear Constraints over GF(2). In particular, when the flow hits the subspace of linear problems, one can stop decimation and use Gaussian elimination. We introduce a new decimation algorithm which uses this linear structure and shows a strongly improved performance with respect to the usual decimation methods on some of the Hardest locked occupation problems.
-
Constraint satisfaction problems with isolated solutions are Hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic Hardness of the random 'locked' Constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these problems is extremely Hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/Hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really Hard Constraint satisfaction problems.
-
Constraint satisfaction problems and neural networks: a statistical physics perspective
2008Co-Authors: Marc Mézard, Thierry MoraAbstract:A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. In particular, the use of cutting edge statistical physics concepts and methods allow one to solve very large Constraint satisfaction problems like random satisfiability, coloring, or error correction. Several aspects of these developments should be relevant for the understanding of functional complexity in neural networks. On the one hand the message passing procedures which are used in these new algorithms are based on local exchange of information, and succeed in solving some of the Hardest computational problems. On the other hand some crucial inference problems in neurobiology, like those generated in multi-electrode recordings, naturally translate into Hard Constraint satisfaction problems. This paper gives a non-technical introduction to this field, emphasizing the main ideas at work in message passing strategies and their possible relevance to neural networks modeling. It also introduces a new message passing algorithm for inferring interactions between variables from correlation data, which could be useful in the analysis of multi-electrode recording data.
-
Constraint satisfaction problems with isolated solutions are Hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic Hardness of the random `locked' Constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of boolean formulas or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these problems is extremely Hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/Hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really Hard Constraint satisfaction problems.
Ling Shi - One of the best experts on this subject based on the ideXlab platform.
-
learning optimal scheduling policy for remote state estimation under uncertain channel condition
IEEE Transactions on Control of Network Systems, 2020Co-Authors: Xiaoqiang Ren, Qingshan Jia, Karl Henrik Johansson, Ling ShiAbstract:We consider optimal sensor scheduling with unknown communication channel statistics. We formulate two types of scheduling problems with the communication rate being a soft or Hard Constraint, respectively. We first present some structural results on the optimal scheduling policy using dynamic programming and assuming that the channel statistics is known. We prove that the $Q$ -factor is monotonic and submodular, which leads to thresholdlike structures in both problems. Then, we develop a stochastic approximation and parameter learning frameworks to deal with the two scheduling problems with unknown channel statistics. We utilize their structures to design specialized learning algorithms. We, then prove the convergence of these algorithms. Performance improvement compared with the standard $Q$ -learning algorithm is shown through numerical examples, which will also discuss an alternative method based on recursive estimation of the channel quality.
-
learning optimal scheduling policy for remote state estimation under uncertain channel condition
arXiv: Systems and Control, 2018Co-Authors: Xiaoqiang Ren, Qingshan Jia, Karl Henrik Johansson, Ling ShiAbstract:We consider optimal sensor scheduling with unknown communication channel statistics. We formulate two types of scheduling problems with the communication rate being a soft or Hard Constraint, respectively. We first present some structural results on the optimal scheduling policy using dynamic programming and assuming the channel statistics is known. We prove that the Q-factor is monotonic and submodular, which leads to the threshold-like structures in both types of problems. Then we develop a stochastic approximation and parameter learning frameworks to deal with the two scheduling problems with unknown channel statistics. We utilize their structures to design specialized learning algorithms. We prove the convergence of these algorithms. Performance improvement compared with the standard Q-learning algorithm is shown through numerical examples.
Wolfgang Maass - One of the best experts on this subject based on the ideXlab platform.
-
Solving Constraint Satisfaction Problems with Networks of Spiking Neurons.
Frontiers in Neuroscience, 2016Co-Authors: Zeno Jonke, Stefan Habenschuss, Wolfgang MaassAbstract:Network of neurons in the brain apply – unlike processors in our current generation of computer Hardware – an event-based processing strategy, where short pulses (spikes) are emitted sparsely by neurons to signal the occurrence of an event at a particular point in time. Such spike-based computations promise to be substantially more power-efficient than traditional clocked processing schemes. However it turned out to be surprisingly difficult to design networks of spiking neurons that can solve difficult computational problems on the level of single spikes (rather than rates of spikes). We present here a new method for designing networks of spiking neurons via an energy function. Furthermore we show how the energy function of a network of stochastically firing neurons can be shaped in a quite transparent manner by composing the networks of simple stereotypical network motifs. We show that this design approach enables networks of spiking neurons to produce approximate solutions to difficult (NP-Hard) Constraint satisfaction problems from the domains of planning/optimization and verification/logical inference. The resulting networks employ noise as a computational resource. Nevertheless the timing of spikes (rather than just spike rates) plays an essential role in their computations. Furthermore, networks of spiking neurons carry out for the Traveling Salesman Problem a more efficient stochastic search for good solutions compared with stochastic artificial neural networks (Boltzmann machines) and Gibbs sampling.
-
A theoretical basis for efficient computations with noisy spiking neurons
arXiv: Neural and Evolutionary Computing, 2014Co-Authors: Zeno Jonke, Stefan Habenschuss, Wolfgang MaassAbstract:Network of neurons in the brain apply - unlike processors in our current generation of computer Hardware - an event-based processing strategy, where short pulses (spikes) are emitted sparsely by neurons to signal the occurrence of an event at a particular point in time. Such spike-based computations promise to be substantially more power-efficient than traditional clocked processing schemes. However it turned out to be surprisingly difficult to design networks of spiking neurons that are able to carry out demanding computations. We present here a new theoretical framework for organizing computations of networks of spiking neurons. In particular, we show that a suitable design enables them to solve Hard Constraint satisfaction problems from the domains of planning - optimization and verification - logical inference. The underlying design principles employ noise as a computational resource. Nevertheless the timing of spikes (rather than just spike rates) plays an essential role in the resulting computations. Furthermore, one can demonstrate for the Traveling Salesman Problem a surprising computational advantage of networks of spiking neurons compared with traditional artificial neural networks and Gibbs sampling. The identification of such advantage has been a well-known open problem.
Xiaoqiang Ren - One of the best experts on this subject based on the ideXlab platform.
-
learning optimal scheduling policy for remote state estimation under uncertain channel condition
IEEE Transactions on Control of Network Systems, 2020Co-Authors: Xiaoqiang Ren, Qingshan Jia, Karl Henrik Johansson, Ling ShiAbstract:We consider optimal sensor scheduling with unknown communication channel statistics. We formulate two types of scheduling problems with the communication rate being a soft or Hard Constraint, respectively. We first present some structural results on the optimal scheduling policy using dynamic programming and assuming that the channel statistics is known. We prove that the $Q$ -factor is monotonic and submodular, which leads to thresholdlike structures in both problems. Then, we develop a stochastic approximation and parameter learning frameworks to deal with the two scheduling problems with unknown channel statistics. We utilize their structures to design specialized learning algorithms. We, then prove the convergence of these algorithms. Performance improvement compared with the standard $Q$ -learning algorithm is shown through numerical examples, which will also discuss an alternative method based on recursive estimation of the channel quality.
-
learning optimal scheduling policy for remote state estimation under uncertain channel condition
arXiv: Systems and Control, 2018Co-Authors: Xiaoqiang Ren, Qingshan Jia, Karl Henrik Johansson, Ling ShiAbstract:We consider optimal sensor scheduling with unknown communication channel statistics. We formulate two types of scheduling problems with the communication rate being a soft or Hard Constraint, respectively. We first present some structural results on the optimal scheduling policy using dynamic programming and assuming the channel statistics is known. We prove that the Q-factor is monotonic and submodular, which leads to the threshold-like structures in both types of problems. Then we develop a stochastic approximation and parameter learning frameworks to deal with the two scheduling problems with unknown channel statistics. We utilize their structures to design specialized learning algorithms. We prove the convergence of these algorithms. Performance improvement compared with the standard Q-learning algorithm is shown through numerical examples.
Lenka Zdeborova - One of the best experts on this subject based on the ideXlab platform.
-
Constraint satisfaction problems with isolated solutions are Hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic Hardness of the random 'locked' Constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these problems is extremely Hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/Hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really Hard Constraint satisfaction problems.
-
Random subcubes as a toy model for Constraint satisfaction problems
Journal of Statistical Physics, 2008Co-Authors: Thierry Mora, Lenka ZdeborovaAbstract:We present an exactly solvable random-subcube model inspired by the structure of Hard Constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.
-
Constraint satisfaction problems with isolated solutions are Hard
Journal of Statistical Mechanics: Theory and Experiment, 2008Co-Authors: Lenka Zdeborova, Marc MézardAbstract:We study the phase diagram and the algorithmic Hardness of the random `locked' Constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of boolean formulas or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these problems is extremely Hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/Hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really Hard Constraint satisfaction problems.
