In this seminar I will discuss the details of the result that
knottedness is in NP assuming the generalized Riemann hypothesis.
The main part of the work is to properly understand Koiran's
construction that solvability of a system of algebraic...
This talk will be a partial survey of the first questions in the
complexity theory of geometric topology problems. What is the
complexity, or what are known complexity bounds, for distinguishing
n-manifolds for various n? For distinguishing knots...
One powerful theme in complexity theory and pseudorandomness in
the past few decades has been the use of lower bounds to give
pseudorandom generators (PRGs). However, the general results using
this hardness vs. randomness paradigm suffer a...
Gowers' uniformity norms are defined by average of a function
over specific sets of linear forms. We study norms that are
similarly defined by a system of linear forms. We prove that for
bounded complex functions over $F_p^n$, each such norm is...
We consider the problem of constructing pseudorandom generators
for read-once circuits. We give an explicit construction of a
pseudorandom generator for the class of read-once constant depth
circuits with unbounded fan-in AND, OR, NOT and...
Shannon's notion of entropy measures the amount of "randomness"
in a process. However, to an algorithm with bounded resources, the
amount of randomness can appear to be very different from the
Shannon entropy. Indeed, various measures of...
A property of finite graphs is called nondeterministically
testable if it has a "certificate'' such that once the certificate
is specified, its correctness can be verified by random local
testing. In this talk we consider certificates that consist...
The goal of the Balanced Separator problem is to find a balanced
cut in a given graph G(V,E), while minimizing the number of edges
that cross the cut. It is a fundamental problem with applications
in clustering, image segmentation, community...
