惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

小众软件
小众软件
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
WordPress大学
WordPress大学
月光博客
月光博客
Hugging Face - Blog
Hugging Face - Blog
博客园 - 聂微东
博客园 - 【当耐特】
博客园_首页
The Cloudflare Blog
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Apple Machine Learning Research
Apple Machine Learning Research
Last Week in AI
Last Week in AI
酷 壳 – CoolShell
酷 壳 – CoolShell
大猫的无限游戏
大猫的无限游戏
雷峰网
雷峰网
量子位
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
T
Tailwind CSS Blog
IT之家
IT之家
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
GbyAI
GbyAI
V
Visual Studio Blog
F
Fortinet All Blogs
Martin Fowler
Martin Fowler

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Improved Algorithms for the General Exact Satisfiability ...
Gordon Hoi, Frank Stephan · 2021-01-21 · via cs.DS updates on arXiv.org

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned $1$, while the rest are all assigned $0$. We can generalise this problem further by defining that a $C^j$ clause is solved iff exactly $j$ of the literals in the clause are $1$ and all others are $0$. We now introduce the family of Generalised Exact Satisfiability problems called G$i$XSAT as the problem to check whether a given instance consisting of $C^j$ clauses with $j \in \{0,1,\ldots,i\}$ for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G$i$XSAT, for $i\in \{2,3,4\}$, in $O(1.3674^n)$ time, $O(1.5687^n)$ time and $O(1.6545^n)$ time, respectively, using polynomial space, where $n$ is the number of variables. This improves the current state of the art for polynomial space algorithms from $O(1.4203^n)$ time for G$2$XSAT by Zhou, Jiang and Yin and from $O(1.6202^n)$ time for G$3$XSAT by Dahllöf and from $O(1.6844^n)$ time for G$4$XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G$2$XSAT, G$3$XSAT and G$4$XSAT in $O(1.3188^n)$ time, $O(1.3407^n)$ time and $O(1.3536^n)$ time respectively at the expense of using exponential space.