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.
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.
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.
Neural networks favor Boolean functions with low entropy.
problem Understanding the inductive bias of neural networks.
method Analyzing a single-layer perceptron with random initial weights.
result There is a strong intrinsic bias towards low entropy Boolean functions.
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.
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.
Random SNNs are stable and simple, with low-frequency Fourier spectra.
problem Stability and robustness of spiking neural networks.
method Boolean function analysis and Fourier spectrum concentration.
result Random LIF-SNNs are stable and biased towards simple functions.
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.
New algorithm uses random matrices for neural network training without synaptic weight symmetries.
problem Training neural networks efficiently and without synaptic weight symmetries.
method Contrastive Hebbian learning with random feedback weights.
result Random contrastive Hebbian learning achieves better computational models for learning.
We develop a method to factorize symmetric sparse Boolean matrices efficiently.
problem Finding a symmetric factorization of a given matrix into a sparse, Boolean matrix.
method Polynomial-time algorithm based on bootstrapping higher-order information and tensor decomposition.
result A matrix with full column rank can be recovered with high probability when the matrix size is sufficiently large.
New algorithm learns halfspaces over hypercube with random bit flips.
problem Agnostic learning of Boolean halfspaces over discrete domains is computationally hard.
method Smoothed analysis with random bit flips for discrete inputs.
result First efficient algorithm for smoothed agnostic learning of halfspaces over Boolean hypercube.
LIBRE learns interpretable Boolean rules from data.
problem Creating interpretable classifiers in imbalanced settings.
method Ensemble of weak learners on random feature subsets, combined with a simple union.
result Efficiently balances prediction accuracy and interpretability.
Randomly biased data makes complex models as easy to learn as simple ones.
problem Learning complex models like multi-index and sparse Boolean functions.
method Introducing a small random shift in the first moment of the data distribution.
result Randomly biased data makes Gaussian single index models and sparse Boolean functions as easy to learn as linear functions.
Study on lower bounds for deep neural networks using ReLU gates.
problem Understanding the role of depth in neural networks computing Boolean functions.
method Use of random restrictions and sign-rank methods to show lower bounds.
result Exponential lower bounds for ReLU circuits ending in a LTF gate.
New approach uses Boolean circuits to optimize neural networks.
problem Improving efficiency of neural network implementations on hardware accelerators.
method Formalized neural networks as Boolean circuits, showing binarized networks are functionally complete.
result Binarized neural networks are functionally complete, suggesting new possibilities for neural network accelerators.
Graph neural networks struggle with proving unsatisfiability in complex logical formulas.
problem Proving unsatisfiability in complex logical formulas.
method Investigating the limitations of graph neural networks in logical reasoning tasks.
result Graph neural networks may fail in certifying unsatisfiability in Boolean formulae.
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.
The paper introduces false discovery rate control for BMF to avoid noisy patterns.
problem No guarantees exist for BMF patterns being real, not just noise.
method Proposes false discovery rate (FDR) to control BMF patterns, proving bounds on FDR.
result Improved BMF algorithms using theoretical FDR bounds for rank selection.
Algorithm learns CNF formulas from random solutions under specific conditions.
problem Learning a CNF formula from uniform random solutions.
method Revisits Valiant's algorithm and applies Lovász local lemma conditions.
result Significantly reduces sample complexity for learning CNFs.
New models analyze stability of gene regulation networks with coregulation.
problem Stability and structure of gene regulation networks with shared regulatory motifs.
method Developed formalism for modeling coregulation rules in RBN, analyzed stability through mean-field approach.
result Coregulation can increase network stability, especially in autoregulated multi-gene modules and hierarchical gene complexes.
The study explores how Matrix Product States can represent boolean and continuous functions.
problem Representing arbitrary boolean and continuous functions using Matrix Product States.
method Developed a construction method for MPS to represent boolean gates and proved density in continuous function space.
result MPS can accurately represent arbitrary boolean functions and continuous functions densely.
Paper verifies properties of binarized neural networks using SAT solvers.
problem Verifying properties of deep neural networks.
method Exact Boolean encoding of binarized neural networks, SAT solvers, counterexample-guided search.
result Demonstrates scalability to medium-size deep neural networks for robustness verification.
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.
New methods protect malware classification networks from adversarial attacks.
problem Adversarial perturbations compromise malware classification networks.
method Training restricted networks with non-negative weight restrictions and relaxing constraints.
result Improved classifier accuracy while maintaining resistance to adversarial attacks.
Probabilistic Boolean tensor decomposition improves accuracy and scalability.
problem Approximating multi-way binary data with interpretable low-rank factors.
method Scalable sampling-based posterior inference exploiting combinatorial structure.
result Maximum a posteriori decompositions outperform existing techniques.
Neural networks can learn Boolean circuits with local correlation.
problem Learning Boolean circuits with neural networks is computationally hard.
method Observing local correlation between input patterns and target labels, focusing on tree-structured Boolean circuits.
result Local correlation determines the success or failure of optimization in learning Boolean circuits.
New approach to certifiably robust neural networks using Boolean function perspective.
problem Lack of principled understanding and certified robustness for ℓ∞ perturbations. method New perspective on Boolean functions, deriving impossibility results, and developing a unified Lipschitz network.
result Unified Lipschitz network that bypasses expressive power limitations and achieves better certified robustness.
The paper explores how neural networks learn logical functions and their generalization error.
problem Learning logical functions with neural networks and understanding generalization error.
method Gradient descent on neural networks, analyzing noise-stability and Boolean influence.
result Gradient descent on certain neural architectures tends to favor low-degree representations, impacting generalization error.
Efficiently estimate Boolean product distribution parameters from truncated samples.
problem Estimating parameters of Boolean product distributions from truncated samples.
method Introducing fatness of truncation set, using membership queries, and adapting Stochastic Gradient Descent.
result Efficiently learn Boolean product distributions from truncated samples with small sample complexity.
CodNN uses error-correcting codes to make neural networks more resilient to noise.
problem Neural networks are sensitive to noise, especially in critical applications.
method Construct robust neural networks by coding data or internal layers with error-correcting codes.
result Parity codes can guarantee robustness for a wide range of neural networks, including binarized networks.
The study explores the compressive power of Boolean threshold autoencoders, finding that seven layers are necessary but three are not.
problem Understanding the compressive limits of Boolean threshold autoencoders.
method Investigation into the minimum number of layers and nodes required for autoencoders to accurately transform binary vectors.
result There exists a seven-layer autoencoder with a logarithmic middle layer size for any set of distinct vectors, but not a three-layer one.
FGN models networks with fractal structures using Gaussian Multiplicative Chaos.
problem Modeling networks with fractal structures.
method FGN model based on Gaussian Multiplicative Chaos.
result FGNs reveal distinct scaling patterns in edge and clique counts.
The theory of learning under the uniform distribution is rich and deep, with connections to cryptography, computational complexity, and the analysis of boolean functions to name a few areas. This theory however is very limited due to the fact that the uniform distribution and the corresponding Fourier basis are rarely …
A new method for Boolean matrix factorisation outperforms existing approaches.
problem Decomposing binary data matrices into meaningful patterns and quantifying their combinations.
method Probabilistic generative model with Metropolised Gibbs sampler for efficient posterior inference.
result The method outperforms all existing approaches on real and simulated data.
The paper explores how different network architectures learn logical functions under GOTU, finding that a min-degree-interpolator is learned.
problem Learning logical functions with a focus on generalization on the unseen.
method Study of different network architectures trained by SGD under GOTU.
result For sparse functions and certain network models, a min-degree-interpolator is learned on the unseen.
Fourier analysis improves REINFORCE for binary models.
problem Improving gradient estimation for binary latent variable models.
method Connecting Fourier spectrum of Boolean functions to REINFORCE and developing low-variance unbiased gradient estimators.
result REINFORCE estimates degree-1 Fourier coefficients of a Boolean function.
New algorithm proves deep networks can learn better than shallow ones.
problem Understanding the power difference between shallow and deep neural networks.
method Identifying a class of Boolean functions and proving that logarithmic-depth networks can learn them efficiently using hierarchical reconstruction.
result First algorithmic separation between constant-depth and logarithmic-depth neural networks.
The study examines the retrieval capabilities of RBMs and generalized Hopfield networks under various prior distributions.
problem Characterizing the state of RBMs and Hopfield networks under different prior distributions.
method Equivalence between RBMs and generalized Hopfield networks, analysis of phase transitions, and study of retrieval capabilities.
result The retrieval phase is robust and exists at low load for every pattern distribution.
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.
New machine learning method uses algorithmic complexity for non-differentiable spaces.
problem Machine learning on non-differentiable spaces.
method Introduces complexity theory in machine learning, using algorithmic complexity for regression and classification.
result More generalizable and resilient to random attacks compared to traditional methods.
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.
GRAB efficiently learns combinatorial Boolean models from data.
problem Learning combinatorial Boolean models from labeled data is computationally expensive.
method GRAB algorithm, using L1-regularized loss minimization and frequent itemset mining. result GRAB efficiently learns CBM with reduced computational time and improved accuracy.
Paper presents a new method to train deep neural networks with reduced memory access.
problem High computational and storage complexity of deep neural networks.
method Boolean logic minimization to remove memory access and reduce resource usage.
result Significantly lower latency and two orders of magnitude fewer computing resources.
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.
New algorithm for robust Boolean matrix factorization handles noise and missing data.
problem Robust probabilistic Boolean matrix factorization in the presence of noise and missing values.
method Probabilistic Expectation Maximization algorithm without latent factor assumptions.
result Outperforms state-of-the-art probabilistic algorithms on real data.