Crytographic limitations on learning Boolean formulae and finite automata

Computers and Intractability: A Guide to the Theory of NP-Completeness

1979 • 45,565 citations

A method for obtaining digital signatures and public-key cryptosystems

1983 • 13,118 citations

A theory of the learnable

1984 • 4,471 citations

A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

1952 • 3,575 citations

How to construct random functions

1986 • 2,086 citations

Learning regular sets from queries and counterexamples

1987 • 2,050 citations

Theory and application of trapdoor functions

1982 • 1,080 citations

Occam's Razor

1987 • 1,044 citations

DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION

1979 • 1,040 citations

Computational limitations on learning from examples

1988 • 542 citations

RSA and Rabin Functions: Certain Parts are as Hard as the Whole

1988 • 339 citations

On the learnability of Boolean formulae

1987 • 311 citations

Constant Depth Reducibility

1984 • 307 citations

Log Depth Circuits for Division and Related Problems

1986 • 244 citations

Learning disjunction of conjunctions

1985 • 179 citations

Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

1986 • 168 citations

Training a 3-node neural network is NP-complete

1988 • 156 citations

A general lower bound on the number of examples needed for learning

1988 • 131 citations

On taking roots in finite fields

1977 • 121 citations

One-way functions and pseudorandom generators

1985 • 94 citations

Primality and Cryptography.

1988 • 79 citations

Equivalence of models for polynomial learnability

1988 • 76 citations

Learnability by fixed distributions

1988 • 70 citations

The minimum consistent DFA problem cannot be approximated within and polynomial

1989 • 52 citations

On Threshold Circuits and Polynomial Computation

1987 • 52 citations

Reductions among prediction problems: on the difficulty of predicting automata

1988 • 51 citations

Learning in neural networks

1988 • 47 citations

The minimum consistent DFA problem cannot be approximated within any polynomial

2003 • 46 citations

A new approximate graph coloring algorithm

1982 • 20 citations

An O(n^0.4)-approximation algorithm for 3-coloring

1989 • 18 citations

On the learnability of finite automata

1988 • 17 citations