We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses rounds of communication and messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by notation, revealing that advances are needed to render both the quantum and classical algorithms practical.
Stable subordinators, and more general subordinators possessing power law probability tails, have been widely used in the context of subdiffusions, where particles get trapped or immobile in a number of time periods, called constant periods. The lengths of the constant periods follow a one-sided distribution which involves a parameter between 0 and 1 and whose first moment does not exist. This paper constructs an estimator for the parameter, applying the method of moments to the number of observed constant periods in a fixed time interval. The resulting estimator is asymptotically unbiased and consistent, and it is well-suited for situations where multiple observations of the same subdiffusion process are available. We present supporting numerical examples and an application to market price data for a low-volume stock.
MATEK-Multi-Agent Theorem Exploration through Knowledge-Graph Memory-is a local command-line orchestration framework for research-level mathematics, designed around humanexplorable persistent mathematical knowledge. AI research sessions often end without a complete solution, leaving partial results, promising ideas, counterexamples, and failed approaches stranded in individual transcripts, and even if a solution was reached the process of how it was reached may be obscure. MATEK instead organizes this work in a typed, project-scoped knowledge graph that survives runs and provider sessions, that can be explored by human researchers using the Obsidian software. The graph links claims, proofs, approaches, tasks, sources, audits, and formalizations, and supplies later agents with an explicit research frontier to build off of. Furthermore, MATEK turns a short problem statement into a sophisticated prompt for a research orchestrator agent, following structures used in recent successful AI-assisted mathematics. The orchestrator makes use of sub-agents that add their contributions to the knowledge graph. Candidate solutions are independently audited, and formalized in Lean if the audits pass. This report describes the implemented methodology. It does not present a controlled evaluation of mathematical discovery performance, and it does not claim that model-generated proofs are reliable merely because the workflow is elaborate. The framework is intended to make a promising prompting and orchestration pattern persistent, human-inspectable, and extensible.
1 September 2020 in Statistics & Probability Letters