Title: Graphs containing triangles are not 3-common
Speaker: Michael Young
When: November 1, 16:30-17:30
Where: Wean Hall 5302
Abstract:
Jagger, Stovicek and Thomason defined the class of k-common graphs, and showed among other results that every graph containing K_4 as a subgraph is not 2-common. We prove that every graph containing K_3 as a subgraph is not 3-common.
When: 2007-10-31 noon
Where: NSH 1507
Who: Anupam Datta
Title: Games and the Impossibility of Realizable Ideal Functionality
Abstract:
A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the set of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.
Joint work with A. Derek, J. C. Mitchell, A. Ramanathan, A. Scedrov
The Power of VCG: On Algorithms that are Maximal In Range
Shahar Dobzinski, Hebrew University
Tuesday October 30, 2007, 3:30PM, Wean 7220
Abstract:
Consider the following simple type of approximation algorithms: limit the set of possible outcomes, and completely optimize over the restricted subrange. In this talk we will study the power of this type of algorithms in two settings: multi-unit auctions, and combinatorial auctions with subadditive bidders.
From a game-theoretic point of view, our results provide a characterization of the power of the main positive result of mechanism design the VCG mechanism. Another motivation is that our lower bounds might play a crucial role towards setting lower bounds on the power of polynomial time truthful mechanisms.
Joint work with Noam Nisan.
Optimization and Approximation under Partial Information
Sudipto Guha, UPenn
October 26, 2007, 3:30PM, Wean 7220
Abstract:
If you had to bet on a race — and you have ten minutes before the race begins, which contestants would you chat to for information? Would you decide on the sequence of contestants you would talk to upfront or choose adaptively? Coincidentally, this same problem and its variants appear in several applications such as databases, planning, and sensor networks, where parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system, as captured by some objective function over the parameters, is significantly improved if some of these parameters can be probed or observed. In a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. This problem and its variants are the focus of this talk where we will consider them through the lens of approximation algorithms.
Title: The Directed Orienteering Problem
Speaker: Viswanath Nagarajan
When: October 25, 16:30-17:30
Where: Wean Hall 5302
Abstract:
We consider the orienteering problem on asymmetric metrics: given a directed metric (V,d), a starting vertex s, an ending vertex t, and a length bound D, find an s-t path having length at most D that maximizes the number of vertices covered. We give an approximation algorithm for this problem achieving a guarantee of O(log^2 n). The previously best known result was an O(log n)-approximation algorithm that runs in quasi-polynomial time (Chekuri & Pal ‘05). For the undirected special case of this problem, a 3-approximation algorithm was known (Bansal et al. ‘04). Our result answers positively the question of poly-logarithmic approximability of the directed orienteering problem (Blum et al. ‘03). This is joint work with R. Ravi.
Who: Maverick Woo
Where: NSH 1507
When: Noon, 2007-10-24
Title: Having Fun with Inverse Ackermann Functions
Abstract:
In this talk we will familiarize ourselves with the inverse Ackermann functions through examples other than the classic Union-Find data structure. We will focus on intuition and also attempt to pick up interesting nuggets from the vast literature using/concerning these functions. No tedious computation will ensue.
My key case got stolen from the gym a while ago. The theft caused me about several nights of sleep and several hundred dollars… cash, CMU ID, driver’s license (showing my address), keys (the subsequent lock replacement), and the key case itself!
And the thief also got my Sandisk SD Plus card. That’s the only thing that makes me “feel good” about the whole incident: the card has been encrypted using TrueCrypt, which is a free open-source disk encryption software for Windows and Linux. I can only hope that TrueCrypt doesn’t have any security flaw in its implementation and that whoever gets my card does not want my data badly enough to crack AES and Twofish. Oh well…
The situation could have been very different had I not used TrueCrypt… So, have you encrypted your flash drive yet?
P.S. I highly recommend the SD Plus cards. These are SD cards with a built-in USB interface and so they are as universal as USB thumb drives. Their speed is reasonable, even though it is not very good. There are faster devices for the same money (like the Ultra series from Buffalo), but not in this stamp-sized form factor. I store my card together with coins!
Given the amount of documents that I deal with, I’ve had many opportunities to save paper if only I could annotating on a PDF directly. Until recently, Jarnal has been the only free solution on Windows. However, I would say that Jarnal is not exactly the most polished piece of software I have used… (But I am not complaining against its price.)
Well, Jarnal has some serious competition now. PDF-XChange Viewer is a free (as in beer) PDF viewer that supports a full suite of native PDF annotation capabilities. By “native”, I mean if you insert a “sticky note” comment into the PDF, it shows up as a sticky note in Adobe Reader and so you can open, close and move the note, just like the stickies created by Acrobat Professional. In comparison, the interface is not very customizable and the keyboard shortcuts are not quite “there” yet, but it is certainly looking very good for a version-1 product. The font rendering is not as good as well, but it is comparable to other free solutions. Its performance on graphics intensive PDF is very good on too! There is even a button that allows you to quickly open the current PDF using Adobe Reader, just in case.
I wish it has better ink support, but again, I am not complaining against its price. 
P.S. Not that I really want to destroy any sales, but I note that PDFCreator is a very good Distiller replacement. Together with PDF-XChange Viewer, they cover most of my PDF needs.
Name: Willem-Jan van Hoeve
University: Carnegie Mellon University
Date: November 2, 2007
Time: 1:30 to 3:00 pm
Location: 388 Posner Hall
Title: Algorithms in Constraint Programming: the Sequence Constraint
Abstract:
Constraint Programming is a powerful and flexible paradigm to model and solve combinatorial problems. In contrast to traditional optimization techniques that reason on the problem as a whole, constraint programming reasons on tractable substructures of the problem individually. More specifically, the search space is reduced by filtering out inconsistent domain values from the variable domains. The challenge is to find efficient filtering algorithms for combinatorial structures that occur frequently in applications. In this talk we consider a combinatorial structure known as the “sequence constraint”, that appears in many applications, such as car manufacturing and nurse rostering. After its introduction in 1988 several filtering algorithms have been proposed for it, none of which removed all possible inconsistent domain values, however. We present three filtering algorithms, including the first algorithm that achieves complete filtering in polynomial time for this constraint. We also provide experimental results, showing the effectiveness of our filtering algorithms in practice. This is joint work with Gilles Pesant, Louis-Martin Rousseau and Ashish Sabharwal. It was awarded as best paper at the annual conference on constraint programming CP 2006 (out of 142 submissions).
(Updated on 2007-10-31 with simpler steps. This post assumes you are running Windows, but it’s actually applicable to Unix users if you replace the MiKTeX terms with their TeX Live counterparts. )
The most recent release of MiKTeX is 2.6 and it ships with pdfLaTeX 1.4. Unfortunately, it is incompatible with Ipe’s latest release 6.0pre28 because this version of Ipe cannot cope with the PDF generated by pdfLaTeX 1.4. As the next version of Ipe is not coming very soon (Otfried says “Certainly not before spring 2008.”), one solution would be to downgrade to MiKTeX 2.5 so that Ipe can use the pdfLaTeX 1.3 that ships with MiKTeX 2.5. But if you have upgraded to pdfLaTeX 1.4 with a reason (like having fun with microtype), then you can also keep the two installations side-by-side with some storage overhead (~100MB). Assuming that your MiKTeX 2.6 is installed in C:\texmf-2.6, here is how you might do the MiKTeX 2.5 installation:
basic-miktex-2.5.2580.exe. It’s the self-contained “basic installer” for MiKTeX 2.5 and contains some basic packages. This file does not seem to be available at the official MiKTeX download page any more, but Google can help you find a copy, or you can get a local copy hosted on this server.C:\texmf-2.5.C:\texmf-2.5 from the PATH environment variable. That way, whenever you run latex, you are still running pdfLaTeX 1.4.IPEPDFLATEX to override IPE’s default pdflatex command, eg, IPEPDFLATEX=C:\texmf-2.5\miktex\bin\pdflatex.exe if that’s where you installed it to. At this moment, you may also be interested to set up something like IPELATEXDIR=C:\temp\iperun to control where Ipe generates the temp files.C:\texmf-2.6 to the bottom of the search list. Click OK and the filename database will be refreshed. (Unix users: this is the Kpathsea step. See here.)At this point, the side-by-side installation is complete. Have fun!
Title: On a random graph evolving by degrees
Speaker: Boris Pittel (Ohio State University)
When: October 19, 15:30-16:30
Where: Wean Hall 5302
Abstract:
We consider a random (multi)graph growth process ${G_m}$ on a vertex set $[n]$, which is a special case of a more general process suggested by Laci Lovasz several years ago. $G_0$ is empty, and $G_{m+1}$ is obtained from $G_m$ by inserting a new edge $e$ at random. Specifically, the conditional probability that $e$ joins two currently disjoint vertices, $i$ and $j$ , is proportional to $(d_i + \alpha)(d_j + \alpha)$, where $d_i$ , $d_j$ are the degrees of $i$ ,$ $j in $G_m$, and $\alpha > 0$ is a fixed parameter. The limiting case $\alpha = \infty$ is the Erdos-Renyi graph process. We show that whp $G_m$ contains a unique giant component iff $c := 2m/n > c_{\alpha} = \alpha/(1 + \alpha)$, and the size of this giant is asymptotic to $n [1-(\frac{\alpha+c^*}{\alpha+c})^{\alpha}]$, where $c^* < c_{\alpha}$ is the root of $\frac{c}{(\alpha+c)^{2+\alpha}} = \frac{c^*}{(\alpha+c^*)^{2+\alpha}}$ . For the multigraph version, ${MG_m}$, we show that $MG_m$ is connected whp iff $m \gg m_n := n^{1+\alpha^{-1}}$, and we conjecture that, for $\alpha > 1$, $m_n$ is the threshold for connectedness of $G_m$ itself.
Date: 2007-10-16 3:30pm
Room: Wean 5409
Speaker: Michael Kearns (UPenn)
Title: Behavioral Games on Networks
Abstract: We have been conducting behavioral experiments in which human subjects attempt to solve challenging graph-theoretic optimization problems through only local interactions and incentives. The primary goal is to shed light on the relationships between network structure and the behavioral and computational difficulty of different problem types.
To date, we have conducted experiments in which subjects are incentivized to solve problems of graph coloring, consensus, independent set, and an exchange economy game. I will report on thought-provoking findings at both the collective and individual behavioral levels, and contrast them with theories from theoretical computer science, sociology, and economics.
This talk discusses joint work with Stephen Judd, Sid Suri, and Nick Montfort.
October 19, 2007
Elaine Shi
3:00 PM, 5409 Wean Hall
Thesis Proposal
Title: Evaluating Predicates over Encrypted Data
Abstract:
In predicate encryption systems, given a capability (i.e., a partial decryption key) and a ciphertext, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden.
An important goal in predicate encryption is to construct efficient schemes that support expressive query predicates. Previously, researchers have constructed efficient schemes where the predicates are equality tests. In this proposal, we extend the previously known result and construct a new encryption scheme supporting conjunctive queries, where the query predicates are conjunctions of equality tests. A direct extension of this result is a scheme supporting multi-dimensional range queries.
We also propose to add delegation to predicate encryption systems. To demonstrate why delegation may be interesting, imagine that Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing him to decrypt a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation. The proposed work is to add delegation to a predicate encryption scheme supporting conjunctive queries.
Thesis Committee:
Adrian Perrig, Chair
Dawn Song
Manuel Blum
Brent Waters, Stanford Research Institute
Query Lower Bounds for Matroids via Group Representations
Nick Harvey, MIT
September 12, 2007, 3:30PM, Wean 7220
Abstract:
Finding an common independent set in two matroids is one of the classical problems of combinatorial optimization, including the well-known bipartite matching problem as a special case. In the early 1970s, algorithms for this problem were discovered that use O(n^3) queries for matroids on n elements. In 1976, Welsh asked the question of whether these algorithms are optimal. In the following thirty years, no non-trivial lower bounds were found.
In this talk, I will present some modest progress on this question. We show that (log_2 3)*n queries are necessary for certain matroids. The arguments are based on communication complexity and representation theory of the symmetric group.
When: Wednesday, October 17, 12:00 p.m.
Where: 1507 Newell-Simon Hall
Who: Michael Dinitz
Title: Compact Routing with Slack
Abstract:
Given a weighted graph G=(V,E), a compact routing scheme is a distributed algorithm for forwarding packets from any source to any destination. The fundamental tradeoff is between the space used at each node and the stretch of the total route, measured by the multiplicative factor between the actual distance traveled and the length of the shortest possible route. We extend the normal definition with a slack parameter epsilon, which allows us to ignore up to epsilon*n2 of the shortest pairwise routes and give stronger guarantees on the remaining ones. We give good epsilon-slack routing schemes in a variety of standard routing models, including the labeled model and the name-independent designer-port model. We also give a lower bound that proves that such schemes do not exist in the name-independent fixed-port model. In the labeled model we also give a gracefully degrading scheme which works simultaneously for all epsilon > 0 and guarantees constant average stretch with polylog space.
Name: Patrick Jalliet
University: MIT, School of Engineering
Date: Friday, October 19, 2007
Time: 1:30 pm to 3:00 pm
Location: Simon Auditorium
Title: Online Optimization for Routing Problems
Abstract:
We consider online routing optimization problems where the objective is to minimize the time needed to visit a set of locations under various constraints:; the problems are online because the set of locations are revealed incrementally over time. We consider two main problems: (2) the online Traveling Salesman Problem (TSP) with precedence and capacity constraints and (2) the online TSP with m salesmen. For both problems we propose online algorithms, each with a competitive ratio of 2; for the m-salesmen problem we show our result is best possible. We also consider polynomial-time online algorithms.
We then consider recourse augmentation, where we give the online servers additional resources to offset the powerful offline adversary advantage; in this way, we address a main criticism of competitive analysis. We consider the cases where the online algorithm has access to faster servers, servers with larger capacities, additional servers and/or advanced information. We derive improved competitive ratios. We also give lower bounds on the competitive ratios under resource augmentation, which in many cases are tight and lead to best-possible results.
Finally, we study online algorithms from an asymptotic point of view. We show that, under general stochastic structures for the problem stat, unknown and unused by the online player, the online algorithms are almost surely asymptotically optimal. Furthermore, we provide computational results that show that the convergence can be very fast.
Title: The Typical Structure of Graphs without Given Excluded Subgraphs
Speaker: Jozsi Balogh, University of Illinois at Urbana-Champaign
When: October 11, 16:30-17:30
Where: Wean Hall 5302
Abstract:
Let L be a finite family of graphs. We describe the typical structure of L-free graphs, improving our earlier results on the Erdos-Frankl-Rodl theorem, by proving our conjecture from our earlier paper. Let p=p(L)=min{F\in L:\chi(F)-1}. We shall prove that the structure of almost all L-free graphs are very similar to the Turan graph T_{n,p}, where “similarity'’ is measured in terms of graph theoretical parameters of L. Some more recent developements will be discussed as well. Joint work with B. Bollobas and M. Simonovits.
Who: Anupam Gupta
Where: NSH 1507
When: Noon, 2007-10-10
Stochastic Analysis of Online Steiner Tree
In the online Steiner tree problem, vertices come one-by-one and have to be connected to the root. The greedy algorithm is an O(log n) competitive algorithm, and this is the best possible. We will obtain better guarantees when the input sequence is not chosen by an adversary, but are just draws from some distribution over the vertices of the graph.
From an interesting idea in gnu.emacs.bug…
How many times have you found yourself mosying thru a file when you wonder, where the heck was I just editing? Well, the best you can do is hit undo, ^F, and undo again, to get back.
… comes a very handy function in Emacs—get this elisp file and bind a key to goto-last-change-with-auto-marks. (I bind it to F4, but of course it’s up to you.)
I note that my typical usage is a bit different from the post above: I usually remember what I was just editing, but I am reviewing a different part of the file. This feature allows me to jump back to my editing point quickly.
I must have used it so frequently that I just pressed F4 in another editor… and that’s how I realize I should share it here.
P.S. You may also be interested in this bit of advice for a slightly different experience:
(defadvice goto-last-change-with-auto-marks (before mav-goto-last-change activate)
"Split the window beforehand to retain the current view"
(unless (eq last-command 'goto-last-change-with-auto-marks)
(split-window-vertically)))
Title: Infrastructure Leasing Problems
Speaker: Barbara Anthony
When: Friday, October 5, 10:30 AM
Where: Doherty 4303
Abstract:
Consider the following Steiner Tree leasing problem. Given a graph G = (V,E) with root r, and a sequence of terminal sets D_t subset of V for each day t in [T]. A feasible solution to the problem is a set of edges E_t for each t connecting D_t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we lease edges for say, {a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of
time. What is a good leasing strategy? We give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
This proposal includes joint work with Anupam Gupta.
Committee: Anupam Gupta (Chair), Tom Bohman, Alan Frieze, R. Ravi