We will give a motivation for the EGC approach, which has been useful  
in handling robustness issues in Computational Geometry. The approach,  
however, is applicable in the more general setting of Numerical  
Analysis. We will give a computational model suitable for the approach  
(i.e., define what it means for a function to be computable in the EGC  
approach), and show why some of the existing models of real  
computation are inadequate in describing the EGC approach.

We sketch how deformations, Groebner basis theory and Puiseasux series
lead to a bound on the algebraic degree of an isolated solution to a system
of polynomial equations with rational coefficients. This problem arises
in the computation of the value of Shapley games.

The classes PNC^1 and C=NC^1, defined by a test for positivity and a
test for zero, respectively, of arithmetic circuit families of
logarithmic depth, sit between NC^1 and DLog. The oracle hierarchies
above these classes can be characterised by logarithmic depth
arithmetic circuits augmented with boolean test gates. We study such
circuits, and show the following:

1. for positivity tests, if the nesting depth of test-gates is a
   constant, it can be brought down to 1 test gate at the root. (Thus,
   the PNC^1 hierarchy collapses.)

2. for equality tests, we have a more nuanced outcome:
   If the test-gate-depth is just 1, and if the test-gates are O(1)
   distance below the root, then such circuits can test feasibility of
   small systems of linear equations with GapNC1-computable
   coefficients. This is in fact an equivalence, characterizing the
   Boolean Hierarchy over C=NC^1.

   If the test-gate-depth is a constant, it can be reduced to one, and
   the sub-circuit above the test-gates needs only three alternations.
   Thus, the C=NC^1 hierarchy collapses to somewhere between its first
   and second levels.

In this talk we will cover exact threshold functions from a number of
perspectives. First a survey of research on constant depth threshold
circuits is given followed by a detailed introduction of exact
threshold functions and corresponding pure circuit classes they give
rise to. Relationships between threshold circuits and exact threshold
counterparts are covered.

Next exact threshold functions are studied as models of representing
Boolean functions. Results about bounds on the magnitude of integer
weights of exact threshold functions are covered.

Finally is given an overview of other uses of exact treshold functions
in Boolean circuit complexity.

The talk is based on joint work Laci Babai, Vladimir Podolskii and
Xiaoming Sun.

Determining a Nash equilibrium in a $2$-player
non-zero sum game is known to be PPAD-hard (Chen et al.)
The problem, even when restricted to bimatrix win-lose games,
remains PPAD-hard  (Abbott et al). However, there do exist
polynomial time tractable classes of win-lose, bimatrix games -
such as, very sparse games (Codenotti et al.) and planar games
(Addario-Berry et al.).

We extend the results in the latter work to $K_{3,3}$-minor free
games. We also explore the possibility of further extending these
results to certain sub-classes of $K_5$-minor free games.

This is work under progress (joint work with Nagarajan
Krishnamurthy, CMI)

A fundamental model of operations research is the finite, but
infinite-horizon, discounted Markov Decision Process. Ye showed
recently that the simplex method with Dantzig pivoting rule, as well
as Howard's policy iteration algorithm, solve discounted Markov
decision processes, with a constant discount factor, in strongly
polynomial time. More precisely, Ye showed that for both algorithms
the number of iterations required to find the optimal policy is
bounded by a polynomial in the number of states and actions. We
improve Ye's analysis in two respects. First, we show a tighter bound
for Howard's policy iteration algorithm. Second, we show that the same
bound applies to the number of iterations performed by the strategy
iteration (or strategy improvement) algorithm used for solving
2-player turn-based stochastic games with discounted zero-sum
rewards. This provides the first strongly polynomial algorithm for
solving these games.

Joint work with Peter Bro Miltersen and Uri Zwick.

In this talk we will motivate and discuss the problem of proving lower
bounds for constant-width arithmetic circuits.

By Ben-Or and Cleve's result, width-three arithmetic branching
programs are at least as powerful as arithmetic formulas, and this
holds both in the commutative and noncommutative settings. By a rank
argument, Nisan, in 1991, showed exponential size lower bounds for
noncommutative algebraic branching programs. Can we extend Nisan's
method to prove size lower bounds for noncommutative bounded-width
circuits?

Proving superpolynomial lower bounds even for width-two noncommutative
arithmetic circuits is an open problem. These circuits are universal
(they can compute all polynomials). In particular, width-two
noncommutative circuits can compute some polynomials that do not have
subexponential size noncommutative algebraic branching programs.
Thus, we need a different method than Nisan's rank argument to prove
lower bounds even for such circuits.

Finally, we discuss monotone constant-width circuits. For every
positive integer $k>1$, we provide an explicit polynomial that can be
computed by a linear-sized monotone circuit of width (and even depth)
$2k$ but has no subexponential-sized monotone circuit of width $k$. It
follows, from the definition of the polynomial, that the
constant-width and the constant-depth hierarchies of monotone
arithmetic circuits are infinite, both in the commutative and the
noncommutative settings.

(This is joint work with Pushkar Joglekar and Srikanth Srinivasan.)

We present the first fully dynamic algorithm for computing the
characteristic polynomial of a matrix.  In the generic symmetric case
our algorithm supports rank-one updates in almost quadratic randomized
time and queries in constant time, whereas in the general case the
time in addition grows linearly in the number of invariant factors of
the matrix. The algorithm is based on the first dynamic algorithm for
computing normal forms of a matrix such as the Frobenius normal form
or the tridiagonal symmetric form. The algorithm can be extended to
solve the matrix eigenproblem in time that additionally grows linearly
with the logarithm of the inverse relative error. Furthermore, it can
be used to dynamically maintain the singular value decomposition (SVD)
of a generic matrix.  Together with the algorithms the hardness of the
problem is studied. For the symmetric case we present a quadratic
lower bound for rank-one updates and a linear lower bound for element
updates. 

Joint work with Piotr Sankowski.

This talk will be about some of recent results
concerning the power of bounded treewidth circuits. The treewidth of a
circuit is the treewidth of the underlying undirected graph. This
notion can be used to study generalisations of formulas and bounded
width circuits.

The talk will describe simulations of circuits of size $s$ and
treewidth $k$ by formulas of size $s^{k^2}$. We will also show that
circuits of width $O(\log^i n)$ can be simulated by circuits of
treewidth $O(\log^i n)$ which in turn can be simulated by circuits of
width $O(\log^{i+1} n)$ with slight blow up in size. We show this in
the arithmetic and Boolean setting but will present the proofs in the
arithmetic setting that uses a restriction of multiplicative
disjointness. This is joint work with Maurice Jansen.

We also will touch upon the relation ship between the number of
negations and treewidth of a circuit. We show that any Boolean
function $f$ can be computed by a circuit of treewidth at most $\lceil
\log(d(f)+1) \rceil$ which uses at most $\lceil \log(d(f)+1) \rceil$
negations, where $d(f)$ is a measure of non-monotonicity of $f$ called
the {\sf decrease}. More generally, there is a circuit (that can be
constructed) of treewidth at most $k$ that uses $d(f).\frac{8k}{2^k}$
computing any Boolean function $f$. In addition, we also show that
this can be done in a size-efficient way: if $f$ can be computed by
circuits treewidth $k$ of size $s$, then there is a circuit computing
$f$ of treewidth $2k$, size $s.n^{O(1)}.2^{\min \{k,\log n\}}$, and
that uses at most $O(\max\{nk/2^{2k}, \log n\})$ negations. This is
joint work with Jing He and Hongyu Liang.

Let $G$ be a group acting on a complex variety $V$. Given
two points $x,y$ in $V$ a fundamental problem of interest is to decide
if $y$ is in the orbit closure of $x$, the closure taken in complex
topology. This is the fundamental problem which arises in the
geometric complexity theory approach to seperating complexity classes,
proposed by Mulmuley and Sohoni. I will give an introduction to this
problem as it appears in GCT. Recently Burgisser and Ikenmeyer show
that the natural framwork to understand the border rank of a tensor is
also as an orbit closure problem. I will discuss this too in the
talk. In a joint paper with Bharat Adsul we give a geometric solution
to the Kronecker problem in the two row case. This solution requires
understanding orbit closures of points in $\mathbb{C}^2 \otimes
\mathbb{C}^2 \otimes \mathbb{C}^2 $ under the action of $GL(2) \times
GL(2) \times GL(2)$. I will discuss this.

We prove that the pseudorandom generator introduced in Impagliazzo et
al. (1994) fools group products of a given finite group. The seed
length is $O(\log n \log {1 / \epsilon})$, where $n$ is the length of
the word and $\epsilon$ is the error. The result is equivalent to the
statement that the pseudorandom generator fools read-once permutation
branching programs of constant width.

Joint work with Michal Koucky, Pavel Pudlak

Concurrent reachability games is a special case of Everett's recursive
games.  It is a class of games heavily studied by the computer science
community, in particular by the formal methods community. Two standard
algorithms for approximately solving two-player zero-sum concurrent
reachability games are value iteration and strategy iteration.  A
rigorous complexity analysis of these algorithms has been an open
problem until now.  We prove doubly exponential lower and upper bounds
on the worst case number of iterations needed for both of these
algorithms to provide non-trivial approximations to the value of a
given game. Also, even when the game given as input has only one
non-terminal position, we prove an exponential lower bound on their
time complexities. The instances establishing the lower bound may be
regarded as natural rather than pathological and our proofs of the
lower bounds proceed by arguing about these instances as games, using
game-theoretic concepts and tools.

Joint work with Kristoffer Arnsfelt Hansen and Peter Bro Miltersen

This talk would focus on the following special case of polynomial
identity testing for depth 4 circuits:
   	
Given as input a polynomial f(x_1,...,x_n) explicitely (as a sum
of monomials) and a purported factorization of f of the form
\Prod g_i(x_1,...,x_n)^{e_i} where each polynomial g_i is also
given explicitely, check if the factorization is valid.

Naive approaches to keep dividing f by the factors provided won't work
since the number of monomials in f/g_i could be very large compared to
those in f. Also, it is non-trivial to even check if a linear function
l divides f or not. 

In this talk, we shall present some partial results towards this
problem -- we'll see that the above problem can be done in deterministic
polynomial time if each purported g_i(x_1,...,x_n) is a sum of
univariates. 

This is joint (ongoing) work with Chandan Saha (IIT Kanpur) and Nitin
Saxena (Hausdorff Center for Mathematics, Bonn).

We present a new construction of log-depth formulae for the majority
function based on 2-out-of-3 threshold gates. From this, we build a
new family of linear integer secret sharing schemes that are
multiplicative, allow for efficient (approximate) secure integer
division and scale well as the number of players increases. Our
construction is the first with these properties, and we show how it
can be used in distributed RSA key generation. We also show some
positive results on local conversion of shares in our scheme to a
class of other schemes and a negative result on usage of our scheme
for pseudorandom secret sharing as defined by Cramer, Damgård and
Ishai.

Motivated by the Hadamard product of matrices we define the Hadamard
product of multivariate polynomials and study its arithmetic circuit
and branching program complexity. We also give applications and
connections to polynomial identity testing. Our main results are
the following

o We show that noncommutative polynomial identity testing for
  algebraic branching programs over rationals is complete for
  the logspace counting class C=L, and over fields of characteristic
  $p$ the problem is in Mod_pL/poly$.
o We show an exponential lower bound for expressing the
  Raz-Yehudayoff polynomial as the Hadamard product of two monotone
  multilinear polynomials. In contrast the Permanent can be expressed
  as the Hadamard product of two monotone multilinear formulas of
  quadratic size.

The "Coin Problem" is the following problem: a coin is given, which
lands on head with probability either 1/2+beta or 1/2-beta. We are
given the outcome of n independent tosses of this coin, and the goal
is to guess which way the coin is biased, and to be correct with
probability >= 2/3. When our computational model is unrestricted, the
majority function is optimal, and succeeds when beta >= c / sqrt(n)
for a large enough constant c. The coin problem is open and
interesting in models that cannot compute the majority function.

In this talk I will present results on the coin problem in the model
of read-once width-w branching programs. We prove that in order to
succeed in this model, beta must be at least 1/ (log n)^{Theta(w)}.
For constant w this is tight by considering the recursive tribes
function. I will also discuss various generalizations and variants of
this.

Finally, I will suggest one application for this kind of theorems:
I'll show that the INW generator epsilon-fools width-w read-once
*permutation* branching programs, using seed length O(logn*loglogn)
when epsilon and w are both constant. I'll also show why we get this
only for permutation branching programs, and what stops us from
getting this for the non-permutation case.

We are looking for applications of the coin problem in other domains
(e.g. streaming lower bounds).

This is joint work with Joshua Brody. Some of this research was done
while at ITCS, Tsinghua University

Hansen, Lachish and Miltersen (ISAAC'09) related a problem of Ajtai to the
difficulty of showing lower bounds against ACC^0. The problem of
Ajtai can be phrased as a problem concerning word circuits. Adler et al
(SODA'06) related the undirected k-pairs conjecture of network coding
to the permuation problem of Aggarwal and Vitter that can also be
phrased as a problem concerning word circuits. We speculate if the
difficulty of the undirected k-pairs conjecture can be gauged using
Boolean circuit complexity.

We present an algorithm for implementing a secure oblivious RAM
where the access pattern is perfectly hidden in the information
theoretic sense, without assuming that the CPU has access to a
random oracle. In addition we prove a lower bound on the amount of
randomness needed for information theoretically secure oblivious
RAM.