We give new results on the number-on-the-forhead (NOF)
communication complexity of the multiparty pointer jumping
problem.
The origional motivation for this problem comes from circuit
complexity. Specifically, there is no explicit function known
to...
In the aftermath of several great imperial expansions,
especially those of the Arabs and the Europeans, one sees the
phenomenon of the native who has accepted the religion and/or
culture of the hegemonic foreigners, only to rediscover his
native...
I will discuss the Green-Tao proof for existence of arbitrarily
long arithmetic progressions in the primes. The focus will
primarily be on the parts of the proof which are related to notions
in complexity theory. In particular, I will try to...
Research in the area of privacy of data analysis has been
flourishing recently, with a rigorous notion such as differential
privacy regarding the desired level of privacy and sanitizing
algorithms matching the definition for many problems. Most
of...
The quest for understanding the origin of our universe has been
dramatically transformed since the expansion of the universe was
discovered by Edwin Hubble in 1929, thanks to impressive advances
in astronomical observations and laboratory...
I will first give an overview of several constructions of graph
sparsifiers and their properties. I will then present a method of
sparsifying a subgraph W of a graph G with optimal number of edges
and talk about the implications of subgraph...
I will survey some constructions of expander graphs using
variants of Kazhdan property T . First, I describe an approach to
property T using bounded generation and then I will describe a
recent method based on the geometric properties of...
An XOR game is a very simple model of evaluating a distributed
function f(x,y) . With probability p(x,y) a Verifier sends
questions x, y to Alice and Bob, respectively. Without
communicating, Alice and Bob then output a, b in {-1,+1} in the
hope...