Computational complexity of machine learning

No abstract is available for this paper.

• Publication year

  1990

• Venue

  ACM distinguished dissertations

• Publication date

  1990-10-22

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Diversity-based inference of finite automata

  1994cited by this paper
• Learning in the presence of malicious errors

  1993cited by this paper
• Primality and cryptography

  1991cited by this paper
• Efficient distribution-free learning of probabilistic concepts

  1990cited by this paper
• Learning DNF under the uniform distribution in quasi-polynomial time

  1990cited by this paper
• On the necessity of Occam algorithms

  1990cited by this paper
• Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results

  1989cited by this paper
• Learning Nested Differences of Intersection-Closed Concept Classes

  1989cited by this paper
• Proceedings of the 1988 Workshop on Computational Learning Theory : MIT, August 3-5, 1988

  1989cited by this paper
• The minimum consistent DFA problem cannot be approximated within any polynomial

  1989cited by this paper
• The Strength of Weak Learnability

  1989cited by this paper
• A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution

  1989cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Learning binary relations and total orders

  1989cited by this paper
• A polynomial-time algorithm for learning k-variable pattern languages from examples

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

  1989cited by this paper
• Inference of finite automata using homing sequences

  1989cited by this paper
• Functionality in neural nets

  1988cited by this paper
• Learning in parallel

  1988cited by this paper
• Types of noise in data for concept learning

  1988cited by this paper
• Predicting (0, 1)-functions on randomly drawn points

  1988cited by this paper
• Learning with hints

  1988cited by this paper
• Automatic Pattern Recognition: A Study of the Probability of Error

  1988cited by this paper
• Equivalence of models for polynomial learnability

  1988cited by this paper
• Learning k-DNF with noise in the attributes

  1988cited by this paper
• Results on learnability and the Vapnik-Chervonenkis dimension

  1988cited by this paper
• Reductions among prediction problems: on the difficulty of predicting automata

  1988cited by this paper
• Computational limitations on learning from examples

  1988cited by this paper
• Learning complicated concepts reliably and usefully

  1988cited by this paper
• Learning in neural networks

  1988cited by this paper
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole

  1988cited by this paper
• Learning from Good and Bad Data

  1988cited by this paper
• On learning Boolean functions

  1987cited by this paper
• Learning one-counter languages in polynomial time

  1987cited by this paper
• On the learnability of Boolean formulae

  1987cited by this paper
• Recent Results on Boolean Concept Learning

  1987cited by this paper
• On Threshold Circuits and Polynomial Computation

  1987cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987cited by this paper
• Epsilon-nets and simplex range queries

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

  1984cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• A theory of the learnable

  1984cited by this paper
• Inductive Inference: Theory and Methods

  1983cited by this paper
• How to generate cryptographically strong sequences of pseudo random bits

  1982cited by this paper
• A new approximate graph coloring algorithm

  1982cited by this paper
• Theory and application of trapdoor functions

  1982cited by this paper
• Some special vapnik-chervonenkis classes

  1981cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• A method for obtaining digital signatures and public-key cryptosystems

  1978cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper
• ON CONVERGENCE OF STOCHASTIC PROCESSES

  1962cited by this paper
• On Learning Conjunctions of Horn ⊃ Clauses ?

  year unknowncited by this paper

• AIR-VLA: Vision-Language-Action Systems for Aerial Manipulation

  2026cites this paper
• Joint Geometric and Trajectory Consistency Learning for One-Step Real-World Super-Resolution

  2026cites this paper
• ProAgentBench: Evaluating LLM Agents for Proactive Assistance with Real-World Data

  2026cites this paper
• Models Under SCOPE: Scalable and Controllable Routing via Pre-hoc Reasoning

  2026cites this paper
• IMTS is Worth Time × Channel Patches: Visual Masked Autoencoders for Irregular Multivariate Time Series Prediction

  2025cites this paper
• NExtLong: Toward Effective Long-Context Training without Long Documents

  2025cites this paper
• Diffuse Thinking: Exploring Diffusion Language Models as Efficient Thought Proposers for Reasoning

  2025cites this paper
• Evaluating the three-level approach of the U-smile method for imbalanced binary classification

  2025cites this paper
• Supervised Contrastive Frame Aggregation for Video Representation Learning

  2025cites this paper
• Multi-behavior purchase prediction via graph convolutional networks on implicit bipartite graph relationships

  2025cites this paper
• Learning "Partner-Aware" Collaborators in Multi-Party Collaboration

  2025cites this paper
• Anomaly Detection for Multi-Class Weather Classification in IoT-Integrated Solar Farms using Mask R-CNN and Deep Reinforcement Learning

  2025influential citation
• A Machine Learning-Empowered Cache Management Scheme for High-Performance SSDs

  2024cites this paper
• Adversarially-Robust Inference on Trees via Belief Propagation

  2024cites this paper
• Choices are More Important than Efforts: LLM Enables Efficient Multi-Agent Exploration

  2024cites this paper
• Limits of Transformer Language Models on Learning Algorithmic Compositions

  2024influential citation
• Learning Decision Trees and Forests with Algorithmic Recourse

  2024influential citation
• Limits of Transformer Language Models on Learning to Compose Algorithms

  2024cites this paper
• White-box Multimodal Jailbreaks Against Large Vision-Language Models

  2024cites this paper
• Mild cognitive impairment detection with optimally selected EEG channels based on variational mode decomposition and supervised machine learning

  2024cites this paper
• Training Machine Learning models at the Edge: A Survey

  2024cites this paper
• Synthetic Images for Georeferencing Camera Images in Mobile Mapping Point-clouds

  2024cites this paper
• XEMLPD: an explainable ensemble machine learning approach for Parkinson disease diagnosis with optimized features

  2024cites this paper
• Comparing machine-learning models of different levels of complexity for crop protection: A look into the complexity-accuracy tradeoff

  2024cites this paper
• Exploiting Functional Constraints in Automatic Dominance Breaking for Constraint Optimization

  2023cites this paper
• Tree-Driven Intelligent Security System for Intrusion Detection in IoT environment

  2023cites this paper
• Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling

  2023cites this paper
• Pay Attention to What You Need

  2023cites this paper
• Enhancing Intrusion Detection in Autonomous Vehicles Using Tree-Based Machine Learning Techniques

  2023cites this paper
• Radiomics and Machine Learning for Skeletal Muscle Injury Recovery Prediction

  2023cites this paper
• Efficient Detection and Localization of DoS Attacks in Heterogeneous Vehicular Networks

  2023cites this paper
• Towards Augmentation Based Defense Strategies Against Adversarial Attacks

  2023cites this paper
• A Novel Deep Hierarchical Machine Learning Approach for Identification of Known and Unknown Multiple Security Attacks in a D2D Communications Network

  2023cites this paper
• Group polarization, influence, and domination in online interaction networks: a case study of the 2022 Brazilian elections

  2023cites this paper
• Advantage of Quantum Machine Learning from General Computational Advantages

  2023influential citation
• STA: Self-controlled Text Augmentation for Improving Text Classifications

  2023cites this paper
• Boosting Offline Reinforcement Learning with Action Preference Query

  2023cites this paper
• A review of Federated Learning in Intrusion Detection Systems for IoT

  2022cites this paper
• DNA: Domain Generalization with Diversified Neural Averaging

  2022cites this paper
• Predicting Activity Duration in Smart Sensing Environments Using Synthetic Data and Partial Least Squares Regression: The Case of Dementia Patients

  2022cites this paper
• Non-Intrusive Fish Weight Estimation in Turbid Water Using Deep Learning and Regression Models

  2022cites this paper
• Digital phenotyping by wearable-driven artificial intelligence in older adults and people with Parkinson’s disease: Protocol of the mixed method, cyclic ActiveAgeing study

  2022cites this paper
• Implementation and Learning of Quantum Hidden Markov Models

  2022cites this paper
• Is Your Model Sensitive? SPEDAC: A New Resource for the Automatic Classification of Sensitive Personal Data

  2022cites this paper
• Defensive mechanism against DDoS attack based on feature selection and multi-classifier algorithms

  2022cites this paper
• Deep-Ensemble-Learning-Based GPS Spoofing Detection for Cellular-Connected UAVs

  2022cites this paper
• Forecast Competition in Energy Imbalance Market

  2022cites this paper
• Modeling Quality and Machine Learning Pipelines through Extended Feature Models

  2022cites this paper
• Assessing the Time Efficiency of Ethical Algorithms

  2022cites this paper
• Is Transfer Inductive?

  2021cites this paper
• A Machine Learning Approach to Enhance the Performance of D2D-Enabled Clustered Networks

  2021cites this paper
• ED2: environment dynamics decomposition world models for continuous control

  2021cites this paper
• RoMA: a Method for Neural Network Robustness Measurement and Assessment

  2021cites this paper
• Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty

  2021cites this paper
• Deep Neural Networks Learn Meta-Structures to Segment Fluorescence Microscopy Images

  2021cites this paper
• A secondary structure-based position-specific scoring matrix applied to the improvement in protein secondary structure prediction

  2021cites this paper
• A Survey of On-Device Machine Learning

  2021cites this paper
• An Approximation Algorithm for P-prize-collecting Set Cover Problem

  2021cites this paper
• Bayesian neural hawkes process for event uncertainty prediction

  2021cites this paper
• MTH-IDS: A Multitiered Hybrid Intrusion Detection System for Internet of Vehicles

  2021cites this paper
• Economics, Fairness and Algorithmic Bias

  2020cites this paper
• Automatic Tuning of Rule-Based Evolutionary Machine Learning via Problem Structure Identification

  2020cites this paper
• More Accurate Learning of k-DNF Reference Classes

  2020cites this paper
• Parameterized Dynamic Variants of Red-Blue Dominating Set

  2020cites this paper
• Survey of Network Intrusion Detection Methods From the Perspective of the Knowledge Discovery in Databases Process

  2020cites this paper
• A Flexible Framework for Nonparametric Graphical Modeling that Accommodates Machine Learning

  2020cites this paper
• Market Driven Multidomain Network Service Orchestration in 5G Networks

  2020cites this paper
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

  2020cites this paper
• A rigorous and robust quantum speed-up in supervised machine learning

  2020influential citation
• Data-Driven Cervical Cancer Prediction Model with Outlier Detection and Over-Sampling Methods

  2020cites this paper
• The P-ART framework for placement of virtual network services in a multi-cloud environment

  2019cites this paper
• Local Search for Geometric Partial Covering Problems

  2019cites this paper
• Towards Personalized Diagnosis of Glioblastoma in Fluid-Attenuated Inversion Recovery (FLAIR) by Topological Interpretable Machine Learning

  2019cites this paper
• Distributed and automated machine learning in big data stream analytics

  2019cites this paper
• Quasi Black Hole Effect of Gradient Descent in Large Dimension: Consequence on Neural Network Learning

  2019cites this paper
• Tree-Based Intelligent Intrusion Detection System in Internet of Vehicles

  2019cites this paper
• MaMaDroid: detecting Android malware by building Markov chains of behavioral models (exten...

  2019cites this paper
• Logistic Regression on Hadoop Using PySpark

  2019cites this paper
• Graph input representations for machine learning applications in urban network analysis

  2019cites this paper
• Fault and performance management in multi-cloud virtual network services using AI: A tutorial and a case study

  2019cites this paper
• Important Complexity Reduction of Random Forest in Multi-Classification Problem

  2019cites this paper
• Interdisciplinary optimism? Sentiment analysis of Twitter data

  2019cites this paper
• Applications of machine learning in cryptography: a survey

  2019cites this paper
• New distance weighted k Nearest Neighbor model for hourly global solar irradiation estimation

  2019cites this paper
• Multivariate-Information Adversarial Ensemble for Scalable Joint Distribution Matching

  2019cites this paper
• Management And Security Of Multi-Cloud Applications

  2019cites this paper
• On-Device Machine Learning: An Algorithms and Learning Theory Perspective

  2019influential citation
• Semantic-Based Detection Architectures Against Monitoring-Control Attacks in Power Grids

  2019cites this paper
• Crowdsourcing with Fewer Workers

  2018cites this paper
• Approximation algorithm for the partial set multi-cover problem

  2018influential citation
• Computational Complexity Analysis of Decision Tree Algorithms

  2018cites this paper
• A Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

  2018cites this paper
• Primal Dual Algorithm for Partial Set Multi-cover

  2018cites this paper
• Direction finder deployment based on the partial set multi-cover problem

  2018cites this paper
• Statistical Methods for Scene and Event Classification

  2018cites this paper
• Information gain ratio correction: Improving prediction with more balanced decision tree splits

  2018cites this paper
• On the Partition Set Cover Problem

  2018cites this paper
• Viral marketing with positive influence

  2017cites this paper
• A simple approximation algorithm for minimum weight partial connected set cover

  2017cites this paper
• On Partial Covering For Geometric Set Systems

  2017cites this paper