- Series
- ACO Student Seminar
- Time
- Friday, April 8, 2016 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Samantha Petti – Georgia Tech
- Organizer
- Yan Wang

Motivated by neurally feasible computation, we study Boolean functions
of an arbitrary number of input variables that can be realized by
recursively applying a small set of functions with a constant number of
inputs each. This restricted type of construction is neurally feasible
since it uses little global coordination or control. Valiantâ€™s
construction of a majority function can be realized in this manner and,
as we show, can be generalized to any uniform threshold function. We
study the rate of convergence, finding that while linear convergence to
the correct function can be achieved for any threshold using a fixed set
of primitives, for quadratic convergence, the size of the primitives
must grow as the threshold approaches 0 or 1. We also study finite
realizations of this process, and show that the constructions realized
are accurate outside a small interval near the target threshold, where
the size of the construction at each level grows as the inverse square
of the interval width. This phenomenon, that errors are higher closer to
thresholds (and thresholds closer to the boundary are harder to
represent), is also a well-known cognitive finding. Finally, we give a
neurally feasible algorithm that uses recursive constructions to learn
threshold functions. This is joint work with Christos Papadimitriou and
Santosh Vempala.