[Lowerbounds, Upperbounds]

Date: 2008-05-14 12:00
Speaker: Yiannis Koutis
Title: Faster algebraic algorithms for path and packing problems
Place: NSH 1507

Abstract:

We study the problem of deciding whether an n-variate polynomial, presented as an arithmetic circuit G, contains a degree k square-free term with an odd coefficient. We show that if G can be evaluated over the integers modulo 2^(k+1) in time t and space s, the problem can be decided with constant probability in O((kn+t)2^k) time and O(kn+s) space. Based on this, we present new and faster algorithms for several parameterized problems, among which: (i) an O(2^(mk)) algorithm for the m-set k-packing problem and (ii) an O(2^(3k/2)) algorithm for the simple k-path problem, or an O(2^k) algorithm if the graph has an induced k-subgraph with an odd number of Hamiltonian paths.

Say you are preparing a camera-ready submission and you are running a little low on space, maybe by a few lines. At this point, hopefully you are willing to put in the time and try rewording some of your sentences. A usual way to start is to identify a paragraph with a very short final line and try rewording a sentence within so that the paragraph uses one less line.

But if you have tried this route, you may notice that TeX has “optimized away” your effort by subtly padding the pages with more vertical spaces, thereby keeping the page count constant…

Long story short, you want to use \raggedbottom. Put it in the preamble and recompile. With this, LaTeX will keep the breaks at the same places, but it will not pad and hence the bottom of the pages will be ragged (duh!). Now you can usually see why your effort did not produce the desired effect: the space that you just freed up does not allow the current page/column to absorb enough material from the next.

With the ability to find a short page/column by inspection, now you can identify the earliest place where rewording is more likely help. Repeat the reword-recompile cycle a couple times, and the page count will go down. Just be sure to take out \raggedbottom when you are done!

P.S. The two-page mode in your previewer can make the inspection more effective.

Date: 2008-05-07 12:00
Speaker: Karl Wimmer
Title: Polynomial regression under arbitrary product spaces
Place: NSH 1507

Abstract:

Recently, Kalai et. al gave a variant of the “Low-Degree Algorithm” for agnostic learning (learning with arbitrary classification noise) under the uniform distribution on {0,1}^n. One result of their work is an agnostic learning algorithm with respect to the class of linear threshold functions under certain restricted instance distributions, including the uniform distribution on {0,1}^n.

In this talk, we extend these ideas to product distributions on instance spaces X_1 x … X_n. We develop a variant of the “Low-Degree Algorithm” for these distributions, and we show that our algorithm agnostically learns with respect to the class of threshold functions under these distributions. We prove this by extending the “noise sensitivity method” to arbitrary product spaces, showing that threshold functions over arbitrary product spaces are no more noise sensitive than their Boolean counterparts.

In an Intel Software Network article titled Parallel computing: disappearing from CS curricula???, Michael Wrinn demonstrated that parallel computing has gradually disappeared from popular CS curricula in the past 10+ years. His first example is:

[…] a panelist at IPDPS (in Miami, a couple of weeks ago) assert that parallel-processing topics have been disappearing from CS curricula in recent years. As anecdotal evidence, he pointed out the topic’s removal in the 2nd edition of Introduction to Algorithms […]

The article goes on to give several other examples to prove his point. In the end, Michael wrote

[…] multicore computing platforms are now the norm. Recognizing that reality, let’s make the adjustment time short.

Are we expecting a surge of algorithm and data structure textbooks with an emphasis in multicore?

Title:Packing in Multipartite Graphs
Speaker: Ryan Martin, Iowa State
When: May 2, 11:30-12:30
Where: Hamburg Hall, Room 237

Abstract:

We present some results on packing graphs in dense multipartite graphs. This is a question very similar to the Hajnal-Szemeredi theorem, which gives sufficient minimum-degree conditions for an $n$-vertex graph to have a subgraph consisting of $\lfloor n/r\rfloor$ vertex-disjoint copies of $K_r$. This is a packing, or tiling, of the graph by copies of $K_r$. The Hajnal-Szemeredi theorem has been generalized to finding minimum-degree conditions that guarantee packings of non-complete graphs, notably by Alon and Yuster and by Kuhn and Osthus. We consider a multipartite version of this problem. That is, given an $r$-partite graph with $N$ vertices in each partition, what is the minimum-degree required of the bipartite graph induced by each pair of color-classes so that the graph contains $N$ vertex-disjoint copies of $K_r$? The question has been answered for $r=3,4$, provided $r$ is sufficiently large. When $r=3$ and $N$ is sufficiently large, a degree condition of $(2/3)N$ is sufficient with the exception of a single tripartite graph when $N$ is an odd multiple of $3$. When $r=4$ and $N$ is sufficiently large, a degree condition of $(3/4)N$ is sufficient and there is no exceptional graph. There are also bounds on the degree condition for higher $r$ by Csaba and Mydlarz. This question has also been generalized to finding minimum-degree conditions for packings of some arbitrary $r$-colorable graph in an $r$-partite. The case $r=2$ is highly nontrivial for packing arbitrary bipartite graphs and was answered very precisely by Zhao. The case $r=3$ is even more complex and we provide some tight bounds on the required degree condition. This talk includes joint work with Cs. Magyar, with E. Szemeredi and with Y. Zhao.