On the power of small-depth threshold circuits

No abstract is available for this paper.

• Publication year

  1990

• Venue

  Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science

• Publication date

  1990-10-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BF01272517
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Introduction to the theory of neural computation

  1994cited by this paper
• Majority gates vs. general weighted threshold gates

  1992cited by this paper
• On The Power Of Threshold Circuits With Small Weights

  1991cited by this paper
• Learning decision trees using the Fourier spectrum

  1991cited by this paper
• Geometric arguments yield better bounds for threshold circuits and distributed computing

  1991cited by this paper
• Some Notes on Threshold Circuits, and Multiplication in Depth 4

  1991cited by this paper
• Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in

  1991cited by this paper
• On the computational power of sigmoid versus Boolean threshold circuits

  1991cited by this paper
• Monotone circuits for connectivity require super-logarithmic depth

  1990cited by this paper
• Polynomial threshold functions, AC functions and spectrum norms

  1990cited by this paper
• Monotone circuits for matching require linear depth

  1990cited by this paper
• A Spectral Lower Bound Techniqye for the Size of Decision Trees and Two Level AND/OR Circuits

  1990cited by this paper
• ON ACC and threshold circuits

  1990cited by this paper
• Harmonic Analysis of Polynomial Threshold Functions

  1990cited by this paper
• Probabilistic communication complexity of Boolean relations

  1989cited by this paper
• Circuits and local computation

  1989influential reference
• A note on the power of threshold circuits

  1989cited by this paper
• On the computational power of PP and (+)P

  1989cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper
• Multiparty protocols and logspace-hard pseudorandom sequences

  1989influential reference
• The influence of variables on Boolean functions

  1988cited by this paper
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

  1987cited by this paper
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

  1987cited by this paper
• Threshold circuits of bounded depth

  1987cited by this paper
• The Complexity of Computations by Networks

  1987cited by this paper
• The monotone circuit complexity of boolean functions

  1987cited by this paper
• A Note on a Theorem of Razborov

  1987cited by this paper
• Computational limitations of small-depth circuits

  1987cited by this paper
• Separating the polynomial-time hierarchy by oracles

  1985cited by this paper
• Unbiased bits from sources of weak randomness and probabilistic communication complexity

  1985influential reference
• Lower bounds on monotone complexity of the logical permanent

  1985cited by this paper
• Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

  1985cited by this paper
• Log Depth Circuits for Division and Related Problems

  1984cited by this paper
• Constant Depth Reducibility

  1984cited by this paper
• ∑11-Formulae on finite structures

  1983cited by this paper
• Borel sets and circuit complexity

  1983cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981cited by this paper
• Some complexity questions related to distributive computing(Preliminary Report)

  1979cited by this paper
• Threshold logic and its applications

  1971cited by this paper
• On the Size of Weights Required for Linear-Input Switching Functions

  1961cited by this paper

• Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication

  2025cites this paper
• Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication

  2025cites this paper
• Riffle Rank

  2025cites this paper
• New Pseudorandom Generators and Correlation Bounds Using Extractors

  2025cites this paper
• On the Depth of Monotone ReLU Neural Networks and ICNNs

  2025cites this paper
• Agnostic Membership Query Learning with Nontrivial Savings: New Results and Techniques

  2024cites this paper
• Trade-Offs Between Energy and Depth of Neural Networks

  2024cites this paper
• A Note on the LogRank Conjecture in Communication Complexity

  2023cites this paper
• Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques

  2023cites this paper
• Matrix Multiplication and Number On the Forehead Communication

  2023cites this paper
• An intelligence parameter classification approach for energy storage and natural convection and heat transfer of nano-encapsulated phase change material: Deep neural networks

  2023cites this paper
• Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees

  2023cites this paper
• Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees

  2022cites this paper
• Low-degree term first in ResNet, its variants and the whole neural network family

  2022cites this paper
• Correlation bounds against polynomials

  2022cites this paper
• Tensors for deep learning theory

  2022cites this paper
• Tucker network: Expressive power and comparison

  2022cites this paper
• A review of convolutional neural network architectures and their optimizations

  2022cites this paper
• Learnability of the Boolean Innerproduct in Deep Neural Networks

  2022cites this paper
• Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

  2021cites this paper
• Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy

  2021cites this paper
• Brain Tumor Detection based on Ensemble Learning

  2021cites this paper
• Impact of Attention on Perception in Cognitive Dynamic Systems

  2021cites this paper
• An improved protocol for the exactly-N problem*

  2021cites this paper
• Globally Convergent Multilevel Training of Deep Residual Networks

  2021cites this paper
• A Deep Learning Approach to Predict the Flow Field and Thermal Patterns of Nonencapsulated Phase Change Materials Suspensions in an Enclosure

  2021cites this paper
• The Fun tion-Inversion Problem: Barriers and Opportunities

  2021cites this paper
• Larger Corner-Free Sets from Better NOF Exactly-\(N\) Protocols

  2021cites this paper
• Circuit Complexity of Visual Search

  2021cites this paper
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

  2021cites this paper
• Brain Tumor Detection: 2 Novel Approaches

  2020cites this paper
• Learning to Play: Reinforcement Learning and Games

  2020cites this paper
• BRAIN TUMOR DETECTION: CONVOLUTIONAL NEURAL NETWORKS AND CLASSIFICATION ALGORITHMS

  2020cites this paper
• Using deep learning to learn physics of conduction heat transfer

  2020cites this paper
• Extractors and Secret Sharing Against Bounded Collusion Protocols

  2020cites this paper
• Auto-Encoder based Deep Representation Model for Image Anomaly Detection

  2020cites this paper
• New lower bounds for probabilistic degree and AC0 with parity gates

  2020cites this paper
• Multilevel Minimization for Deep Residual Networks

  2020cites this paper
• Expressivity of Deep Neural Networks

  2020cites this paper
• Size, Depth and Energy of Threshold Circuits Computing Parity Function

  2020cites this paper
• Deep Networks with Fast Retraining

  2020cites this paper
• A Superpixel-Based Relational Auto-Encoder for Feature Extraction of Hyperspectral Images

  2019cites this paper
• Hybrid fully convolutional networks‐based skin lesion segmentation and melanoma detection using deep feature

  2019cites this paper
• Bio-inspired Analysis of Deep Learning on Not-So-Big Data Using Data-Prototypes

  2019cites this paper
• On Functions Computed on Trees

  2019cites this paper
• Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

  2019cites this paper
• Stochastic Feedforward Neural Networks: Universal Approximation

  2019cites this paper
• C C ] 2 6 A pr 2 01 9 On the Relationship between Energy Complexity and other Boolean Function Measures

  2019cites this paper
• Leakage-Resilient Secret Sharing Against Colluding Parties

  2019cites this paper
• Number-On-Forehead Communication Complexity of Data Clustering with Sunflowers

  2019cites this paper
• Deep Learning

  2019cites this paper
• The Function-Inversion Problem: Barriers and Opportunities

  2019influential citation
• Tucker Decomposition Network: Expressive Power and Comparison

  2019cites this paper
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

  2019cites this paper
• Fundamentals of Machine Learning

  2019cites this paper
• User Interface Evaluation with Machine Learning Methods

  2019cites this paper
• ResNet Sparsifier: Learning Strict Identity Mappings in Deep Residual Networks

  2018cites this paper
• Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits

  2018influential citation
• Local reduction

  2018cites this paper
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

  2018cites this paper
• Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits

  2018cites this paper
• Application of prior information to discriminative feature learning

  2018cites this paper
• SV-RCNet: Workflow Recognition From Surgical Videos Using Recurrent Convolutional Network

  2018cites this paper
• Application of deep autoencoder model for structural condition monitoring

  2018cites this paper
• Circuit lower bounds from learning-theoretic approaches

  2018cites this paper
• Reconciling Feature-Reuse and Overfitting in DenseNet with Specialized Dropout

  2018cites this paper
• Three Puzzles on Mathematics, Computation, and Games

  2018cites this paper
• On building ensembles of stacked denoising auto-encoding classifiers and their further improvement

  2018cites this paper
• Design and Implementation of CNN for detecting Melanoma through Image Processing

  2018cites this paper
• Leakage-Resilient Secret Sharing

  2018cites this paper
• Fast and High-performance Multi-convolution Deep Neural Network Structure with Residuals

  2018cites this paper
• Different Learning Architectures Contribute to Value Prediction in Human Cognition

  2018cites this paper
• Feature regularization and learning for human activity recognition.

  2018cites this paper
• On multiparty communication with large versus unbounded error

  2018cites this paper
• Deep Learning Works in Practice. But Does it Work in Theory?

  2018cites this paper
• Multi-parameter optimisation of quantum optical systems

  2018cites this paper
• Person re-identification in images with deep learning. (Ré-identification de personnes dans des images par apprentissage automatique)

  2018cites this paper
• On the relationship between energy complexity and other boolean function measures

  2018cites this paper
• N ov 2 01 8 On The Communication Complexity of High-Dimensional Permutations Nati Linial

  2018cites this paper
• Learning Strict Identity Mappings in Deep Residual Networks

  2018cites this paper
• New architectures for very deep learning

  2018cites this paper
• Improved pseudorandom generators from pseudorandom multi-switching lemmas

  2018cites this paper
• On the Expressive Power of Overlapping Architectures of Deep Learning

  2017cites this paper
• Automated Melanoma Recognition in Dermoscopy Images via Very Deep Residual Networks

  2017cites this paper
• Simultaneous Multiparty Communication Complexity of Composed Functions

  2017cites this paper
• A deep learning approach for sentiment analysis

  2017cites this paper
• How and What Deep Learning Learns

  2017cites this paper
• Inner Product and Set Disjointness

  2017cites this paper
• A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem

  2017cites this paper
• Weights at the Bottom Matter When the Top is Heavy

  2017cites this paper
• On The Communication Complexity of High-Dimensional Permutations

  2017cites this paper
• On the Expressive Power of Overlapping Operations of Deep Networks

  2017cites this paper
• Recurrent neural network weight estimation through backward tuning

  2017cites this paper
• Selected challenges in computational lower bounds

  2017cites this paper
• Classification du texte numérique et numérisé. Approche fondée sur les algorithmes d'apprentissage automatique. (Text and Image based classification of documents using machine and representation learning)

  2017cites this paper
• Selected challenges in computational lower bounds

  2017cites this paper
• Deep Learning in Object Recognition, Detection, and Segmentation

  2016cites this paper
• A protein-protein interaction extraction approach based on deep neural network

  2016cites this paper
• Multi-Residual Networks

  2016cites this paper
• Dynamical Systems and Interaction Networks

  2016cites this paper