A Multivariate Complexity Analysis of Qualitative Reasoning Problems

• URL: http://arxiv.org/abs/2209.15275v1
• Date: Fri, 30 Sep 2022 07:29:53 GMT
• Title: A Multivariate Complexity Analysis of Qualitative Reasoning Problems
• Authors: Leif Eriksson, Victor Lagerkvist
• Abstract summary: We introduce the classes FPE and XE of problems solvable in $f(k) cdot 2O(n)$, respectively $f(k)n$, time. We show that the Partially Ordered Time problem of effective width $k$ is solvable in $16kn$ time and is thus included in XE. We also show that the network consistency problem for Allen's interval algebra with no interval overlapping with more than $k$ others is solvable in $(2nk)2k cdot 2n$ time and is included in
• Score: 9.594432031144716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be solved in $2^{O(n \cdot \log n)}$ time, but single-exponential running times $2^{O(n)}$ are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter $n$ (e.g., the number of variables) and a coarse-grained parameter $k$ expected to be relatively small. We introduce the classes FPE and XE of problems solvable in $f(k) \cdot 2^{O(n)}$, respectively $f(k)^n$, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the Partially Ordered Time problem of effective width $k$ is solvable in $16^{kn}$ time and is thus included in XE, and (2) that the network consistency problem for Allen's interval algebra with no interval overlapping with more than $k$ others is solvable in $(2nk)^{2k} \cdot 2^{n}$ time and is included in FPE. Our multivariate approach is in no way limited to these to specific problems and may be a generally useful approach for obtaining single-exponential algorithms.

Related papers

• Approximating the Number of Relevant Variables in a Parity Implies Proper Learning [0.0]
  We show that approxing the number of relevant variables in the parity function is as hard as properly learning parities. In our second result, we show that from any $T(n)$-time algorithm that, for any parity $f$, returns a $gamma$-approximation of the number of relevant variables $d(f)$ of $f$.
  arXiv  Detail & Related papers  (2024-07-16T15:20:30Z)
• A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) [22.123838452178585]
  We present a running time analysis of strength evolutionary algorithm 2 (SPEA2) for the first time. Specifically, we prove that the expected running time of SPEA2 for solving three commonly used multiobjective problems, i.e., $m$OneMinMax, $m$LeadingOnesZeroes, and $m$-OneZeroJump.
  arXiv  Detail & Related papers  (2024-06-23T14:12:22Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  We show that gradient descent (SGD) can efficiently solve the $k$-parity problem on a $d$dimensional hypercube. We then demonstrate how a trained neural network with SGD, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning [9.594432031144716]
  Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning. We propose a novel framework for solving NP-hard qualitative reasoning problems. We obtain a major improvement of $O*((fraccnlogn)n)$ for Allen's interval algebra.
  arXiv  Detail & Related papers  (2023-05-25T11:45:12Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
  The constraint problem (CSP) has important applications in computer science and AI. A highly successful approach is to bound the treewidth of the underlying primal graph. We improve this bound to $f(w)cdot nO(1)$, for CSPs whose basic relations have patchwork property.
  arXiv  Detail & Related papers  (2021-07-03T13:04:41Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  We give an algorithm for identifying a $k$-mixture using samples of $m=2k$ iid binary random variables. It suffices to know the moments to additive accuracy $w_mincdotzetaO(k)$.
  arXiv  Detail & Related papers  (2020-07-16T04:23:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

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.