[math-ias] IAS TCS/DM Seminars -- Week of November 26, 2012

[Dottie Phares]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
 
Theoretical Computer Science/Discrete Math Seminars
Week of November 26, 2012
 
 
 
 
Monday, November 26
 
Computer Science/Discrete Mathematics Seminar I
Topic:                    Polynomial Identity Testing of Read-Once Oblivious
Algebraic Branching Progress
Speaker:               Michael Forbes, Massachusetts Institute of Technology
Time/Room:         11:15am - 12:15pm/S-101
Abstract:               See below
 
 
 
Tuesday, November 27
 
Computer Science/Discrete Mathematics Seminar II
Topic:                    Computational Complexity in Mechanism Design
Speaker:               Jing Chen, Massachusetts Institute of Technology;
Member, School of Mathematics
Time/Room:         10:30am - 12:30pm/S-101
Abstract:               See below
 
 
 
1             Polynomial Identity Testing of Read-Once Oblivious Algebraic
Branching Progress
               Michael Forbes
 
Polynomial Identity Testing (PIT) is the problem of identifying whether a
given algebraic circuit
computes the identically zero polynomial. It is well-known that this problem
can be solved with
small error probability by testing whether the circuit evaluates to zero on
random evaluation
points.  Recently, there has been much interest in solving this problem
deterministically, because
it has close connections with circuit lower bounds, and this problem is now
one of the frontiers of
the area of pseudorandomness.
 
The method of partial derivatives is a fairly successful technique for
understanding algebraic
computation. Nisan used this method to show exponential lower bounds for
non-commutative branching
programs, a natural model of computation at least as powerful as formulas.
Later, Raz and Shpilka
used the method develop a polynomial-time "white box" PIT algorithm for
non-commutative branching
programs, where this algorithm can "look" at the structure of the branching
program. In this work,
we extend the partial derivative method to the "black box" PIT setting for
read-once oblivious
branching programs, by deriving a quasi-polynomial-time algorithm that
solves PIT by only evaluating
the branching program at chosen locations. As a corollary, we also derive
similar results for
non-commutative branching programs.
 
Joint work with Amir Shpilka
 
 
 
2             Computational Complexity in Mechanism Design
               Jing Chen
 
Some important mechanisms considered in game theory require solving
optimization problems that are
computationally hard. Solving these problems approximately may not help, as
it may change the
players' rational behavior in the original mechanisms, leading to
undesirable outcomes. This is
particularly the case in combinatorial auctions.
 
I'll present special cases of combinatorial auctions where approximation
algorithms do lead to
mechanisms that are both computationally efficient and economically well
behaved. If time allows,
I'll also present conditions under which such mechanisms do not exist.
 
 
 
Computer Science/Discrete Math Seminars can be found on our web page:













 














 
http://www.math.ias.edu/csdm













 
http://www.math.ias.edu

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121120/9c661137/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Nov26_CSDM.pdf
Type: application/pdf
Size: 3537 bytes
Desc: not available
URL: <http://imap.math.ias.edu/mailman/private/all/attachments/20121120/9c661137/attachment-0001.pdf>