arXiv research

The Boolean Satisfiability (SAT) problem is the canonical NP-complete problem and is fundamental to computer science, with a wide array of applications in planning, verification, and theorem proving. Developing and evaluating practical SAT solvers relies on extensive empirical testing on a set of real-world benchmark f…

Neuro# learns heuristics to speed up #SAT solvers.

Learning β for k-SAT with one sample is hard, especially for low degrees.

Many optimization problems can be cast into the maximum satisfiability (MAX-SAT) form, and many solvers have been developed for tackling such problems. To evaluate a MAX-SAT solver, it is convenient to generate hard MAX-SAT instances with known solutions. Here, we propose a method of generating weighted MAX-2-SAT insta…

SAT improves adversarial training by smoothing the loss landscape through curriculum learning.

Variance plays a crucial role in risk-sensitive reinforcement learning, and most risk measures can be analyzed via variance. In this paper, we consider two law-invariant risks as examples: mean-variance risk and exponential utility risk. With the aid of the state-augmentation transformation (SAT), we show that, the two…

Single sample estimation for hard-constrained models like SAT and coloring problems.

New study shows low-degree polynomial algorithms struggle at clause densities close to Fix's.

New algorithms boost SAT solver performance by optimizing restart strategies.

Hybrid LLM and quantum optimization improve CSA collateral management by 9-10%.

Estimates inverse temperature of Ising models with a single sample.

UCBVI-γ algorithm minimizes regret in discounted MDPs.

We show that {\sc Heegaard Genus $\leq g$}, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to $g$, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {\sc CNF-SAT} to {\sc Heegaard Genus $\leq g$}.

A new adaptive binarization technique using fuzzy integrals improves image quality.

There have been recent efforts for incorporating Graph Neural Network models for learning full-stack solvers for constraint satisfaction problems (CSP) and particularly Boolean satisfiability (SAT). Despite the unique representational power of these neural embedding models, it is not clear how the search strategy in th…

New algorithm optimizes beam and rate allocation in mmWave systems for multiple users.

Improved robustness in ASR systems with speaker adaptation.

Survival strategy for crypto firms in bear markets using BTC-to-sats payments rail.

A new RL framework allows removing user data without affecting performance.

We give a simple optimistic algorithm for which it is easy to derive regret bounds of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformly ergodic Markov decision processes with $S$ states, $A$ actions, and mixing time parameter $t_{\rm mix}$. These bounds are the first regret bounds in the general, non-epi…

Perhaps surprisingly, it is possible to predict how long an algorithm will take to run on a previously unseen input, using machine learning techniques to build a model of the algorithm's runtime as a function of problem-specific instance features. Such models have important applications to algorithm analysis, portfolio…

Develops a learning algorithm for PSL formulas from examples.

In this work we establish the tightest lower bound up-to-date for the minimal crossing number of a satellite knot based on the minimal crossing number of the companion used to build the satellite. If $M$ is the wrapping number of the pattern knot, we essentially show that $c(Sat(P,C))>\frac{M^2}{2}c(C)$. The existence …

It is feasible and practically-valuable to bridge the characteristics between graph neural networks (GNNs) and logical reasoning. Despite considerable efforts and successes witnessed to solve Boolean satisfiability (SAT), it remains a mystery of GNN-based solvers for more complex predicate logic formulae. In this work,…

New algorithms reduce risk in reinforcement learning with provable regret bounds.

This is a report on our ongoing research on a combinatorial approach to knot recognition, using coloring of knots by certain algebraic objects called quandles. The aim of the paper is to summarize the mathematical theory of knot coloring in a compact, accessible manner, and to show how to use it for computational purpo…

Computational results demonstrate that posterior sampling for reinforcement learning (PSRL) dramatically outperforms algorithms driven by optimism, such as UCRL2. We provide insight into the extent of this performance boost and the phenomenon that drives it. We leverage this insight to establish an $\tilde{O}(H\sqrt{SA…

A quantum framework optimizes collateral allocation for derivatives.

New lower bound shows RL with linear approximations is computationally hard.

The average shadowing property is considered for set-valued dynamical systems, generated by parameterized IFS, which are uniformly contracting, or conjugacy, or products of such ones. We also prove that if a continuous surjective IFS F on a compact metric space X has the aver- age shadowing property, then every point x…

In order to make good decision under uncertainty an agent must learn from observations. To do so, two of the most common frameworks are Contextual Bandits and Markov Decision Processes (MDPs). In this paper, we study whether there exist algorithms for the more general framework (MDP) which automatically provide the bes…

Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and …

Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer $Ω(\sqrt{SAT})$ regret on some MDP, where $T$ is the elapsed time and $S$ and $A$ are the cardinalities of the state and action spaces. This implies $T = Ω(SA)$ time to guarantee a near-optimal policy. In many settings…

Survey on automating geometry problem solving with large models.

Logarithmic regret achieved in Q-learning with positive gap.

Refines neural network predictions using background knowledge for improved accuracy.

Understanding properties of deep neural networks is an important challenge in deep learning. In this paper, we take a step in this direction by proposing a rigorous way of verifying properties of a popular class of neural networks, Binarized Neural Networks, using the well-developed means of Boolean satisfiability. Our…

We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a r…

Improves algorithm selection for thousands of candidates using dyadic features.

Continuous optimization is an important problem in many areas of AI, including vision, robotics, probabilistic inference, and machine learning. Unfortunately, most real-world optimization problems are nonconvex, causing standard convex techniques to find only local optima, even with extensions like random restarts and …

Paper proposes new $γ$-regret measure for non-episodic RL.

RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.

New algorithm reduces RL policy optimization gap.

Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment. They are typically simpler, more flexible to use, and thus more prevalent in modern deep RL than model-based approaches. However, empirical wor…

In the field of exploratory data mining, local structure in data can be described by patterns and discovered by mining algorithms. Although many solutions have been proposed to address the redundancy problems in pattern mining, most of them either provide succinct pattern sets or take the interests of the user into acc…

Generally speaking, the goal of constructive learning could be seen as, given an example set of structured objects, to generate novel objects with similar properties. From a statistical-relational learning (SRL) viewpoint, the task can be interpreted as a constraint satisfaction problem, i.e. the generated objects must…

New concept of regular separation for ODEs leads to improved Hardy field results.

Transformer learns graph structure better with subgraph info.