We introduce an efficient message passing scheme for solving Constraint Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief Propagation (BP) and Survey Propagation (SP) messages to bypass decimation and directly produce a single satisfying assignment. Our first CSP solver, called Perturbed Blief …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
22 results for “CSP”
New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
This paper presents a new approach for training artificial neural networks using techniques for solving the constraint satisfaction problem (CSP). The quotient gradient system (QGS) is a trajectory-based method for solving the CSP. This study converts the training set of a neural network into a CSP and uses the QGS to …
Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscond-mat.dis-nn
We introduce a novel Entropy-driven Monte Carlo (EdMC) strategy to efficiently sample solutions of random Constraint Satisfaction Problems (CSPs). First, we extend a recent result that, using a large-deviation analysis, shows that the geometry of the space of solutions of the Binary Perceptron Learning Problem (a proto…
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…
The electroencephalogram (EEG) is the most popular form of input for brain computer interfaces (BCIs). However, it can be easily contaminated by various artifacts and noise, e.g., eye blink, muscle activities, powerline noise, etc. Therefore, the EEG signals are often filtered both spatially and temporally to increase …
Background: In cognitive neuroscience the potential of Deep Neural Networks (DNNs) for solving complex classification tasks is yet to be fully exploited. The most limiting factor is that DNNs as notorious 'black boxes' do not provide insight into neurophysiological phenomena underlying a decision. Layer-wise Relevance …
CSP improves time-series forecasting without training, outperforming DeepNPTS in speed and accuracy.
problem Improving probabilistic time-series forecasting without training.
method Mixing empirical and residual draws around a seasonal naive forecast.
result CSP significantly outperforms DeepNPTS on CRPS, normalized mean quantile loss, and coverage metrics.
Recently, there have been several progresses for the conjugacy search problem (CSP) in Garside groups, especially in braid groups. All known algorithms for solving this problem use a sort of exhaustive search in a particular finite set such as the super summit set and the ultra summit set. Their complexities are propor…
Of all real Lagrangian--Grassmannians , only admits a distinguished (Lorentzian) conformal structure and hence is identified with the indefinite M\"obius space . Using Cartan's method of moving frames, we study hyperbolic (timelike) surfaces in modulo the conformal symplectic gro…
This paper is the second in a series in which the authors study the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in Garside groups. The ultra summit set USS(X) of an element X in a Garside group G is a finite set of elements in G, introduced by the second author, which is a complete invariant…
In this paper a relation between iterated cyclings and iterated powers of elements in a Garside group is shown. This yields a characterization of elements in a Garside group having a rigid power, where 'rigid' means that the left normal form changes only in the obvious way under cycling and decycling. It is also shown …
Efficient Subsampling of Realistic Images From GANs Conditional on a Class or a Continuous Variablecs.CV
This work introduces an efficient method to sample high-quality images from conditional GANs.
problem Efficient subsampling of images from conditional GANs (cGANs) is challenging.
method Developed a novel conditional density ratio estimation method (cDRE-F-cSP) and rejection sampling scheme (cDR-RS).
result cDR-RS outperforms state-of-the-art methods in both effectiveness and efficiency.
Novel deep learning architecture decodes imagined speech from EEG.
problem Insufficient training samples for deep learning in decoding imagined speech.
method Employed a novel deep learning architecture with CSP for feature selection, DWT for feature extraction, and majority voting for classification.
result Achieved accuracies comparable to state-of-the-art results.
Volume of the steady-state space of financial flows in a monetary stock-flow-consistent modelphysics.soc-ph
We show that a steady-state stock-flow consistent macro-economic model can be represented as a Constraint Satisfaction Problem (CSP).The set of solutions is a polytope, which volume depends on the constraintsapplied and reveals the potential fragility of the economic circuit,with no need to study the dynamics. Several …
EarnMore uses masked stock representations to train RL agents for customizable stock pools efficiently.
problem Training RL agents for customizable stock pools (CSPs) is computationally expensive and unstable.
method EarnMore introduces a mechanism to mask out stocks outside the target pool, learns meaningful stock representations, and uses a re-weighting mechanism to focus on favorable stocks.
result EarnMore significantly outperforms state-of-the-art baselines in profit metrics with over 40% improvement.
A training-free conformal interval is a mandatory baseline for probabilistic time-series forecasting.
problem Comparing probabilistic forecasters against weak or omitted baselines.
method A simple conformal interval with no parameters and no training.
result The ConformalNaive interval decisively beats several baselines.
We propose , a novel self-regularized non-monotonic activation function which can be mathematically defined as: . As activation functions play a crucial role in the performance and training dynamics in neural networks, we validated experimentally on several well-known benchmarks…
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscs.LG
New framework analyzes effectiveness of neural network-based combinatorial problem solvers.
problem Analyzing neural network-based methods for combinatorial optimization problems.
method Introducing a theoretical framework to assess the effectiveness of solution-samplers using policy-gradient methods.
result Positive theoretical answer to the existence of expressive, tractable, and benign optimization landscapes for combinatorial problems.
Proposes extensions to semi-parametric models using BART for shared covariates.
problem Avoiding poor coverage properties and reducing bias in linear predictor estimates.
method Modifies tree-generation moves in BART to handle shared covariates between linear and non-parametric components.
result Competitive performance in modelling complex interactions and predicting student achievements.
We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there …
The free energy is a key quantity of interest in Ising models, but unfortunately, computing it in general is computationally intractable. Two popular (variational) approximation schemes for estimating the free energy of general Ising models (in particular, even in regimes where correlation decay does not hold) are: (i)…