A Fast Algorithm for Consistency Checking Partially Ordered Time
- URL: http://arxiv.org/abs/2305.15917v1
- Date: Thu, 25 May 2023 10:36:49 GMT
- Title: A Fast Algorithm for Consistency Checking Partially Ordered Time
- Authors: Leif Eriksson and Victor Lagerkvist
- Abstract summary: We consider the problem of deciding if a (likely incomplete) description of a system of events is consistent.
While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT.
We construct a much faster algorithm with a run-time bounded by $O*((0.26n)n)$.
- Score: 9.594432031144716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Partially ordered models of time occur naturally in applications where agents
or processes cannot perfectly communicate with each other, and can be traced
back to the seminal work of Lamport. In this paper we consider the problem of
deciding if a (likely incomplete) description of a system of events is
consistent, the network consistency problem for the point algebra of partially
ordered time (POT). While the classical complexity of this problem has been
fully settled, comparably little is known of the fine-grained complexity of POT
except that it can be solved in $O^*((0.368n)^n)$ time by enumerating ordered
partitions. We construct a much faster algorithm with a run-time bounded by
$O^*((0.26n)^n)$. This is achieved by a sophisticated enumeration of structures
similar to total orders, which are then greedily expanded toward a solution.
While similar ideas have been explored earlier for related problems it turns
out that the analysis for POT is non-trivial and requires significant new
ideas.
Related papers
- Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
In practical distributed systems, workers typically not homogeneous, and can have highly varying processing times.
We introduce a new parallel method Freya to handle arbitrarily slow computations.
We show that Freya offers significantly improved complexity guarantees compared to all previous methods.
arXiv Detail & Related papers (2024-05-24T13:33:30Z) - EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
We present EKM: a novel algorithm for solving this problem exactly with worst-case $Oleft(NK+1right)$ complexity.
EKM is developed according to recent advances in transformational programming and generation, using formal program steps.
We show that the wall-clock run time of our algorithm matches the worst-case time complexity analysis on synthetic datasets.
arXiv Detail & Related papers (2024-05-16T15:11:37Z) - Scalable network reconstruction in subquadratic time [0.0]
We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline.
Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability.
We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
arXiv Detail & Related papers (2024-01-02T19:00:13Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models.
A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters.
We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
arXiv Detail & Related papers (2023-10-05T07:10:40Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.
Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
arXiv Detail & Related papers (2023-02-16T13:57:19Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization.
We provide novel excess risk bounds, both in expectation and with high probability.
Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
arXiv Detail & Related papers (2022-11-03T12:40:24Z) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Dihedral Coset Problem (DCP) in $Z_N$ has been extensively studied in quantum computing and post-quantum cryptography.
Ettinger-Hoyer algorithm is known to solve the DCP in $O(log(N))$ queries.
We introduce the first algorithm to improve in the linear queries regime over the Ettinger-Hoyer algorithm.
arXiv Detail & Related papers (2022-06-29T05:30:54Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$.
We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
arXiv Detail & Related papers (2021-03-03T22:42:15Z) - Distributed Stochastic Consensus Optimization with Momentum for
Nonconvex Nonsmooth Problems [45.88640334610308]
This paper presents a new distributed optimization algorithm for non-smooth problems.
We show that the proposed algorithm can achieve an overcal communication.
Experiments are presented to illustrate the effectiveness of the proposed algorithms.
arXiv Detail & Related papers (2020-11-10T13:12:21Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
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.