| 1. |
- Rydving, Erik, et al.
(författare)
-
Do Gedanken experiments compel quantization of gravity?
- 2021
-
Ingår i: Physical Review D. - : American Physical Society (APS). - 2470-0010 .- 2470-0029. ; 104:8
-
Tidskriftsartikel (refereegranskat)abstract
- Whether gravity is quantized remains an open question. To shed light on this problem, various Gedanken experiments have been proposed. One popular example is an interference experiment with a massive system that interacts gravitationally with another distant system, where an apparent paradox arises: even for spacelike separation the outcome of the interference experiment depends on actions on the distant system, leading to a violation of either complementarity or no-signaling. A recent resolution shows that the paradox is avoided when quantizing gravitational radiation and including quantum fluctuations of the gravitational field. Here we show that the paradox in question can also be resolved without considering gravitational radiation, relying only on the Planck length as a limit on spatial resolution. Therefore, in contrast to conclusions previously drawn, we find that the necessity for a quantum field theory of gravity does not follow from so far considered Gedanken experiments of this type. In addition, we point out that in the common realization of the setup the effects are governed by the mass octopole rather than the quadrupole. Our results highlight that no Gedanken experiment to date compels a quantum field theory of gravity, in contrast to the electromagnetic case.
|
|
| 2. |
- Alava, Mikko, et al.
(författare)
-
Circumspect descent prevails in solving random constraint satisfaction problems
- 2008
-
Ingår i: Proceedings of the National Academy of Sciences of the United States of America. - : Proceedings of the National Academy of Sciences. - 0027-8424 .- 1091-6490. ; 105:40, s. 15253-15257
-
Tidskriftsartikel (refereegranskat)abstract
- We study the performance of stochastic local search algorithms for random instances of the K-satisfiability (K-SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large K-SAT instances almost surely in linear time, up to high clause-to-variable ratios a; for example, for K = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.
|
|
| 3. |
- Ameur, Adam, et al.
(författare)
-
Global gene expression analysis by combinatorial optimization
- 2004
-
Ingår i: In Silico Biology. - 1386-6338. ; 4
-
Tidskriftsartikel (refereegranskat)abstract
- Generally, there is a trade-off between methods of gene expression analysis that are precise but labor-intensive, e.g. RT-PCR, and methods that scale up to global coverage but are not quite as quantitative, e.g. microarrays. In the present paper, we show how how a known method of gene expression profiling (K. Kato, Nucleic Acids Res. 23, 3685-3690 (1995)), which relies on a fairly small number of steps, can be turned into a global gene expression measurement by advanced data post-processing, with potentially little loss of accuracy. Post-processing here entails solving an ancillary combinatorial optimization problem. Validation is performed on in silico experiments generated from the FANTOM data base of full-length mouse cDNA. We present two variants of the method. One uses state-of-the-art commercial software for solving problems of this kind, the other a code developed by us specifically for this purpose, released in the public domain under GPL license.
|
|
| 4. |
- Ardelius, John, et al.
(författare)
-
Behavior of heuristics on large and hard satisfiability problems
- 2006
-
Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. - 1063-651X .- 1095-3787. ; 74:3, s. 037702-
-
Tidskriftsartikel (refereegranskat)abstract
- We study the behavior of a heuristic for solving random satisfiability problems by stochastic local search near the satisfiability threshold. The heuristic for average satisfiability (ASAT), is similar to the Focused Metropolis Search heuristic, and shares the property of being focused, i.e., only variables in unsatisfied clauses are updated in each step. It is significantly simpler than the benchmark WALKSAT heuristic. We show that ASAT solves instances as large as N=10(6) in linear time, on average, up to a ratio of 4.21 clauses per variable in random three-satisfiability. For K higher than 3, ASAT appears to solve instances of K-satisfiability up to the Montanari-Ricci-Tersenghi-Parisi full replica symmetry breaking (FSRB) threshold denoted alpha(s)(K) in linear time.
|
|
| 5. |
- Ardelius, John, et al.
(författare)
-
Clustering of solutions in hard satisfiability problems
- 2007
-
Ingår i: Journal of Statistical Mechanics: Theory and Experiment. - 1742-5468. ; :10, s. P10012-
-
Tidskriftsartikel (refereegranskat)abstract
- We study numerically the solution space structure of random 3-SAT problems close to the SAT/UNSAT transition. This is done by considering chains of satisfiability problems, where clauses are added sequentially to a problem instance. Using the overlap measure of similarity between different solutions found on the same problem instance, we examine geometrical changes as a function of α. In each chain, the overlap distribution is first smooth, but then develops a tiered structure, indicating that the solutions are found in well separated clusters. On chains of not too large instances, all remaining solutions are eventually observed to be found in only one small cluster before vanishing. This condensation transition point is estimated by finite size scaling to be αc = 4.26 with an apparent critical exponent of about 1.7. The average overlap value is also observed to increase with α up to the transition, indicating a reduction in solutions space size, in accordance with theoretical predictions. The solutions are generated by a local heuristic, ASAT, and compared to those found by the Survey Propagation algorithm up to αc.
|
|
| 6. |
- Ardelius, John, 1978-
(författare)
-
On state space structure and average case complexity in random K-SAT problems
- 2008
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and theoretical physics. In the last ten years it has been suggested that critical behaviour, usually seen in models from condensed matter physics, may be responsible for the intractability of NP complete computation problems. This would suggest a very deep connection between the two fields on the most fundamental level. How deep this connection really is is subject to ongoing research as well as the topic of this thesis. Some of the conjectrues from the physics community regarding computational hardness in certain problem classes has turned out to be wrong or misinterpreted but the gained interest in both fields has promising potiential in moving the research frontier forward. The material presented in this thesis is the result of nearly two years work in trying to clearify how the results from physics can be interpreted in the language of actuall computation problems.
|
|
| 7. |
- Aurell, Erik, et al.
(författare)
-
A Cavity Master Equation for the continuous time dynamics of discrete spins models
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We present a new method to close the Master Equation representing the continuous time dynamics of Ising interacting spins. The method makes use of the the theory of Random Point Processes to derive a master equation for local conditional probabilities. We analytically test our solution studying two known cases, the dynamics of the mean field ferromagnet and the dynamics of the one dimensional Ising system. We then present numerical results comparing our predictions with Monte Carlo simulations in three different models on random graphs with finite connectivity: the Ising ferromagnet, the Random Field Ising model, and the Viana-Bray spin-glass model.
|
|
| 8. |
- Aurell, Erik, et al.
(författare)
-
A closure for the master equation starting from the dynamic cavity method
- 2023
-
Ingår i: Journal of Physics A. - : IOP Publishing. - 1751-8113 .- 1751-8121. ; 56:17
-
Tidskriftsartikel (refereegranskat)abstract
- We consider classical spin systems evolving in continuous time with interactions given by a locally tree-like graph. Several approximate analysis methods have earlier been reported based on the idea of Belief Propagation / cavity method. We introduce a new such method which can be derived in a more systematic manner using the theory of Random Point Processes. Within this approach, the master equation governing the system's dynamics is closed via a set of differential equations for the auxiliary cavity probabilities. The numerical results improve on the earlier versions of the closure on several important classes of problems. We re-visit here the cases of the Ising ferromagnet and the Viana-Bray spin-glass model.
|
|
| 9. |
- Aurell, Erik, et al.
(författare)
-
A message-passing scheme for non-equilibrium stationary states
- 2011
-
Ingår i: JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT. - 1742-5468. ; , s. P04014-
-
Tidskriftsartikel (refereegranskat)abstract
- We study stationary states in a diluted asymmetric (kinetic) Ising model. We apply the recently introduced dynamic cavity method to compute magnetizations of these stationary states. Depending on the update rule, different versions of the dynamic cavity method apply. We here study synchronous updates and random sequential updates, and compare local properties computed by the dynamic cavity method to numerical simulations. Using both types of updates, the dynamic cavity method is highly accurate at high enough temperatures. At low enough temperatures, for sequential updates the dynamic cavity method tends to a fixed point, but this does not agree with numerical simulations, while for parallel updates, the dynamic cavity method may display oscillatory behavior. When it converges and is accurate, the dynamic cavity method offers a huge speed-up compared to Monte Carlo, particularly for large systems.
|
|
| 10. |
- Aurell, Erik, et al.
(författare)
-
A physics-style approach to scalability of distributed systems
- 2005
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 3267, s. 266-272
-
Tidskriftsartikel (refereegranskat)abstract
- Is it possible to treat large scale distributed systems as physical systems? The importance of that question stems from the fact that the behavior of many P2P systems is very complex to analyze analytically, and simulation of scales of interest can be prohibitive. In Physics, however, one is accustomed to reasoning about large systems. The limit of very large systems may actually simplify the analysis. As a first example, we here analyze the effect of the density of populated nodes in an identifier space in a P2P system. We show that while the average path length is approximately given by a function of the number of populated nodes, there is a systematic effect which depends on the density. In other words, the dependence is both on the number of address nodes and the number of populated nodes, but only through their ratio. Interestingly, this effect is negative for finite densities, showing that an amount of randomness somewhat shortens average path length.
|
|
