Speaker: Eric Blais
Title: Testing juntas
Date: 2008-04-09 12:00
Place: NSH 1507
Abstract:
A function on $n$ variables is called a $k$-junta if it depends on at most $k$ of the variables. A randomized algorithm $A$ is an algorithm for testing $k$-junta if it can reliably distinguish the case where a given function $f$ is a $k$-junta from the case where $f$ is “far” from being a $k$-junta using only a few queries to $f$. In this talk, we will explore the following question: What is the minimum number of queries required by to test $k$-juntas? Until recently, all known algorithms for testing $k$-juntas required at least $O(k^2)$ queries. I will introduce a new algorithm for testing $k$-juntas with only $O(k^{1.5})$ queries.
Title: Two results in Discrete Differential Geometry
Speaker: Aaron Trout, Chatham University
When: April 3, 12:30-13:30
Where: Porter Hall 125B
Abstract:
We will discuss two results in discrete differential geometry: 1) A combinatorial 3-manifold with edges of degree at most five has edge-diameter at most five. 2) Suppose such a combinatorial 3-manifold $M$ has vertices $v$ and $w$ at the maximum edge-distance. Then, $M$ is a 3-sphere whose triangulation is completely determined by the star of $v$. These theorems are analogous to two important results in the differential geometry of positively curved spaces. The first is analogous to the Bonnet-Myers theorem, which bounds the diameter of Riemannian manifolds whose Ricci curvature is everywhere greater than a fixed positive constant. The second result is a discrete version of the Toponogov-Cheng rigid-sphere theorem, which shows that the maximum diameter allowed by the Bonnet-Myers theorem is achieved only for the standard sphere. The proofs we present are entirely combinatorial in nature, use only elementary arguments, and follow closely the proofs of the corresponding classical results. We will also talk about some enumeration algorithms which can be used to investigate the geometry of combinatorial manifolds. This talk is based on my Ph.D. thesis, which was done at Rice University under the direction of Robin Forman.
Speaker: Christian Klein
Title: Unbiased Controlled Rounding
Date: 2008-04-02 12:00
Place: NSH 1507
Abstract:
Rounding a real-valued matrix to an integer one, such that the rounding errors in all rows and columns are less than one, is a classical problem. It has been applied to hyper-graph coloring, in scheduling and in statistics. Here, it often is also desirable to round each entry randomly such that the probability of rounding it up equals its fractional part. This is known as unbiased rounding in statistics and as randomized rounding in computer science.
In statistics, such roundings are mainly used for two reasons. First, given a table of statistical data, one can increase its readability by rounding each entry to multiples of (some power of) 10. Second, such roundings can be used for statistical disclosure control. Here, one wants to avoid that an attacker can identify individual respondents from the published data.
In this talk, several ways to compute such roundings are presented. They all also ensure some kind of local data consistency that is particularly useful for statistical data, namely that the rounding error in all initial intervals of rows (and columns) is less than one.
Title:Intersection Cuts in 2 Dimensions
Speaker: Francois Margot, CMU
When: March 27, 12:30-13:30
Where: Porter Hall 125B
Abstract:
When solving Mixed Integer Linear Programs (MILP) with branch-and-cut algorithms a variety of cuts can be generated. The best known cuts are probably Gomory mixed integer cuts, obtained from a single row of the optimal simplex tableau for the linear relaxation of the MILP. Recently, results on generating cuts using information from two rows of the tableau have appeared. In particular, Andersen, Louveaux, Wolsey and Weismantel (2007) investigate the facets of a particular relaxation of the MILP to a problem with two integer variables and two constraints. They show that all facets are then split inequalities or intersection cuts obtained from triangles or quadrilaterals. We give the converse, determining which of these splits, triangles and quadrilaterals actually give facets. We also give the corresponding characterization for an infinite-dimensional relaxation of the relaxation of Andersen et al., similarly to the relaxation used by Gomory and Johnson in their study of the group problem. Joint work with Gerard Cornuejols.
Via Punk Rock OR, I wish you will 133.1% agree with this post.
When: 2008-03-25 12:00
Where: NSH 1507
Speaker: Aaron Roth
Title: The Price of Malice in Linear Congestion Games
Abstract:
The price of anarchy has proven to be a useful measure for quantifying the degradation of performance in a system that is populated by selfish agents. However, it is a brittle measure, because it assumes that all users of the system are perfectly rational and adeptly seek to minimize their own cost. In actual networks, this is not always the case! Users may be oblivious to congestion, may be unable to calculate optimal routes, or may be explicitly malicious (consider, for example, denial of service attacks and worms). In this talk, we study the price of malice in traffic routing games, in which users must choose paths on a network to route their flow, and incur traffic dependent latency costs. We quantify by how much Byzantine (possibly malicious) users can degrade social cost. We provide bounds on two measures of the price of malice that have been proposed in the literature, by bounding the price of total anarchy. Bounding the price of malice using the price of total anarchy has the advantage that our bounds on social cost can be plausibly achieved by computationally efficient, decentralized agents who may only be aware of their own costs.
Where: 1507 NSH
When: 2008-03-19 Noon
Speaker: Abe Othman
Title: Beyond the Revelation Principle: Manipulation-Optimal Mechanisms
Abstract:
Rational, self-interested agents will lie to a mechanism if it benefits them. Despite this, the revelation principle states that any outcome a mechanism implements can also be implemented by a mechanism where agents are motivated to tell the truth. In this paper, we introduce the concept of manipulation-optimal mechanisms: non-truthful mechanisms that always do as well as the best truthful mechanism, and strictly better if any agent fails to find/play its best manipulation (lie).
Though the existence of such a mechanism has been shown previously in an artificial context, we study how broadly the paradigm applies in general. We curtail it with an impossibility result: in a manipulation-optimal mechanism, each agent can have at most one manipulable type. For such settings, we show that manipulation-optimal mechanisms can exist if the goal is social welfare maximization, but not when agents are symmetric and the mechanism is anonymous. We also show that there exist anonymous manipulation-optimal mechanisms with the goal of affine welfare maximization, even with symmetric players.
We then explore a way around our impossibility result: natural restrictions on the agents’ strategies. We study the Generalized Second-Price auction used by Google, Yahoo!, and MSN to auction billions of dollars of search keywords annually. This mechanism has been criticized because it is manipulable. Under two common assumptions, however, we show that it is manipulation optimal. Thus, switching to a truthful mechanism could only be deleterious to profits.
Joint work with Tuomas Sandholm.
Name: R. Ravi, Tepper School of Business and Russell Schwartz, Computer Science Department
University: Carnegie Mellon University
Date: Friday, March 7, 2008
Time: 1:30 to 3:00 pm
Location: Room 151 Posner Hall
Title: Mathematical Programming Methods for Phylogeny Reconstruction from Genetic Variation Data
Abstract:
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. We present two integer linear programming (ILP) formulations to find the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven extremely efficient in practice on datasets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics than cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP.
The above methods are applicable for reconstruction of maximum parsimony trees from haplotype data, but such data are difficult to determine directly for autosomal DNA. Data more commonly is available in the form of genotypes, which consist of conflated combinations of pairs of haplotypes from homologous chromosomes. Currently, there are no general algorithms for the direct reconstruction of maximum parsimony phylogenies from genotype data. Hence phylogenetic applications for autosomal data must therefore rely on other methods for first computationally inferring haplotypes from genotypes. We extend our previous methods for computing maximum parsimony phylogenies directly from genotype data. We show that the standard practice of first inferring haplotypes from genotypes and then reconstructing a phylogeny on the haplotypes often substantially overestimates phylogeny size. As an immediate application, our method can be used to determine the minimum number of mutations required to explain a given set of observed genotypes.
Joint work with Srinath Sridhar, Fumei Lam and Guy E. Blelloch.
Time: 2008-03-05 12:00
Place: NSH 1507
Speaker: Deeparnab Chakrabarty
Title: Steiner Trees – Geometry, Linear Programs and Algorithms
Abstract:
In this talk, we investigate the bidirected cut LP relaxation for the Minimum Steiner Tree problem. We use geometry to devise a new lower bound on the cost of any Steiner tree. The lower bound is captured via an LP which we call the simplex-embedding LP. A short description of it is that it is an l_1-embedding of the graph on a simplex, maximizing a certain linear objective function. Interestingly, the dual of the LP turns out to be equivalent to the bi-directed cut relaxation.
For quasi-bipartite graphs, graphs which have no Steiner-Steiner edges, we will show how we improve the upper bound on the integrality gap of our LP relaxation (and hence as well as the bidirected cut LP relaxation). In this talk, we will show an upper bound of $\sqrt{2}$ which improves upon the known 3/2. We will also indicate how this can be further improved to 4/3. In contrast, the best lower bound known is 8/7 by Martin Skutella.
This is joint work with Nikhil R. Devanur and Vijay V. Vazirani.
Title: Coloring triangle-free graphs on surfaces
Speaker: Robin Thomas, Georgia Tech
When: February 28, 12:30-13:30
Where: Porter Hall 125B
Abstract:
Let S be a fixed surface, and let k and q be fixed integers. Is there a polynomial-time algorithm that decides whether an input graph of girth at least q drawn in S is k-colorable? This question has been studied extensively during the last 15 years. In the first part of the talk we will survey known results. In the second part of the talk we describe a solution to one of the two cases left open (the prospects for the other one are not bright). For every surface S we give a polynomial-time algorithm that computes the chromatic number of an input triangle-free graph G drawn in S. The new contribution here is deciding whether G is 3-colorable, and is obtained using a coloring extension theorem that in turn makes use of disjoint paths in order to construct a coloring. The notion of “winding number” of a 3-coloring plays an important role. This is joint work with Zdenek Dvorak and Daniel Kral.
Date: February 27 2008, noon
Location: NSH 1507
Speaker: Daniel Golovin
Title: Uniquely Represented Data Structures with Applications to Privacy
Abstract:
A uniquely represented data structure has a unique physical state to encode each logical state of its abstract data type. In this talk I will discuss new efficient uniquely represented versions of popular data structures (including hash tables, binary search trees, and queues), how these data structures work, and how they can be used to improve the security and privacy of real-world applications.
As an example application, consider a typical system with some internal data structures. If the memory representations of those internal data structures are inspected, they may leave significant clues to the past use of the system. For example, a data structure with lazy deletions might retain an object that the user believes was deleted long ago; this is problematic in environments requiring high security or strict privacy guarantees. Uniquely represented data structures eliminate such problems entirely by storing exactly the information specified by an abstract data type, and nothing more.
I/O-Efficient Algorithms for Computing Contour Lines on a Terrain
Bardia Sadri, Duke University
February 22, 2008, 3:30PM, Wean 7220
Abstract:
A terrain \Sigma is the graph of a bivariate function. We assume that \Sigma is represented as a triangulated surface with n vertices. A contour (or contour line) of \Sigma is a connected component of a level set of \Sigma. Generically, each contour is a closed polygonal curve; at “critical” levels these curves may touch each other. We present I/O-efficient algorithms for the following two problems related to computing contours of \Sigma:
Given two real parameters h and d > 0, we present an I/O-optimal algorithm that report all contours of \Sigma at heights h + kd, for every positive integer k, using O(Sort(N)+T/B) I/Os, where T is the total number edges in the output contours, B is the “block size,” and Sort(N) is the number of I/Os needed to sort N elements. The algorithm uses O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise order. Moreover, our algorithm generates information on how the contours are nested.
We can preprocess \Sigma, using O(Sort(N)) I/Os, into a linear-size data structure so that all contours at a given height can be reported using O(logB N + T/B) I/Os, where T is the output size. Each contour is generated individually with its composing segments sorted in clockwise order.
This is a joint work with Lars Arge, Pankaj K. Agarwal, and Thomas Moelhave.
Title: An Erdos-Stone type theorem for spanning subgraphs
Speaker: Anusch Taraz, Technical University Munich
When: February 21, 12:30-13:30
Where: Porter Hall 125B
Abstract:
In this talk we discuss the proof of the following conjecture by Bollobas and Komlos: Suppose that G and H are both graphs on n vertices, H has bounded maximum degree, chromatic number r, and bandwidth o(n), G has minimum degree at least ((r-1)/r + eps)n, and n is sufficiently large. Then G must contain a copy of H. This is joint work with Julia Boettcher and Mathias Schacht.
Time: 12:00pm 2008-02-19
Place: NSH 1507
Speaker: Yi Wu
Title: An Optimal SDP Approximation Algorithm for Max-Cut
Abstract:
Let $G$ be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a $c$ fraction of the total edge weight, $1/2 \leq c \leq 1$. If the actual optimal cut for $G$ is at most an $s$ fraction of the total edge weight, we say that $(c, s)$ is an SDP gap. We define the SDP gap curve $GapSDP: [1/2, 1] \rightarrow [1/2, 1]$ by $GapSDP(c) = \text{inf} {s : (c, s) \text{ is an SDP gap}}$.
We complete a long line of work by determining the entire SDP gap curve; we show $GapSDP(c) = S(c)$ for a certain explicit (but complicated to state) function $S$. In particular, our lower bound $GapSDP(c) \geq S(c)$ is proved via a polynomial-time ‘$\text{RPR}^2$’ algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is $\text{RPR}^2$ confirms a conjecture of Feige and Langberg.
We also describe and analyze the tight connection between SDP gaps and Long Code tests. Using this connection, we give optimal Long Code tests for Max-Cut. We reach the following conclusions:
- The Max-Cut SDP gap curve subject to triangle inequalities is also given by $S(c)$.
- No $\text{RPR}^2$ algorithm can be guaranteed to find cuts of value larger than $S(c)$ in graphs where the optimal cut is $c$. (Contrast this with the fact that in the graphs exhibiting the $c$ vs. $S(c)$ SDP gap, our $\text{RPR}^2$ algorithm actually finds the optimal cut.)
- Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P != NP and the Unique Games Conjecture.
Sound 3-query PCPPs are long
Prahladh Harsha, TTI Chicago
February 29, 2008, 3:30PM, Wean 7220
Abstract:
The celebrated PCP Theorem [AS+ALMSS] states that any NP proof can be rewritten in such a manner that a probabilistic verifier can check the veracity of the proof by querying the proof in at most a constant number of locations. In this paper, we ask the question if there exist 3-query PCPs that are both short (of size n.\poly\log n) as well as reject proofs of false assertions with probability close to 1/2? In other worlds, can we have the best of the results of both Hastad (3-query PCPs with soundness 1/2-eps but long proofs) and Ben-Sasson-Sudan+Dinur (3-query PCPs with short proofs, but poor soundness)?
We show that any PCP construction that yields PCPs of proximity with similar parameters CANNOT achieve the above property. We obtain this result by studying the trade-off between the length of a PCP of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle access to the proof. Our main result is that a verifier limited to querying a short (i.e, polynomial) proof cannot obtain the same soundness as that obtained by a verifier querying a long (i.e, exponential) proof.
Title: Avoiding small subgraphs in Achlioptas processes
Speaker: Michael Krivelevich, Tel Aviv University
When: February 14, 12:30-13:30
Where: Porter Hall 125B
Abstract:
Consider the following model of random graphs. We are given a monotone graph property P (Hamiltonicity, non-3-colorability, containment of a copy of a fixed graph H etc.) and an integer parameter r>=1. At each round, we are presented with r random edges from the set of edges of the complete graph K_n on n vertices and are asked to choose one of them. The task is to design an online edge choice algorithm that will be able to postpone (avoid) or to facilitate (embrace) almost surely the appearance of P. This model is sometimes called the Achlioptas process, after Dimitris Achlioptas who suggested it for the case r=2 and the property P being the existence of a linear sized connected component (the so called giant component) in the graph. The latter setting is essentially the only one that has been studied extensively so far. In the work to be presented, we were able to achieve a satisfactory solution for the case where the task is to avoid the appearance of a fixed graph H, and H is either a cycle, or a complete graph, or a complete bipartite graph. The answer is quite surprising and depends heavily on the parameter r. For example, the threshold for avoiding K_4 in the Achlioptas process with parameter r=2 is n^{28/19}.
FRIDAY FEBRUARY 15TH
3:30PM
WEH 7220
TITLE: LP-duality Based Algorithms for Restless Bandit Problems
Kamesh Munagala, Duke University
Abstract:
In numerous areas of operations research and artificial intelligence, we face a problem common to gamblers choosing slot machines (or bandits) in a casino: whether to try new machines or keep playing the one we know and hope for the best! More generally, we face the trade-off between exploration and exploitation: between learning from and adapting to a stochastic system and exploiting our current best-knowledge. A model that captures this trade-off is the celebrated Multi-arm Bandit Problem, which was formulated and solved many decades ago, and has since then become a fundamental tool in decision theory. However, in many stochastic applications, we cannot use the basic multi-arm bandit model, but must consider a generalization called the Restless Bandit Problem. Although this problem has been extensively studied, little positive progress has been made. In fact, it has been proven that in its ultimate generality, the restless bandit problem is PSPACE-Hard to approximate to any non-trivial factor.
In this talk, we derive a 2-approximation algorithm for a general subclass of the Restless Bandit Problem, in which the state-transition probability for each bandit is “separable” into a constant probability matrix and a vector of arbitrary monotone functions of time. The monotonicity models increasing levels of uncertainty as time-since-last-observation increases, which occurs in many applications such as in wireless scheduling. The resulting algorithm is simple and intuitive.
To derive the result, we modify a well-known LP relaxation, take its dual, and add a “balance” condition which provides more structure to the LP. From the dual variables, we construct an index policy, and prove that it’s a 2-approximation by using complementary slackness and a potential function argument. Our techniques are fairly clean, yield simple index policies with small approximation factors, and are applicable to related stochastic scheduling problems.
Joint work with Sudipto Guha, UPenn, and Peng Shi, Duke.
Date: 2008-02-13 12:00
Room: NSH 1507
Speaker: Katrina Ligett
Title: A Learning Theory Approach to Non-Interactive Database Privacy
Abstract:
We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial-time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
February 12, 2008
Todd Phillips
10:00 AM, 4623 Wean Hall
Thesis Proposal
Title: Optimal Meshing Algorithms
Abstract:
The meshing problem is to decompose a geometric domain into simple elements that preserve the domain boundary. Meshing algorithms have been used for physical simulation and graphics applications for fifty years, but have only received serious theoretical attention in the last two decades. I propose to address two fundamental algorithmic questions in this area.
Many meshing algorithms require the use of a bounding box to mesh a larger region that contains the domain of interest. The extra elements are then discarded, similar to scaffolding around a construction project. I will provide a new output analysis of such meshing algorithms, where I will show that the number of extraneous scaffold elements is bounded by the number of interesting domain elements. This favorable result ensures that the output-sensitive runtime of such algorithms will depend only on the size of the domain mesh. This same framework shows that a 3D domain volume mesh is asymptotically the same size as a 2D boundary surface mesh, which has deep ramifications for the development of surface reconstruction and surface meshing algorithms.
An important characteristic of a domain to be meshed is the spread ($\Delta$), the ratio of the largest to smallest input feature. I propose the first runtime-optimal meshing algorithm that does not depend on $\Delta$. Previous optimal meshing algorithms work only for inputs with a constant $\log \Delta$ or a constant $\log\log \Delta$ (equivalent to fixed-length integer or floating-point models). Essential to the algorithm is a new eager point-location strategy. Novel low-entropy sorting techniques are developed for bucketing uninserted points. The algorithm also relies on centervertices, a new geometric construction related to centerpoints.
My research will also address related open questions on size-optimality for meshing algorithms.
Thesis Committee:
Gary L. Miller, Chair
Anupam Gupta
Daniel Sleator
Noel Walkington
Tamal Dey, Computer Science and Engineering, Ohio State
Title: Lehman Matrices
Speaker: Gerard Cornuejols
When: February 7, 12:30-13:30
Where: Porter Hall 125B
Abstract:
A pair of square $0,1$ matrices $A,B$ such that $AB^T=E+kI$ (where $E$ is the $n \times n$ matrix of all 1s and $k$ is a positive integer) are called {\em Lehman matrices}. These matrices figure prominently in Lehman’s seminal theorem on minimally nonideal matrices. There are two choices of $k$ for which this matrix equation is known to have infinite families of solutions. When $n=k^2+k+1$ and $A=B$, we get point-line incidence matrices of finite projective planes, which have been widely studied in the literature. The other case occurs when $k=1$ and $n$ is arbitrary, but very little is known in this case. This talk discusses this class of Lehman matrices and classifies them according to their similarity to circulant matrices. The work is joint with Betrand Guenin and Levent Tuncel.
