[CSDM] [pvsnp-all] Fwd: [Theory-Read] Uri Zwick at theory lunch this Friday @11:45

[Mark Braverman]

Reminder: this is now!

----- Forwarded Message -----
From: "Mark Braverman" <mbraverm at CS.Princeton.EDU>
To: "expeditions project list" <pvsnp-all at lists.cs.princeton.edu>, theory-read at lists.cs.princeton.edu
Cc: zwick at tau.ac.il
Sent: Thursday, February 14, 2013 3:34:54 PM
Subject: [Theory-Read] Uri Zwick at theory lunch this Friday @11:45

Hi All,

Uri Zwick will speak at the theory lunch this week.

Food will be served at 11:45, @CS Building, room 402.

Title & abstract are below.

TITLE:
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

ABSTRACT:
The simplex algorithm is among the most widely used algorithms for solving
linear programs in practice. Most deterministic pivoting rules are known,
however, to require an exponential number of steps to solve some linear
programs. No non-polynomial lower bounds were known, prior to this work, for
randomized pivoting rules. We provide the first subexponential (i.e., of the
form $2^{\Omega(n^\alpha)}$, for some $\alpha>0$) lower bounds for the two most
natural, and most studied, randomized pivoting rules suggested to date.

The first randomized pivoting rule we consider is Random-Edge, which among all
improving pivoting steps (or edges) from the current basic feasible solution
(or vertex) chooses one uniformly at random. The second randomized pivoting
rule we consider is Random-Facet, a more complicated randomized pivoting rule
suggested by Kalai (1992) and Matou{\v{s}}ek, Sharir and Welzl (1996).

Our lower bound for the Random-Facet pivoting rule essentially matches the
subexponential upper bounds of Kalai and Matou{\v{s}}ek et al. Lower bounds for
Random-Edge and Random-Facet were known before only in abstract settings, and
not for concrete linear programs.

Our lower bounds are obtained by utilizing connections between pivoting steps
performed by simplex-based algorithms and improving switches performed by
policy iteration algorithms for 1-player and 2-player games. We start by
building 2-player parity games (PGs) on which suitable randomized policy
iteration algorithms perform a subexponential number of iterations. We then
transform these 2-player games into 1-player Markov Decision Processes
(MDPs) which correspond almost immediately to concrete linear programs.

Joint work with Thomas Dueholm Hansen and Oliver Friedmann
_______________________________________________
Theory-Read mailing list
Theory-Read at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/theory-read
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all