Crytographic limitations on learning Boolean formulae and finite automata

No abstract is available for this paper.

• Publication year

  1989

• Venue

  Symposium on the Theory of Computing

• Publication date

  1989-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/73007.73049
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Primality and cryptography

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

  1989cited by this paper
• An O(n0.4)-approximation algorithm for 3-coloring

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

  1989cited by this paper
• Learnability by fixed distributions

  1988cited by this paper
• Learning in neural networks

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

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

  1988cited by this paper
• On the learnability of finite automata

  1988cited by this paper
• A general lower bound on the number of examples needed for learning

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

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

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

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

  1987cited by this paper
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing

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

  1987cited by this paper
• Learning Regular Sets from Queries and Counterexamples

  1987cited by this paper
• How to construct random functions

  1986cited by this paper
• Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

  1986cited by this paper
• One-way functions and pseudorandom generators

  1985cited by this paper
• Learning Disjunction of Conjunctions

  1985cited by this paper
• A theory of the learnable

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

  1984cited by this paper
• Constant Depth Reducibility

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

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

  1982cited by this paper
• Occam's razor

  1980cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION

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

  1978cited by this paper
• On taking roots in finite fields

  1977cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• Using transformers to learn system models

  2026cites this paper
• Prediction of nexus among ESG disclosure and firm Performance: Applicability, explainability and implications

  2025cites this paper
• A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic

  2025cites this paper
• Predicting the Amount of Compensation for Harm Awarded by Courts Using Machine-Learning Algorithms

  2024cites this paper
• Machine Learning-Based Classification of Rock Bursts in an Active Coal Mine Dominated by Non-Destructive Tremors

  2024cites this paper
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

  2024cites this paper
• The Cost of Parallelizing Boosting

  2024cites this paper
• Prospectivity and Uncertainty Analysis of Tungsten Polymetallogenic Mineral Resources in the Nanling Metallogenic Belt, South China: A Comparative Study of AdaBoost, GBDT, and XgBoost Algorithms

  2024cites this paper
• A molecular representation to identify isofunctional molecules

  2024cites this paper
• Soft Fault Diagnosis Technology of Filter Circuit Based on Heterogeneous Ensemble Learning

  2023cites this paper
• Applications of machine learning in metabolomics: Disease modeling and classification

  2022cites this paper
• A Bayesian-based classification framework for financial time series trend prediction

  2022cites this paper
• Bankruptcy Prediction Using Machine Learning Techniques

  2022cites this paper
• A Survey of Ensemble Learning: Concepts, Algorithms, Applications, and Prospects

  2022cites this paper
• An Explainable AI Approach for the Rapid Diagnosis of COVID-19 Using Ensemble Learning Algorithms

  2022cites this paper
• Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation

  2021cites this paper
• Boosted Dense Retriever

  2021cites this paper
• A Matrix Algebra Approach to Artificial Intelligence

  2020cites this paper
• A New Ensemble Machine-Learning Framework for Searching Sweet Spots in Shale Reservoirs

  2020cites this paper
• An algorithm for learning representations of models with scarce data

  2020cites this paper
• ADABOOK & MULTIBOOK: Adaptive Boosting with Chance Correction

  2020cites this paper
• A stepwise surrogate model for parameter calibration of the Variable Infiltration Capacity model: the case of the upper Brahmaputra, Tibet Plateau

  2020cites this paper
• On the use of machine learning algorithms in forensic anthropology.

  2020cites this paper
• CNN-boosted full-waveform inversion

  2020cites this paper
• An Improved AdaBoost Algorithm for Handwriting Digits Recognition

  2020cites this paper
• Boosting Trees

  2020cites this paper
• Supervised Machine Learning Techniques: An Overview with Applications to Banking

  2020cites this paper
• A boosting algorithm to extend first-hitting-time models to a high-dimensional survival setting

  2019cites this paper
• Cryptographic Sensing

  2019cites this paper
• Machine-learned analysis of the association of next-generation sequencing based genotypes with persistent pain after breast cancer surgery.

  2019cites this paper
• Deep learning approach for detecting tropical cyclones and their precursors in the simulation by a cloud-resolving global nonhydrostatic atmospheric model

  2018cites this paper
• Supporting information to “ Model averaging in ecology : a review of Bayesian , information-theoretical and tactical approaches ”

  2018cites this paper
• Data-driven Aircraft Trajectory Predictions using Ensemble Meta-Estimators

  2018cites this paper
• Machine-learned analysis of the association of next-generation sequencing–based human TRPV1 and TRPA1 genotypes with the sensitivity to heat stimuli and topically applied capsaicin

  2018cites this paper
• The Boosting and Bootstrap Ensembles for the Pair Classifier Based on the Dual Indiscernibility Matrix

  2017cites this paper
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity

  2016cites this paper
• User Personalized Satisfaction Prediction via Multiple Instance Deep Learning

  2016cites this paper
• Learning Grammars and Automata with Queries

  2016cites this paper
• Boosting Nonparametric Policies

  2016cites this paper
• Sample compression schemes for VC classes

  2015cites this paper
• Complementarity In Data Mining

  2015cites this paper
• Compressing and Teaching for Low VC-Dimension

  2015cites this paper
• Complexity theoretic limitations on learning halfspaces

  2015cites this paper
• PUF-based Hardware and Software Active IP Protection

  2014cites this paper
• Complexity Theoretic Limitations on Learning DNF's

  2014influential citation
• Large Margin Distribution Learning

  2014cites this paper
• The Evolution of Boosting Algorithms

  2014cites this paper
• Learning from combination of data chunks for multi-class imbalanced data

  2014cites this paper
• Regression Trees and Rule-Based Models

  2013cites this paper
• A Short Tour of the Predictive Modeling Process

  2013cites this paper
• Factors That Can Affect Model Performance

  2013cites this paper
• On-Line Boosting Tracking Based on Color Information and Haar-Like Features

  2013cites this paper
• Linear Regression and Its Cousins

  2013cites this paper
• From average case complexity to improper learning complexity

  2013influential citation
• An Introduction to Feature Selection

  2013cites this paper
• Classification Trees and Rule-Based Models

  2013cites this paper
• Remedies for Severe Class Imbalance

  2013cites this paper
• Margins, Shrinkage, and Boosting

  2013cites this paper
• Empirical Risk Minimization for Probabilistic Grammars: Sample Complexity and Hardness of Learning

  2012cites this paper
• Machine Learning - The Art and Science of Algorithms that Make Sense of Data

  2012cites this paper
• Securing netlist-level FPGA design through exploiting process variation and degradation

  2012cites this paper
• Global Reweighting and Weight Vector Based Strategy for Multiclass Boosting

  2012cites this paper
• The learnability of abstract syntactic principles.

  2011cites this paper
• Automatic citrus canker detection from leaf images captured in field

  2011cites this paper
• Application of Streaming Algorithms and DFA Learning for Approximating Solutions to Problems in Robot Navigation

  2011cites this paper
• Autonomous Learning of Action Models for Planning

  2011cites this paper
• CORES: fusion of supervised and unsupervised training methods for a multi-class classification problem

  2011cites this paper
• Formal and Empirical Grammatical Inference

  2011cites this paper
• Unsupervised Learning and Grammar Induction

  2010cites this paper
• Grammatical Inference: Learning Automata and Grammars

  2010cites this paper
• Computational Learning Theory

  2010cites this paper
• L'Inférence Grammaticale au pays des Apprentissages Automatiques : Discussions sur la coexistence de deux disciplines

  2010cites this paper
• Lower Bounds on Learning Random Structures with Statistical Queries

  2010cites this paper
• Learning to Create is as Hard as Learning to Appreciate.

  2010cites this paper
• Multilinear Subspace Learning for Face and Gait Recognition

  2009cites this paper
• KKL, Kruskal-Katona, and Monotone Nets

  2009cites this paper
• New perspectives on the complexity of computational learning, and other problems in theoretical computer science

  2009cites this paper
• Intrinsic Geometries in Learning

  2009cites this paper
• The AdaBoost Algorithm with Prior Probabilities and the Visualization Demonstrated in GIS for Geo-hazard Forecasting

  2009cites this paper
• Learning Languages from Bounded Resources: The Case of the DFA and the Balls of Strings

  2008influential citation
• Disappearing Cryptography: Information Hiding: Steganography and Watermarking

  2008cites this paper
• Learnability, representation, and language: a bayesian approach

  2008cites this paper
• On the Prospects for Building a Working Model of the Visual Cortex

  2007cites this paper
• Learning Finite-State Transducers: Evolution Versus Heuristic State Merging

  2007cites this paper
• A statistically aligned recombination operator for finite state machines

  2007cites this paper
• Real Boosting a la Carte with an Application to Boosting Oblique Decision Tree

  2007influential citation
• Data Complexity Issues in Grammatical Inference

  2006cites this paper
• Minimizing DNF formulas and AC/sup 0//sub d/ circuits given a truth table

  2006cites this paper
• Extraction de données et apprentissage automatique pour les sites web adaptatifs

  2006cites this paper
• Learning Stochastic Logical Automaton

  2006cites this paper
• Identification in the Limit of Systematic-Noisy Languages

  2006cites this paper
• Learning invariant features using inertial priors

  2006cites this paper
• New Results for Learning Noisy Parities and Halfspaces

  2006influential citation
• Languages as hyperplanes: grammatical inference with string kernels

  2006cites this paper
• A survey of neural network ensembles

  2005cites this paper
• A bibliographical study of grammatical inference

  2005cites this paper
• Learning deterministic finite automata with a smart state labeling evolutionary algorithm

  2005cites this paper
• Learning from data with complex interactions and ambiguous labels

  2005cites this paper
• Progressing the state-of-the-art in grammatical inference by competition

  2005cites this paper
• Application of automata learning algorithms to robot motion tracking

  2005cites this paper