Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PERCEPTRON:
Reports tagged with Perceptron:
TR98-061 | 29th September 1998
Robert H. Sloan, Ken Takata, György Turán

On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the
columns is frequent if there are at least t rows having a 1 entry in
each corresponding position. This concept is used in the algorithmic,
combinatorial approach to knowledge discovery and data mining. We
consider the complexity aspects ... more >>>


TR06-061 | 5th May 2006
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Learning Halfspaces with Noise

Learning an unknown halfspace (also called a perceptron) from
labeled examples is one of the classic problems in machine learning.
In the noise-free case, when a halfspace consistent with all the
training examples exists, the problem can be solved in polynomial
time using linear programming. ... more >>>


TR25-018 | 27th January 2025
Neekon Vafa, Vinod Vaikuntanathan

Symmetric Perceptrons, Number Partitioning and Lattices

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq ... more >>>




ISSN 1433-8092 | Imprint