Computer Science and Discrete Mathematics (CSDM)

Machine Learning is invaluable for extracting insights from large volumes of data. A key assumption enabling many methods, however, is having access to training data comprising independent observations from the entire distribution of relevant data...

An introduction to Boolean Function Analysis We will discuss some of the basic principles and results in the study of Boolean-valued functions over the discrete hypercube using discrete Fourier analysis. In particular, we will talk about basic...

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it...

The following multi-determinantal algebraic variety plays an important role in algebra and computational complexity theory: SING_{n,m}, consisting of all m-tuples of n x n complex matrices which span only singular matrices. In particular, an...

We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2...