Study on functions computed by deep-layered machines finds same distribution in neural networks and Boolean circuits.
problem Understanding the space of functions computed by deep-layered machines.
method Investigation of Boolean functions on random-layered machines, including neural networks and Boolean circuits.
result The space of functions computed at large depth limit is characterized and the macroscopic entropy of Boolean functions is either monotonically increasing or decreasing with depth.
New findings show that common optimization algorithms struggle with random problems.
problem Finding near-optimal solutions to random optimization problems.
method Low-degree polynomials, Boolean circuits, and Langevin dynamics.
result These algorithms fail to produce nearly optimal solutions with high probability.
This study shows neural nets can approximate Turing machines with meaningful statistical properties.
problem Theoretical limitations in approximating Turing machines with neural networks.
method Formal definition of statistically meaningful approximation, analysis of boolean circuits and Turing machines using neural nets.
result Transformers can statistically meaningfully approximate Turing machines with polynomial sample complexity.
We consider efficiency in the implementation of deep neural networks. Hardware accelerators are gaining interest as machine learning becomes one of the drivers of high-performance computing. In these accelerators, the directed graph describing a neural network can be implemented as a directed graph describing a Boolean…
Predictive models are finding an increasing number of applications in many industries. As a result, a practical means for trading-off the cost of deploying a model versus its effectiveness is needed. Our work is motivated by risk prediction problems in healthcare. Cost-structures in domains such as healthcare are quite…
We study the statistical behavior of reasoning probes in a stylized model of iterative computation inspired by neural algorithmic reasoning. The underlying computation is given by a looped Boolean circuit whose graph is a perfect ν-ary tree (ν≥2), with outputs recursively fed back as inputs across computation ro…
While on some natural distributions, neural-networks are trained efficiently using gradient-based algorithms, it is known that learning them is computationally hard in the worst-case. To separate hard from easy to learn distributions, we observe the property of local correlation: correlation between local patterns of t…
Unified tractability conditions for various compositional inference queries.
problem Analyzing tractability of probabilistic and causal inference queries.
method Algebraic perspective on circuits, focusing on semiring operators.
result Unified sufficient conditions for tractable composition of operators.
Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function x↦max{0,x}. We try to understand the role of depth in such neural networks by showing size lowerbounds against such network …
In this technical report we presented a novel approach to machine learning. Once the new framework is presented, we will provide a simple and yet very powerful learning algorithm which will be benchmark on various dataset. The framework we proposed is based on booleen circuits; more specifically the classifier produced…
Boolean logic used for neural network training and inference, with convergence analysis.
problem Discrete optimization in neural networks with Boolean logic.
method Boolean logic backpropagation with convergence analysis.
result First convergence analysis for Boolean logic in neural networks.
CoT enhances transformer accuracy on serial tasks by enabling serial computation.
problem Improving accuracy of large language models on inherently serial problems.
method Integrating a chain of thought (CoT) into decoder-only transformers to enable serial computation.
result Constant-depth transformers with CoT can solve problems in AC^0, surpassing TC^0 without CoT.
New Fourier analysis method for non-uniform Boolean hypercube.
problem Non-uniform probability measures on the Boolean hypercube.
method ANOVA-based decomposition, explicit basis, least squares problem.
result Generalization of Fourier analysis for arbitrary probability measures.
A new deep learning method using Boolean logic reduces training and inference energy.
problem High computational and energy costs in deep learning training and inference.
method Introduces Boolean weights and inputs for efficient training using Boolean logic.
result Achieves full-precision accuracy in ImageNet classification and surpasses state-of-the-art results in semantic segmentation.
Boolean matrix factorization and Boolean matrix completion from noisy observations are desirable unsupervised data-analysis methods due to their interpretability, but hard to perform due to their NP-hardness. We treat these problems as maximum a posteriori inference problems in a graphical model and present a message p…
New Boolean algebra method shows knot unknotting number is (c+1)/2.
problem Finding the minimum number of region crossing changes to unknot a knot.
method Boolean algebra applied to region crossing changes.
result Region unknotting number is (c+1)/2 for any knot with crossing number c.
A new method relaxes Boolean Matrix Factorization to make it more efficient.
problem High computational cost of solving NP-hard combinatorial optimization problems in Boolean Matrix Factorization.
method Proposes a proximal gradient algorithm using an elastic-binary regularizer to relax BMF.
result Demonstrates improved runtime and better recall, loss, and interpretability on real-world data.
Probabilistic learning for binary classification with categorical variables.
problem Binary classification with categorical covariates.
method Probabilistic analysis and two algorithms for learning boolean functions.
result Effective learning of boolean functions from binary data.
Boolean matrix factorisation aims to decompose a binary data matrix into an approximate Boolean product of two low rank, binary matrices: one containing meaningful patterns, the other quantifying how the observations can be expressed as a combination of these patterns. We introduce the OrMachine, a probabilistic genera…
Survey on learning Boolean functions in computational theory.
problem Learning Boolean function classes in computational theory.
method Overview of known results in PAC and related models.
result Discussion of various learning results for Boolean functions.
A Bayesian Boolean Matrix Factorization for cancer genomics
problem Identifying coordinated feature changes in cancer
method Bayesian Boolean Matrix Factorization
result Captures widespread, near-simultaneous chromosome-number changes
Minimalist softmax attention learns constrained Boolean functions with supervision.
problem Learning k-bit Boolean functions, especially AND and OR. method Minimalist single-head softmax-attention mechanism with teacher forcing.
result Minimalist attention can solve Boolean tasks with supervision, but not without.
New framework reduces LLM complexity by directly finetuning in Boolean domain.
problem Reducing the complexity of large language models (LLMs) while maintaining performance.
method Proposes a novel framework using multi-kernel Boolean parameters for direct finetuning in the Boolean domain.
result Significantly reduces complexity during both finetuning and inference, outperforming recent techniques.
GETF efficiently decomposes large-scale Boolean tensors.
problem Efficiently factorizing large-scale Boolean tensors.
method Geometric Expansion for all-order Tensor Factorization (GETF).
result GETF significantly improves reconstruction accuracy and efficiency.
Machine learning has started to be deployed in fields such as healthcare and finance, which propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known mac…
Study evaluates capacity and trainability of parametrized quantum circuits.
problem Finding the best type of circuits for hybrid quantum-classical algorithms.
method Geometric structure of parameter space, effective quantum dimension, and circuit expressiveness.
result Identifies a transition in quantum geometry leading to decay of quantum natural gradient for deep circuits.
Transformers learn sparse Boolean functions through RL and SFT, revealing distinct learning behaviors.
problem Learning sparse Boolean functions with Transformers.
method Reinforcement Learning (RL) with process rewards and Supervised Fine-Tuning (SFT).
result RL learns the whole CoT chain simultaneously, while SFT learns step by step.
Paper improves variational inference on Boolean hypercube using quantum methods.
problem Improving variational inference for pairwise Markov random fields on the Boolean hypercube.
method Quantum relaxations of the Kullback-Leibler divergence for upper-bounds, primal-dual optimization, and greedy selection of hierarchies.
result Efficient algorithm and improved bounds for variational inference.
The paper tests if LLMs' capabilities are executed by small subnetworks (circuits).
problem Understanding how LLMs execute their capabilities.
method Formalized criteria for circuits, developed hypothesis tests, applied to six circuits.
result Synthetic circuits align with idealized properties, while Transformer circuits vary in their alignment.
Paper proposes algorithms for BMF using integer programming.
problem Approximating binary input matrix as product of two smaller binary factors.
method Alternating optimization strategy using integer programming to solve subproblems and combine solutions.
result Proposed algorithms outperform state of the art on medium-scale problems.
The paper develops algorithms for Boolean matrix factorization using IP and heuristics.
problem Approximating binary input matrices as products of smaller binary factors.
method Alternating optimization with integer programming and greedy/local-search heuristics.
result Proposed methods improve scalability and performance compared to existing techniques.
Boolean matrix factorization (BMF) is a popular and powerful technique for inferring knowledge from data. The mining result is the Boolean product of two matrices, approximating the input dataset. The Boolean product is a disjunction of rank-1 binary matrices, each describing a feature-relation, called pattern, for a g…
Study examines noise sensitivity of DNNs for binary classification.
problem Understanding non-robustness of DNN classifiers under noise.
method Defined and extended noise sensitivity and stability concepts for Boolean functions, applied to DNN models.
result Sorted out the relation between definitions and properties of DNN architectures under noise.
This paper explores how boolean formulas can be learned by deep neural networks.
problem Understanding the learnability of boolean formulas by deep neural networks.
method Analysis of boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs.
result Neural networks outperform rule-based systems and pure symbolic approaches in learning boolean formulas.
We explain why numbers occurring in the classification of polygon spaces coincide with numbers of self-dual equivalence classes of threshold functions, or of regular Boolean functions, or of decisive weighted majority games.
This paper introduces the combinatorial Boolean model (CBM), which is defined as the class of linear combinations of conjunctions of Boolean attributes. This paper addresses the issue of learning CBM from labeled data. CBM is of high knowledge interpretability but naïve learning of it requires exponentially large compu…
Study detects if a circuit bounds a disc using curve intersections.
problem Determining if a circuit bounds an embedded disc.
method Analyzing the group generated by Dehn twists about curves in a circuit.
result Cycle relation between Dehn twists detects disc-boundability.
Theory of ends of spaces using linear algebra.
problem Understanding ends of spaces at infinity.
method Developing a theory using scale, sub-Boolean algebras, and linear algebra.
result All known types of ends are special cases of a linear algebraic process.
Evolutionary strategy optimizes quantum circuit design and parameters.
problem Optimizing quantum circuit design and parameters for NISQ devices.
method Simple evolutionary strategy to optimize both circuit architecture and parameters.
result Minor slowdown on actual quantum hardware compared to simulations, with insights into mutation operations.
Boolean matrix has been used to represent digital information in many fields, including bank transaction, crime records, natural language processing, protein-protein interaction, etc. Boolean matrix factorization (BMF) aims to find an approximation of a binary matrix as the Boolean product of two low rank Boolean matri…
This work uses SVM to identify track component failures in AC Track Circuits.
problem Detecting and identifying specific track component failures in AC Track Circuits.
method Applied SVM classifier to STDS track circuit data.
result Successfully classified 15 different track component failures.
The statistical complexity of quantum circuits is studied using Rademacher complexity.
problem Measuring the richness of quantum hypothesis spaces.
method Applying Rademacher complexity to quantum circuits, investigating dependencies on resources, depth, width, and input/output registers.
result Bounds on the capacity of quantum neural networks constrained by circuit depth, width, and resource measures.
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,…
NeuraLUT maps neural networks to lookup tables, reducing latency and improving expressivity.
problem Reducing latency in deep neural networks for FPGA accelerators.
method Mapping entire sub-networks to a single lookup table, introducing skip connections.
result Up to 4.3x lower latency for the same accuracy.
Quantum circuit Born machines are generative models which represent the probability distribution of classical dataset as quantum pure states. Computational complexity considerations of the quantum sampling problem suggest that the quantum circuits exhibit stronger expressibility compared to classical neural networks. O…
Quantum mechanics is inherently probabilistic in light of Born's rule. Using quantum circuits as probabilistic generative models for classical data exploits their superior expressibility and efficient direct sampling ability. However, training of quantum circuits can be more challenging compared to classical neural net…
The study examines how quantum resources enhance the complexity of quantum circuits.
problem Quantum resource enhancement on circuit complexity.
method Utilizing quantum resource theories, the study analyzes statistical complexities of quantum circuits with limited quantum resources.
result Bounds for statistical complexities of quantum circuits are derived and applied to specific cases.
Study links neural network inductive bias, feature learning, and generalization on Boolean functions.
problem Understanding how neural networks learn and generalize on Boolean data.
method End-to-end analysis of depth-2 discrete fully connected networks and DNF formulas, using Monte Carlo learning.
result Predictable training dynamics and interpretable features emerge, linking inductive bias and generalization.