Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search

• URL: http://arxiv.org/abs/2207.03343v1
• Date: Mon, 4 Jul 2022 07:06:48 GMT
• Title: Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search
• Authors: Milo Roucairol and Tristan Cazenave
• Abstract summary: We demonstrate how Monte Carlo Search (MCS) algorithms can be used to build graphs and find counter-examples to spectral graph theory conjectures. We refute a conjecture attributed to Peter Shor that was left open.
• Score: 4.38602607138044
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We demonstrate how Monte Carlo Search (MCS) algorithms, namely Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA), can be used to build graphs and find counter-examples to spectral graph theory conjectures in minutes. We also refute a conjecture attributed to Peter Shor that was left open.

Related papers

• Monte Carlo Graph Coloring [3.435169201271934]
  Graph Coloring is probably one of the most studied and famous problem in graph algorithms. We show how to efficiently apply Monte Carlo search to Graph Coloring.
  arXiv  Detail & Related papers  (2025-04-04T08:57:01Z)
• Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms [4.561007128508218]
  The optimized Monte Carlo Tree Search algorithms are PUCT and SHUSS. For small search budgets of 32 evaluations the discovered root exploration terms make both algorithms competitive.
  arXiv  Detail & Related papers  (2024-04-14T17:06:20Z)
• Adaptive Monte Carlo Search for Conjecture Refutation in Graph Theory [0.0]
  Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm.
  arXiv  Detail & Related papers  (2023-06-13T17:54:13Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  We present a novel mechanism to improve the accuracy of graph random features (GRFs) Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs.
  arXiv  Detail & Related papers  (2023-05-21T14:12:02Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling [58.14878401145309]
  We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.
  arXiv  Detail & Related papers  (2022-05-12T11:15:47Z)
• Recursive Monte Carlo and Variational Inference with Auxiliary Variables [64.25762042361839]
  Recursive auxiliary-variable inference (RAVI) is a new framework for exploiting flexible proposals. RAVI generalizes and unifies several existing methods for inference with expressive expressive families. We show RAVI's design framework and theorems by using them to analyze and improve upon Salimans et al.'s Markov Chain Variational Inference.
  arXiv  Detail & Related papers  (2022-03-05T23:52:40Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Antithetic Riemannian Manifold And Quantum-Inspired Hamiltonian Monte Carlo [3.686886131767452]
  We present new algorithms which are antithetic versions of Hamiltonian Monte Carlo and Quantum-Inspired Hamiltonian Monte Carlo. Adding antithetic sampling to Hamiltonian Monte Carlo has been previously shown to produce higher effective sample rates compared to vanilla Hamiltonian Monte Carlo. The analysis is performed on jump diffusion process using real world financial market data, as well as on real world benchmark classification tasks using Bayesian logistic regression.
  arXiv  Detail & Related papers  (2021-07-05T15:03:07Z)
• Measurable Monte Carlo Search Error Bounds [40.29552672672265]
  We prove bounds on the sub-optimality of Monte Carlo estimates for non-stationary bandits and Markov decision processes. These bounds can be directly computed at the conclusion of the search and do not require knowledge of the true action-value.
  arXiv  Detail & Related papers  (2021-06-08T22:20:14Z)
• Annealed Flow Transport Monte Carlo [91.20263039913912]
  Annealed Flow Transport (AFT) builds upon Annealed Importance Sampling (AIS) and Sequential Monte Carlo (SMC) AFT relies on NF which is learned sequentially to push particles towards the successive targets. We show that a continuous-time scaling limit of the population version of AFT is given by a Feynman--Kac measure.
  arXiv  Detail & Related papers  (2021-02-15T12:05:56Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.