IRIS Pol. Torinohttps://iris.polito.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Sun, 22 Sep 2019 18:28:39 GMT2019-09-22T18:28:39Z10231Inference and learning in sparse systems with multiple stateshttp://hdl.handle.net/11583/2439002Titolo: Inference and learning in sparse systems with multiple states
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11583/24390022011-01-01T00:00:00ZStatistical physics approach to graphical games: local and global interactionshttp://hdl.handle.net/11583/2439003Titolo: Statistical physics approach to graphical games: local and global interactions
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11583/24390032011-01-01T00:00:00ZSign problem in the Bethe approximationhttp://hdl.handle.net/11583/2505876Titolo: Sign problem in the Bethe approximation
Abstract: We propose a message-passing algorithm to compute the Hamiltonian expectation with respect to an appropriate class of trial wave functions for an interacting system of fermions. To this end, we connect the quantum expectations to average quantities in a classical system with both local and global interactions, which are related to the variational parameters and use the Bethe approximation to estimate the average energy within the replica-symmetric approximation. The global interactions, which are needed to obtain a good estimation of the average fermion sign, make the average energy a nonlocal function of the variational parameters. We use some heuristic minimization algorithms to find approximate ground states of the Hubbard model on random regular graphs and observe significant qualitative improvements with respect to the mean-field approxi- mation.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/11583/25058762012-01-01T00:00:00ZSimple models of small world networks with directed linkshttp://hdl.handle.net/11583/1905094Titolo: Simple models of small world networks with directed links
Tue, 01 Jan 2002 00:00:00 GMThttp://hdl.handle.net/11583/19050942002-01-01T00:00:00ZMessage passing for quantified Boolean formulashttp://hdl.handle.net/11583/2498002Titolo: Message passing for quantified Boolean formulas
Abstract: We introduce two types of message passing algorithms for quantified Boolean formulas (QBF). The first type is a message passing based heuristics that can prove unsatisfiability of the QBF by assigning the universal variables in such a way that the remaining formula is unsatisfiable. In the second type, we use message passing to guide branching heuristics of a Davis-Putnam Logemann-Loveland (DPLL) complete solver. Numerical experiments show that on random QBFs our branching heuristics gives robust exponential efficiency gain with respect to the state-of-art solvers. We also manage to solve some previously unsolved benchmarks from the QBFLIB library. Apart from this our study sheds light on using message passing in small systems and as subroutines in complete solvers.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/11583/24980022012-01-01T00:00:00ZStatistical Mechanics of Steiner treeshttp://hdl.handle.net/11583/1841213Titolo: Statistical Mechanics of Steiner trees
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11583/18412132008-01-01T00:00:00ZStatistical Mechanics of Maximal Independent Setshttp://hdl.handle.net/11583/2362441Titolo: Statistical Mechanics of Maximal Independent Sets
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11583/23624412009-01-01T00:00:00ZStochastic Matching Problemhttp://hdl.handle.net/11583/2422756Titolo: Stochastic Matching Problem
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11583/24227562011-01-01T00:00:00ZStochastic optimization by message passinghttp://hdl.handle.net/11583/2460655Titolo: Stochastic optimization by message passing
Abstract: Most optimization problems in applied sciences realistically involve uncertainty in the parameters defining the cost function, of which only statistical information is known beforehand. Here we provide an in-depth discussion of how message passing algorithms for stochastic optimization based on the cavity method of statistical physics can be constructed. We focus on two basic problems, namely the independent set problem and the matching problem, for which we display the general method and caveats for the case of the so called two-stage problem with independently distributed stochastic parameters. We compare the results with some greedy algorithms and briefly discuss the extension to more complicated stochastic multi-stage problems.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11583/24606552011-01-01T00:00:00ZStatistical physics and network optimization problemshttp://hdl.handle.net/11583/2617484Titolo: Statistical physics and network optimization problems
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11583/26174842015-01-01T00:00:00Z