Georgia Institute of Technology College of Sciences

Algorithms and Randomness Center (ARC) Theory Day is an annual event, to showcase lectures on recent exciting developments in theoretical computer science. This year's inaugural event features four young speakers who have made such valuable contributions to the field. In addition, this year we are fortunate to have Avi Wigderson from the Institute for Advanced Study (Princeton) speak on fundamental questions and progress in computational complexity to a general audience. See the complete list of titles and times of talks.

Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.

Chromatic derivatives are special, numerically robust linear differential operators which provide a unification framework for a broad class of orthogonal polynomials with a broad class of special functions. They are used to define chromatic expansions which generalize the Neumann series of Bessel functions. Such expansions are motivated by signal processing; they grew out of a design of a switch mode power amplifier. Chromatic expansions provide local signal representation complementary to the global signal representation given by the Shannon sampling expansion. Unlike the Taylor expansion which they are intended to replace, they share all the properties of the Shannon expansion which are crucial for signal processing. Besides being a promising new tool for signal processing, chromatic derivatives and expansions have intriguing mathematical properties connecting in a novel way orthogonal polynomials with some familiar concepts and theorems of harmonic analysis. For example, they introduce novel spaces of almost periodic functions which naturally correspond to a broad class of families of orthogonal polynomials containing most classical families. We also present a conjecture which generalizes the Paley Wiener Theorem and which relates the growth rate of entire functions with the asymptotic behavior of the recursion coefficients of a corresponding family of orthogonal polynomials.

Information processing in neurons and their networks is understood incompletely, especially when neuronal inputs have indirect correlates with external stimuli as for example in the hippocampus. We study a case when all neurons in one network receive inputs from another network within a short time window. We consider it as a mapping of binary vectors of spiking activity ("spike" or "no spike") in an input network to binary vectors of spiking activity in the output network. Intuitively, if an input pattern makes a neuron spike then the neuron should also spike in response to similar patterns - otherwise, neurons would be too sensitive to noise. On the other hand, neurons should discriminate between sufficiently different input patterns and spike selectively. Our main goal was to quantify how well neurons discriminate input patterns depending on connectivity between networks, spiking threshold of neurons and other parameters. We modeled neurons with perceptrons that have binary weights. Most recent results on perceptron neuronal models are asymptotic with respect to some parameters. Here, using combinatorial analysis, we complement them by exact formulas. Those formulas in particular predict that the number of the inputs per neuron maximizes the difference between the neuronal and network responses to similar and distinct inputs. A joint work with Jean Vaillant (UAG).