Complex analysis methods
The talk is about a method for estimating
Bell's number, which is the number of ways of partitioning
n elements. We will be trying to understand how fast Bell's number
grows, using the probabilistic method, taylor series, etc
to get the bound. Knowledge of Complex theory key.
On Seller Optimal Envy-Free Pricing
Jason Hartline, Microsoft Research
We consider the computational problem a monopolistic store owner faces when setting prices for the items for sale. Given the true combinatorial valuations of a set of consumers for the sale items, we look for pricings for the individual items such that
a) there is no squabbling between consumers (when they are all in the store at once). I.e, the pricing induces an envy-free allocation in which every consumer can obtain their utility maximizing allocation of items as if they were the only shopper in the store.
b) the seller's profit is optimized.
We consider the unit demand special case of this problem in which each consumer is assumed to want at most one item (e.g., sale of houses, or movies on airline flights). We review some pricing techniques from game-theory and use them to get a log-approximation. We show that a special case of this unit demand problem is APX-hard.
Finally, we consider the mechanism design problem of actually selling the items when the demands of the consumers are not publicly known in advance (and give a log approximation).
This is joint work with Anna Karlin and Claire Kenyon.
Multiobjective Optimization: Finding All Relevant Solutions
While the number of undominated solutions to a multiobjective
optimization problem may be exponential, the number of solutions that
are approximately optimal is polynomial. We show a short proof of this
fact, and describe algorithms (along with lower bounds) for computing
the smallest such solution sets (also known as $\epsilon$-Pareto
curves). Time permitting, we will present some of the many open problems
in this area.
This is joint work with Mihalis Yannakakis.
Fritz John's Theorem
Man-Cho Anthony So
One form of John's Theorem states that every convex body K contains an
unique ellipsoid of maximal volume (and hence by duality, K is contained in
an unique ellipsoid of minimal volume). Such ellipsoids are not just of
pure mathematical interest. They are employed in, e.g. the ellipsoid method
for linear programming. John's Theorem also gives a characterization of
such ellipsoids. In this talk I will present a proof of this
characterization using tools from functional analysis.
Complexity Results for the Protocol Insecurity Decision Problem
The verification of cryptographic protocols became of great importance
with the developpement of communications and transactions on public
channels, like internet. In this talk, I will present some complexity
results for the protocol insecurity decision problem. These results use
(and try to weaken) the hypothesis of cryptographic primitives
reliability like the encryption. Indeed, many well known attacks rely
only on specification weaknesses. Moreover, results introducing some
properties of the cryptographic primitives will be presented, like
algebraic properties and key commutation
Checking polynomials for positive semi-definiteness
Given a $n$-variable, degree-$m$ polynomial $p$, with real
coefficients, we ask if $ p \geq 0$ over the reals. Such polynomials
are called positive semi-definite (psd). An efficient solution to this
problem is useful in the analysis of systems with
non-linear dynamics. However, the problem is known to be NP-hard for
A natural "relaxation" is to check if the polynomial in question can
be expressed as a sum of squares of other polynomials. Such
polynomials are called "sums of squares"(sos). In 1888,
Hilbert showed that not every psd is a sos. Furthermore,
he outlined *exactly* three instances (m=2, n=1, (m=4 and n=3)) where
these two notions co-incide. A recent paper by
P. Parrilo uses semi-definite programming to tackle this problem.
Time permitting, I will show some more useful relaxations based on
Error-correction mechanisms for self assembly
Self-assembly is the ubiquitous process by which objects autonomously
assemble into complexes. Nature provides many examples: Atoms react to
form molecules. Molecules react to form crystals and supramolecules. Cells
sometimes coalesce to form organisms. It is widely believed that self-
assembly will ultimately become an important technology, enabling the
fabrication of great quantities of small complex objects such as computer
circuits. DNA has emerged as an important component to use in self-
assembly of nano-scale systems due to its small size, its incredible
versatility, and the precedent set by the abundant use of DNA self-
assembly in nature. Accordingly, DNA self-assembly has received
significant attention over the last few years. I will talk about a
thermodynamic model of DNA self-assembly and use it to analyze some of the
error correction mechanisms.
Affine Relationships Among Variables of a Program
The static analysis community is familiar with abstract interpretation, a
general framework introduced in P. Cousot's and R. Cousot's 1976 paper.
Prior to this work, Michael Karr published his "Affine Relationships Among
Variables of a Program" (1976). It "presents a practical approach to
detecting [equality relationships that hold between a linear combination
of the program variables and a constant] by considering the problem from
the viewpoint of linear algebra." Besides being a beautifully written
paper, it motivated the general framework of abstract interpretation. I
will present the main results of the paper.
Testing Modular Systems via Edge Covering
We consider a graph optimization problem that arises in the testing of
systems. Our focus is on systems composed of modules, each of which is
modelled by a finite state machine. In this context, a test of a system
corresponds to a path in a directed graph representing the system. We
are interested in finding a small set of tests with a desired fault
coverage for a system. We formulate this problem using network flows,
and discuss approximation algorithms and hardness results for it.
This is joint work with Mihalis Yannakakis.