Theory of Computing Blog Aggregator

Even after the Snowden revelations, there remained one big mystery about what the NSA was doing and how.  The NSA’s classified 2013 budget request mentioned, as a priority item, “groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.”  There was a requested increase, of several hundred million dollars, for “cryptanalytic IT services” and “cryptanalysis and exploitation services program C” (whatever that was).  And a classified presentation slide showed encrypted data being passed to a high-performance computing system called “TURMOIL,” and decrypts coming out.  But whatever was going on inside TURMOIL seemed to be secret even within NSA; someone at Snowden’s level wouldn’t have had access to the details.

So, what was (or is) inside the NSA’s cryptanalytic black box?  A quantum computer?  Maybe even one that they bought from D-Wave?  (Rimshot.)  A fast classical factoring algorithm?  A proof of P=NP?  Commentators on the Internet rushed to suggest each of these far-reaching possibilities.  Some of us tried to pour cold water on these speculations—pointing out that one could envision many scenarios that were a little more prosaic, a little more tied to the details of how public-key crypto is actually used in the real world.  Were we just naïve?

This week, a new bombshell 14-author paper (see also the website) advances an exceedingly plausible hypothesis about what may have been the NSA’s greatest cryptanalytic secret of recent years.  One of the authors is J. Alex Halderman of the University of Michigan, my best friend since junior high school, who I’ve blogged about before.  Because of that, I had some advance knowledge of this scoop, and found myself having to do what regular Shtetl-Optimized readers will know is the single hardest thing in the world for me: bite my tongue and not say anything.  Until now, that is.

Besides Alex, the other authors are David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelink, and Paul Zimmermann (two of these, Green and Heninger, have previously turned up on Shtetl-Optimized).

These authors study vulnerabilities in Diffie-Hellman key exchange, the “original” (but still widely-used) public-key cryptosystem, the one that predates even RSA.  Diffie-Hellman is the thing where Alice and Bob first agree on a huge prime number p and a number g, then Alice picks a secret a and sends Bob ga (mod p), and Bob picks a secret b and sends Alice gb (mod p), and then Alice and Bob can both compute (ga)b=(gb)a=gab (mod p), but an eavesdropper who’s listening in only knows p, g, ga (mod p), and gb (mod p), and one can plausibly conjecture that it’s hard from those things alone to get gab (mod p).  So then Alice and Bob share a secret unknown to the eavesdropper, which they didn’t before, and they can use that secret to start doing cryptography.

As far as anyone knows today, the best way to break Diffie-Hellman is simply by calculating discrete logarithms: that is, solving the problem of recovering a given only g and h=ga (mod p).  At least on a classical computer, the fastest known algorithm for discrete logarithms (over fields of prime order) is the number field sieve (NFS).  Under plausible conjectures about the distribution of “smooth” numbers, NFS uses time that grows like exp((1.923+o(1))(log p)1/3(log log p)2/3), where the exp and logs are base e (and yes, even the lower-order stuff like (log log p)2/3 makes a big difference in practice).  Of course, once you know the running time of the best-known algorithm, you can then try to choose a key size (that is, a value of log(p)) that’s out of reach for that algorithm on the computing hardware of today.

(Note that the recent breakthrough of Antoine Joux, solving discrete log in in quasipolynomial time in fields of small characteristic, also relied heavily on sieving ideas.  But there are no improvements from this yet for the “original” discrete log problem, over prime fields.)

But there’s one crucial further fact, which has been understood for at least a decade by theoretical cryptographers, but somehow was slow to filter out to the people who deploy practical cryptosystems.  The further fact is that in NFS, you can arrange things so that almost all the discrete-logging effort depends only on the prime number p, and not at all on the specific numbers g and h for which you’re trying to take the discrete log.  After this initial “precomputation” step, you then have a massive database that you can use to speed up the “descent” step: the step of solving of ga=h (mod p), for any (g,h) pair that you want.

It’s a little like the complexity class P/poly, where a single, hard-to-compute “advice string” unlocks exponentially many inputs once you have it.  (Or a bit more precisely, one could say that NFS reveals that exponentiation modulo a prime number is sort of a trapdoor one-way function, except that the trapdoor information is subexponential-size, and given the trapdoor, inverting the function is still subexponential-time, but a milder subexponential than before.)

The kicker is that, in practice, a large percentage of all clients and servers that use Diffie-Hellman key exchange use the same few prime numbers p.  This means that, if you wanted to decrypt a large fraction of all the traffic encrypted with Diffie-Hellman, you wouldn’t need to do NFS over and over: you could just do it for a few p’s and cache the results.  This fact can singlehandedly change the outlook for breaking Diffie-Hellman.

The story is different depending on the key size, log(p).  In the 1990s, the US government insisted on “export-grade” cryptography for products sold overseas (what a quaint concept!), which meant that the key size was restricted to 512 bits.  For 512-bit keys, Adrian et al. were able to implement NFS and use it to do the precomputation step in about 7 days on a cluster with a few thousand cores.  After this initial precomputation step (which produced 2.5GB of data), doing the descent, to find the discrete log for a specific (g,h) pair, took only about 90 seconds on a 24-core machine.

OK, but no one still uses 512-bit keys, do they?  The first part of Adrian et al.’s paper demonstrates that, because of implementation issues, even today you can force many servers to “downgrade” to the 512-bit, export-grade keys—and then, having done so, you can stall for time for 90 seconds as you figure out the session key, and then do a man-in-the-middle attack and take over and impersonate the server.  It’s an impressive example of the sort of game computer security researchers have been playing for a long time—but it’s really just a warmup to the main act.

As you’d expect, many servers today are configured more intelligently, and will only agree to 1024-bit keys.  But even there, Adrian et al. found that a large fraction of servers rely on just a single 1024-bit prime (!), and many of the ones that don’t rely on just a few other primes.  Adrian et al. estimate that, for a single 1024-bit prime, doing the NFS precomputation would take about 45 million years using a single core—or to put it more ominously, 1 year using 45 million cores.  If you built special-purpose hardware, that could go down by almost two orders of magnitude, putting the monetary cost at a few hundred million dollars, completely within the reach of a sufficiently determined nation-state.  Once the precomputation was done, and the terabytes of output stored in a data center somewhere, computing a particular discrete log would then take about 30 days using 1 core, or mere minutes using a supercomputer.  Once again, none of this is assuming any algorithmic advances beyond what’s publicly known.  (Of course, it’s possible that the NSA also has some algorithmic advances; even modest ones could obviate the need for special-purpose hardware.)

While writing this post, I did my own back-of-the-envelope, and got that using NFS, calculating a 1024-bit discrete log should be about 7.5 million times harder than calculating a 512-bit discrete log.  So, extrapolating from the 7 days it took Adrian et al. to do it for 512 bits, this suggests that it might’ve taken them about 143,840 years to calculate 1024-bit discrete logs with the few thousand cores they had, or 1 year if they had 143,840 times as many cores (since almost all this stuff is extremely parallelizable).  Adrian et al. mention optimizations that they expect would improve this by a factor of 3, giving us about 100 million core-years, very similar to Adrian et al.’s estimate of 45 million core-years (the lower-order terms in the running time of NFS might account for some of the remaining discrepancy).

Adrian et al. mount a detailed argument in their paper that all of the details about NSA’s “groundbreaking cryptanalytic capabilities” that we learned from the Snowden documents match what would be true if the NSA were doing something like the above.  The way Alex put it to me is that, sure, the NSA might not have been doing this, but if not, then he would like to understand why not—for it would’ve been completely feasible within the cryptanalytic budget they had, and the NSA would’ve known that, and it would’ve been a very good codebreaking value for the money.

Now that we know about this weakness of Diffie-Hellman key exchange, what can be done?

The most obvious solution—but a good one!—is just to use longer keys.  For decades, when applied cryptographers would announce some attack like this, theorists like me would say with exasperation: “dude, why don’t you fix all these problems in one stroke by just, like, increasing the key sizes by a factor of 10?  when it’s an exponential against a polynomial, we all know the exponential will win eventually, so why not just go out to where it does?”  The applied cryptographers explain to us, with equal exasperation in their voices, that there are all sorts of reasons why not, from efficiency to (maybe the biggest thing) backwards-compatibility.  You can’t unilaterally demand 2048-bit keys, if millions of your customers are using browsers that only understand 1024-bit keys.  On the other hand, given the new revelations, it looks like there really will be a big push to migrate to larger key sizes, as the theorists would’ve suggested from their ivory towers.

A second, equally-obvious solution is to stop relying so much on the same few prime numbers in Diffie-Hellman key exchange.  (Note that the reason RSA isn’t vulnerable to this particular attack is that it inherently requires a different composite number N for each public key.)  In practice, generating a new huge random prime number tends to be expensive—taking, say, a few minutes—which is why people so often rely on “standard” primes.  At the least, we could use libraries of millions of “safe” primes, from which a prime for a given session is chosen randomly.

A third solution is to migrate to elliptic-curve cryptography (ECC), which as far as anyone knows today, is much less vulnerable to descent attacks than the original Diffie-Hellman scheme.  Alas, there’s been a lot of understandable distrust of ECC after the DUAL_EC_DBRG scandal, in which it came out that the NSA backdoored some of NIST’s elliptic-curve-based pseudorandom generators by choosing particular elliptic curves that it knew how handle.  But maybe the right lesson to draw is mod-p groups and elliptic-curve groups both seem to be pretty good for cryptography, but the mod-p groups are less good if everyone is using the same few prime numbers p (and those primes are “within nation-state range”), and the elliptic-curve groups are less good if everyone is using the same few elliptic curves.  (A lot of these things do seem pretty predictable with hindsight, but how many did you predict?)

Many people will use this paper to ask political questions, like: hasn’t the NSA’s codebreaking mission once again usurped its mission to ensure the nation’s information security?  Doesn’t the 512-bit vulnerability that many Diffie-Hellman implementations still face, as a holdover from the 1990s export rules, illustrate why encryption should never be deliberately weakened for purposes of “national security”?  How can we get over the issue of backwards-compatibility, and get everyone using strong crypto?  People absolutely should be asking such questions.

But for readers of this blog, there’s one question that probably looms even larger than those of freedom versus security, openness versus secrecy, etc.: namely, the question of theory versus practice.  Which “side” should be said to have “won” this round?  Some will say: those useless theoretical cryptographers, they didn’t even know how their coveted Diffie-Hellman system could be broken in the real world!  The theoretical cryptographers might reply: of course we knew about the ability to do precomputation with NFS!  This wasn’t some NSA secret; it’s something we discussed openly for years.  And if someone told us how Diffie-Hellman was actually being used (with much of the world relying on the same few primes), we could’ve immediately spotted the potential for such an attack.  To which others might reply: then why didn’t you spot it?

Perhaps the right lesson to draw is how silly such debates really are.  In the end, piecing this story together took a team that was willing to do everything from learning some fairly difficult number theory to coding up simulations to poring over the Snowden documents for clues about the NSA’s budget.  Clear thought doesn’t respect the boundaries between disciplines, or between theory and practice.

(Thanks very much to Nadia Heninger for reading this post and correcting a few errors in it.  For more about this, see Bruce Schneier’s post or Matt Green’s post.)

by Scott at May 23, 2015 01:41 AM UTC

Let H be a graph. The Ramsey number R(H) is the smallest n such that whenever you color the edges of the complete graph with n vertices with two colors blue and red, you can either find a blue copy or a red copy of H.

Ramsey’s famous theorem asserts that if H is a complete graph on m vertices then R(H) is finite.   Ir follows that R(H) is finite for every graph H and understanding the dependence of R(H) on H is a very important question. Of course there are very basic extensions: to many colors, to different requirements for different colors, and to hypergraphs.

A graph is d-degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most d. Thus, trees are 1-degenerate (and 1-degenerate graphs are forests), and planar graphs are 5-degenerate. For graphs to be degenerate is equivalent to the condition that the number of edges is at most linear times the number of vertices uniformly for all subgraphs.

In 1973, Burr and Erdős  conjectured that that for every natural number d, there exists a constant c = c(d) such that every d-degenerate graph H on n vertices satisfies r(H)\le cn.  This is a very different behavior than that of complete graphs where the dependence on the number of vertices is exponential. In 1983 Chvátal, Rödl, Szemerédi, and Trotter proved the conjecture when the maximum degree is bounded. Over the years further restricted cases of the conjectures were proved some weaker estimates were demonstrated. These developments were instrumental in the developments of some very basic tools in extremal and probabilistic combinatorics. Lee’s paper Ramsey numbers of degenerate graphs proved the conjecture!

by Gil Kalai at May 22, 2015 09:45 AM UTC

Authors: Thore Husfeldt
Download: PDF
Abstract: This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.

at May 22, 2015 12:46 AM UTC

Authors: Amit Daniely
Download: PDF
Abstract: We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution $\mathcal{D}$ on $\mathbb{Q}^n\times \{\pm 1\}$. We define $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D})$ as the least error of a halfspace classifier for $\mathcal{D}$. A learner who can access $\mathcal{D}$ has to return a hypothesis whose error is small compared to $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D})$.

Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random $K$-$\mathrm{XOR}$ formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D}) \le \eta$ for arbitrarily small constant $\eta>0$, and that $\mathcal{D}$ is supported in $\{\pm 1\}^n\times \{\pm 1\}$. Namely, even under these favorable conditions its error must be $\ge \frac{1}{2}-\frac{1}{n^c}$ for every $c>0$. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where $K$ can be poly-logarithmic in $n$), we can take $\eta = 2^{-\log^{1-\nu}(n)}$ for arbitrarily small $\nu>0$. Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).

at May 22, 2015 12:40 AM UTC

Authors: Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, Sébastien Adam
Download: PDF
Abstract: Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method.

at May 22, 2015 12:46 AM UTC

Authors: Noga Alon, Elchanan Mossel, Robin Pemantle
Download: PDF
Abstract: We consider the problem of corruption detection on networks. We show that graph expansion is necessary for corruption detection and discuss algorithms and the computational hardness of the problem.

at May 22, 2015 12:40 AM UTC

Authors: Greg Bodwin, Virginia Vassilevska Williams
Download: PDF
Abstract: We obtain new upper bounds on the additive distortion for graph emulators and spanners on relatively few edges. We introduce a new subroutine called "strip creation," and we combine this subroutine with several other ideas to obtain the following results:

\item Every graph has a spanner on $O(n^{1+\epsilon})$ edges with $\tilde{O}(n^{1/2 - \epsilon/2})$ additive distortion, for arbitrary $\epsilon\in [0,1]$. \item Every graph has an emulator on $\tilde{O}(n^{1 + \epsilon})$ edges with $\tilde{O}(n^{1/3 - 2\epsilon/3})$ additive distortion whenever $\epsilon \in [0, \frac{1}{5}]$. \item Every graph has a spanner on $\tilde{O}(n^{1 + \epsilon})$ edges with $\tilde{O}(n^{2/3 - 5\epsilon/3})$ additive distortion whenever $\epsilon \in [0, \frac{1}{4}]$.

Our first spanner has the new best known asymptotic edge-error tradeoff for additive spanners whenever $\epsilon \in [0, \frac{1}{7}]$. Our second spanner has the new best tradeoff whenever $\epsilon \in [\frac{1}{7}, \frac{3}{17}]$. Our emulator has the new best asymptotic edge-error tradeoff whenever $\epsilon \in [0, \frac{1}{5}]$.

at May 22, 2015 12:40 AM UTC

Authors: Wenkai Zhang, Jing Li
Download: PDF
Abstract: CFSFDP (clustering by fast search and find of density peaks) is recently developed density-based clustering algorithm. Compared to DBSCAN, it needs less parameters and is computationally cheap for its non-iteration. Alex. at al have demonstrated its power by many applications. However, CFSFDP performs not well when there are more than one density peak for one cluster, what we name as "no density peaks". In this paper, inspired by the idea of a hierarchical clustering algorithm CHAMELEON, we propose an extension of CFSFDP,E_CFSFDP, to adapt more applications. In particular, we take use of original CFSFDP to generating initial clusters first, then merge the sub clusters in the second phase. We have conducted the algorithm to several data sets, of which, there are "no density peaks". Experiment results show that our approach outperforms the original one due to it breaks through the strict claim of data sets.

at May 22, 2015 12:46 AM UTC

Authors: Greg Bodwin, Virginia Vassilevska Williams
Download: PDF
Abstract: We make improvements to the current upper bounds on pairwise distance preservers and additive spanners.

A {\em distance preserver} is a sparse subgraph that exactly preserves all distances in a given pair set $P$. We show that every undirected unweighted graph has a distance preserver on $O(\max\{n|P|^{1/3}, n^{2/3}|P|^{2/3}\})$ edges, and we conjecture that $O(n^{2/3}|P|^{2/3} + n)$ is possible.

An {\em additive subset spanner} is a sparse subgraph that preserves all distances in $S \times S$ for a node subset $S$ up to a small additive error function. Our second contribution is a new application of distance preservers to graph clustering algorithms, and an application of this clustering algorithm to produce new subset spanners. Ours are the first subset spanners that benefit from a non-constant error allowance. For constant $d$, we show that subset spanners with $+n^{d + o(1)}$ error can be obtained at any of the following sparsity levels:

[table omitted]

An {\em additive spanner} is a subset spanner on $V \times V$. The existence of error sensitive subset spanners was an open problem that formed a bottleneck in additive spanner constructions. By resolving this problem, we are able to prove that for any constant $d$, there are additive spanners with $+n^{d + o(1)}$ error at any of the following sparsity levels:

[table omitted]

If our distance preserver conjecture is true, then the fourth additive spanner is the best known for the entire range $d \in (0, 3/7]$. Otherwise, the first is the best known for $d \in [1/3, 3/7]$, the second is the best known for $d \in [3/13, 1/3]$, and and the third is the best known for $d \in (0, 3/13]$.

As an auxiliary result, we prove that all graphs have $+6$ pairwise spanners on $\Oish(n|P|^{1/4})$ edges.

at May 22, 2015 12:46 AM UTC

Authors: Yong-Jin Liu, Chun-Xu Xu, Dian Fan, Ying He
Download: PDF
Abstract: Intrinsic Delaunay triangulation (IDT) is a fundamental data structure in computational geometry and computer graphics. However, except for some theoretical results, such as existence and uniqueness, little progress has been made towards computing IDT on simplicial surfaces. To date the only way for constructing IDTs is the edge-flipping algorithm, which iteratively flips the non-Delaunay edge to be locally Delaunay. Although the algorithm is conceptually simple and guarantees to stop in finite steps, it has no known time complexity. Moreover, the edge-flipping algorithm may produce non-regular triangulations, which contain self-loops and/or faces with only two edges. In this paper, we propose a new method for constructing IDT on manifold triangle meshes. Based on the duality of geodesic Voronoi diagrams, our method can guarantee the resultant IDTs are regular. Our method has a theoretical worst-case time complexity $O(n^2\log n)$ for a mesh with $n$ vertices. We observe that most real-world models are far from their Delaunay triangulations, thus, the edge-flipping algorithm takes many iterations to fix the non-Delaunay edges. In contrast, our method is non-iterative and insensitive to the number of non-Delaunay edges. Empirically, it runs in linear time $O(n)$ on real-world models.

at May 22, 2015 12:57 AM UTC

I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and four more I couldn't make because of health issues (I'm fine now). People DID sub for me those two and DID do what I would have done. I covered some crypto which I had not done in the past.

Because of all of this I ended up not covering the proof that the primes were infinite until the last week.

INTENTIONAL EXPERIMENT: Rather than phrase it as a proof by contradiction I phrased it, as I think Euclid did, as

Given primes p1,p2,...,pn you can find a prime NOT on the list. (From this it easily follows that the primes are infinite.)

Proof: the usual one, look at p1xp2x...xpn + 1 and either its prime or it has a prime factor not on the list.

The nice thing about doing it this way is that there are EASY examples where p1xp2x...xpn+1 is NOT prime

(e.g., the list is {2,5,11} yields 2x5x11 + 1 = 111 = 3 x 37, so 3 and 37 are both not in {2,5,11})

where as if you always use the the product of the first n primes then add 1, you don't get to a non-prime until 2x3x5x7x11x13 + 1 = 30031 = 59x 509.

They understood the proof better than prior classes had, even prior honors classes.

UNINTENTIONAL: Since I did the proof at the end of the semester they ALREADY had some proof maturity, more so than had I done it (as I usually do) about 1/3 of the way through the course.

They understood the proof better than prior classes had, even prior honors classes. Hence I should proof all of the theorems the last week! :-)

But seriously, they did understand it better, but I don't know which of the two factors, or what combination caused it. Oh well.

by GASARCH ( at May 21, 2015 11:56 PM UTC

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all $\alpha\in[0,\underline{\alpha}_n]$, and under the restriction to balanced functions, also for all $\alpha\in[\frac{1}{2}-\overline{\alpha}_n,\frac{1}{2}]$, where $\underline{\alpha}_n,\overline{\alpha}_n\to 0$ as $n\to\infty$. In addition, we derive an upper bound on $I(f(X);Y)$ which holds for all balanced functions, and improves upon the best known bound for all $\frac{1}{3}<\alpha<\frac{1}{2}$.

at May 21, 2015 04:54 AM UTC

Authors: Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh
Download: PDF
Abstract: Computing Delaunay triangulations in $\mathbb{R}^d$ involves evaluating the so-called in\_sphere predicate that determines if a point $x$ lies inside, on or outside the sphere circumscribing $d+1$ points $p_0,\ldots ,p_d$. This predicate reduces to evaluating the sign of a multivariate polynomial of degree $d+2$ in the coordinates of the points $x, \, p_0,\, \ldots,\, p_d$. Despite much progress on exact geometric computing, the fact that the degree of the polynomial increases with $d$ makes the evaluation of the sign of such a polynomial problematic except in very low dimensions. In this paper, we propose a new approach that is based on the witness complex, a weak form of the Delaunay complex introduced by Carlsson and de Silva. The witness complex $\mathrm{Wit} (L,W)$ is defined from two sets $L$ and $W$ in some metric space $X$: a finite set of points $L$ on which the complex is built, and a set $W$ of witnesses that serves as an approximation of $X$. A fundamental result of de Silva states that $\mathrm{Wit}(L,W)=\mathrm{Del} (L)$ if $W=X=\mathbb{R}^d$. In this paper, we give conditions on $L$ that ensure that the witness complex and the Delaunay triangulation coincide when $W$ is a finite set, and we introduce a new perturbation scheme to compute a perturbed set $L'$ close to $L$ such that $\mathrm{Del} (L')= \mathrm{wit} (L', W)$. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lov\'asz local lemma. The only numerical operations we use are (squared) distance comparisons (i.e., predicates of degree 2). The time-complexity of the algorithm is sublinear in $|W|$. Interestingly, although the algorithm does not compute any measure of simplex quality, a lower bound on the thickness of the output simplices can be guaranteed.

at May 21, 2015 12:40 AM UTC

The Game Theory course that I am teaching is accompanied by weekly exercises which include a so-called G-exercise. G-exercises are games that the students play with or against each other. The (expected) payoff they receive will be accumulated and counts towards their final course grade. Starting with the Prisoner’s Dilemma, these exercises include classics like “Guess 2/3 of the Average“, Centipede, the El Farol Bar game, and an All-Pay Auction.

Last week the students were randomly matched into pairs and were asked to play a variant of the Battle of the Sexes (we slightly changed the payoffs and made the game symmetric).

Screen Shot 2015-05-20 at 23.22.04

The students are assigned a private chat channel with their partner and have a couple of days to discuss their strategies. By Saturday Midnight, each student has to privately submit his (possibly mixed) strategy using an online form. Players then directly receive their expected payoff.

Despite its simplicity, this G-exercise turned out to one of the most interesting ones because, over the years, students consistently reinvented solutions concepts such as Stackelberg strategies and correlated equilibrium. At the time the exercise is introduced, the students know about basic concepts such as Pareto optimality, dominated strategies, and maximin strategies. They barely know about Nash equilibrium.

Many students try to agree on one of the pure equilibria. Of course, this turns out to be difficult because of the unfair payoff distribution. Some students are successful in compensating each other (e.g., by offering beers in return for payoff 3). Others aim at evenly dividing the total payoff and agree on randomizing uniformly between A and B. This gives both players an expected payoff of 1, but obviously suffers from the fact that it’s not an equilibrium. So in some cases, players agree to play 50:50, and then one of them (or both!) eventually submit A. In the latter case, they both get no payoff. Some students succeed in computing the mixed equilibrium (3/4 A + 1/4 B), share it with their partner, and submit their strategies. This yields an expected payoff of 3/4 for both players. However, playing the maximin strategy (1/4 A + 3/4 B) guarantees exactly the same payoff no matter what the other player does. Many students seem to realize this and play the maximin strategy instead. A perhaps unexpected tactic by many players is to try to turn this into a sequential game by committing to strategy A:

Good morning,

I have already submitted strategy A (see the attached screenshot). I will be on a hiking trip over the weekend and won’t have Internet access. You can maximize your payoff by choosing B.

Have a nice weekend!

This Stackelbergian bully strategy works surprisingly well (although the screenshot cannot serve as a proof; players can revise their strategies as many times as they like until the deadline).

Finally, a handful of students reinvent the concept of correlated equilibrium. Frustrated by the fact that any real randomization will put positive probability on the undesirable (0,0) outcomes, they decide to randomize between the two pure equilibria. For example, they meet in the cafeteria and throw a coin that decides which pure equilibrium is played. This year, there was a public holiday shortly before the submission deadline, which prevented some students from meeting in person. They therefore designed elaborate mechanisms (correlation devices) to simulate the coin flip, e.g., by checking the timestamp of the first article appearing on a national news website on a given day or by adding their student ID numbers and observing whether the last digit of the sum is odd or even.

These are the little things that make teaching worthwhile.

PS: The final statistics were as follows:

Screen Shot 2015-05-20 at 23.24.35

by felixbrandt at May 20, 2015 09:52 PM UTC

On Wednesday, May 27th at 1 PM Eastern Time (10 AM Pacific Time, 7 PM Central European Time, 5 PM UTC), Aaron Potechin will talk about “Sum of Squares Lower Bounds for the Planted Clique Problem” (abstract below).

Please sign up on the online form if you wish to join the talk as a group.

For more information about the TCS+ online seminar series, please see the website.

The planted clique problem asks whether or not we can find a k-clique which is planted in a random G(n,\frac{1}{2}) graph. Although the expected size of the largest clique in a random graph is only 2\log n, we currently do not know of any polynomial time algorithm which can find a planted clique of size much smaller than n^{1/2}.

The sum of squares hierarchy gives a hierarchy of approximation algorithms, each more powerful than the last. These algorithms are some of the most powerful approximation algorithms we know of, but their performance on many problems is not well understood.

In this talk, I will present the first non-trivial bounds on the performance of the sum of squares hierarchy on the planted clique problem, describing the planted clique problem, the sum of squares hierarchy, and how we can show that the sum of squares hierarchy fails to find the planted clique if its size is sufficiently small.

by plustcs at May 20, 2015 01:46 PM UTC

In a recent paper Ron Graham surveys the work of Paul Erdős on Egyptian fractions. Did you know that Erdős' second paper was on the subject? I didn't. It proved that the sum of a harmonic progression can never form an Egyptian fraction representation of an integer (there is always at least one prime that appears in only one term). Graham himself is also a fan, having studied Egyptian fractions in his Ph.D. thesis.

Another of Erdős' papers surveyed by Graham is also somewhat related to the subject of my recent blog posts on sequences of highly composite numbers. This paper (famous for formulating the Erdős–Straus 4/n = 1/x + 1/y + 1/z conjecture) included another conjecture that every rational number x/y (between 0 and 1) has an Egyptian fraction representation with O(log log y) terms. However, the best bound known so far is larger, O(sqrt log y).

For any number z, let D(z) be the smallest number with the property that every positive integer less than z can be expressed as a sum of at most D(z) divisors of z (not necessarily distinct). Then a stronger version of Erdős' conjecture (for which the same bounds are known) is that, for every y, there exists a number z larger than y (but not too much larger) with D(z) = O(log log z). With such a z, you can split x/y into floor(xz/y)/z + remainder/yz and then use the sum-of-divisors property of z to split each of these two terms into a small number of unit fractions.

Computing D(z) for small values of z is not particularly hard, using a dynamic programming algorithm for the subset sum problem. So, based on the guess that the highly composite numbers would have small values of D(z), I tried looking for the biggest highly composite number with each value. In this way I found that D(24) = 3; D(180) = 4; D(5040) = 5; and D(1081080) = 6. That is, every positive integer less than 1081080 can be represented as a sum of at most six divisors of 1081080, and some require exactly six. Based on this, every x/y with y at most 1081080 can be represented as at most a 12-term Egyptian fraction.

Each number in the sequence 2, 6, 24, 180, 5040, 1081080, ... is within a small factor of the 1.6 power of the previous number; another way of saying the same thing is that the numbers in this sequence obey an approximate multiplicative Fibonacci recurrence in which each number is approximately the product of the previous two. The next number in the sequence might still be within reach of calculation, using a faster programming language than my Python implementation. If that 1.6-power pattern could be shown to continue forever, then Erdős' log-log conjecture would be true.

at May 20, 2015 07:37 AM UTC

Authors: Sang Won Bae, Chan-Su Shin, Antoine Vigneron
Download: PDF
Abstract: We establish tight bounds for beacon-based coverage problems, and improve the bounds for beacon-based routing problems in simple rectilinear polygons. Specifically, we show that $\lfloor \frac{n}{6} \rfloor$ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon $P$ with $n$ vertices. We also prove tight bounds for the case where $P$ is monotone, and we present an optimal linear-time algorithm that computes the beacon-based kernel of $P$. For the routing problem, we show that $\lfloor \frac{3n-4}{8} \rfloor - 1$ beacons are always sufficient, and $\lceil \frac{n}{4}\rceil-1$ beacons are sometimes necessary to route between all pairs of points in $P$.

at May 20, 2015 12:42 AM UTC

Authors: Cameron Farnsworth
Download: PDF
Abstract: We present new lower bounds for the symmetric border rank of the n x n determinant for all n. Further lower bounds are given for the 3 x 3 permanent.

at May 20, 2015 12:40 AM UTC

Authors: Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil
Download: PDF
Abstract: We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an implementation of the Omega Failure Detector under such assumption. We prove that the existence and sustainability of a leader is exponentially more probable in a multi-hop Omega implementation than in a single-hop one. An implementation is: message efficient if all but finitely many messages are sent by a single process; packet efficient if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t the number of processes, packets of different messages may potentially use different channels, thus the number of used channels is not limited; super packet efficient if the number of channels used by packets to transmit all but finitely many messages is linear. With deterministic assumption, we prove the following. If reliability and timeliness of one message does not correlate with another, i.e., there are no channel reliability properties, then a packet efficient implementation of Omega is impossible. If eventually timely and eventually reliable channels are allowed, we establish necessary and sufficient conditions for the existence of a message and packet efficient implementation of Omega. We also prove that the eventuality of timeliness of reliability of channels makes a super packet efficient implementation of Omega impossible. On the constructive side, we present and prove correct a deterministic packet efficient algorithm in a weaker model that allows eventually timely and fair-lossy channels.

at May 20, 2015 12:40 AM UTC

Authors: N. Bourgeois, R. Catellier, T. Denat, V. Th. Paschos
Download: PDF
Abstract: We study average-case complexity of branch-and-bound for maximum independent set in random graphs under the $\mathcal{G}(n,p)$ distribution. In this model every pair $(u,v)$ of vertices belongs to $E$ with probability $p$ independently on the existence of any other edge. We make a precise case analysis, providing phase transitions between subexponential and exponential complexities depending on the probability $p$ of the random model.

at May 20, 2015 12:40 AM UTC

Authors: Gil Kalai
Download: PDF
Abstract: Borsuk asked in 1933 if every set of diameter 1 in $R^d$ can be covered by $d+1$ sets of smaller diameter. In 1993, a negative solution, based on a theorem by Frankl and Wilson, was given by Kahn and Kalai. In this paper I will present questions related to Borsuk's problem.

at May 20, 2015 12:42 AM UTC

Authors: Antoine Limasset, Pierre Peterlongo
Download: PDF
Abstract: Mapping reads on references is a central task in numerous genomic studies. Since references are mainly extracted from assembly graphs, it is of high interest to map efficiently on such structures. In this work we formally define this problem and provide a first theoretical and practical study toward this direction when the graph is a de Bruijn Graph. We show that the problem is NP-Complete and we propose simple and efficient heuristics with a prototype implementation called BGREAT that handle real world instances of the problem with moderate resources. It achieves to map millions reads per CPU hour on a complex human de Bruijn graph. BGREAT availability:

at May 20, 2015 12:41 AM UTC

This is the time of the year when IMT Lucca announces a number of fully funded PhD scholarships. IMT Lucca is one of the institutions in Italy that is closest to my heart and where I have had the pleasure to spend some time in the past interacting with PhD students and faculty. It provides an excellent environment for PhD students in a truly splendid setting. I strongly recommend it, if you are considering a PhD in several areas of computer science and control theory. Watch the video below, which will whet your appetite, and then read on.

The Institute for Advanced Studies IMT Lucca - Italy invites applications for fully-funded PhD scholarships in Computer Science tenable from 1st November 2015.

IMT Lucca is a truly international research university within the Italian public higher education system that focuses on cutting-edge research in key areas such as Computer Sciences, Systems Engineering, Complex Networks, Economics and Cultural Heritage. The three-year doctoral program, which is taught entirely in English, is articulated in four discipline-specific curricula that share an interdisciplinary scientific background.

Computer Science doctoral studies at IMT are coordinated by Rocco De Nicola and promote research on the theory and applications of informatics such as concurrency, performance, programming languages, security, dependability, software engineering, and computational biology. The overarching goal is to develop languages, models, algorithms, verification techniques, engineering methodologies, and software tools for reasoning about distributed systems.

The doctoral students will be working within the SysMA research unit of IMT Lucca (; some of the research lines are pursued in collaboration with two institutes of the Italian Research Council (CNR) in Pisa, namely ISTI ( and IIT (

PhD students receive a stipend of about €13,600 EUR gross (around €12,400 EUR after taxes) per year, as established by Italian law. In addition, they are offered free meals and on-campus housing in the historical center of the beautiful Tuscan city of Lucca. Students also get the opportunity to spend research periods abroad, with the possibility of receiving additional financing through the Erasmus+ program.

The deadline for application is June 29th, 2015 at 18:00 Italian time.

The call is open to all candidates who are expected to obtain the required degree by October 31st, 2015; however, they must still apply by the above deadline. Further details, along with the online application form, can be found at:

by Luca Aceto ( at May 19, 2015 06:52 PM UTC

Continuing my thoughts on the STOC 2017 reboot, I went back to Boaz's original question:

What would make you more likely to go to STOC?

And thought I'd answer it by mentioning an event that I really enjoy attending. I didn't post it as a comment because it's a little out of scope for the blog post itself: it doesn't make concrete recommendations so much as relay anecdotal evidence. 

The Information Theory and Applications workshop is a workshop: it doesn't have printed proceedings, and it encourages people to present work that has been published (or is under review) elsewhere. Keep that caveat in mind: the structure here might not work for a peer-reviewed venue like STOC. 

Having said that, the ITA is a wonderful event to go to. 
  • It's in San Diego every year in February - what's not to like about that
  • It runs for 5 days, so is quite long. But the topics covered change over the course of the 5 days: the early days are heavy on information theory and signal processing, and the algorithms/ml/stats shows up later in the week. 
  • There are multiple parallel sessions: usually 5. And lots of talks (no posters)
  • There are lots of fun activities. There's an irreverent streak running through the entire event, starting with the countdown clock to the invitations, the comedy show where professional comedians come and make fun of us :), various other goofy events interspersed with the workshop, and tee-shirts and mugs with your name and picture on them. 
The talks are very relaxed, probably precisely because there isn't a sense of "I must prove my worth because my paper got accepted here". Talk quality varies as always, but the average quality is surprisingly high, possibly also because it's by invitation. 

But the attendance is very high. I think the last time I attended there were well over 600 people, drawn from stats, math, CS, and EE. This had the classic feel of a 'destination workshop' that STOC wants to emulate. People came to share their work and listen to others, and there was lots of space for downtime discussions. 

My assertion is that the decoupling of presentation from publication (i.e the classical workshop nature of ITA), makes for more fun talks, because people aren't trying to prove a theorem from the paper and feel the freedom to be more expansive in their talks (maybe covering related results, or giving some larger perspective). 

Obviously this would be hard to do at STOC. But I think the suggestions involving posters are one way of getting to this: namely, that you get a pat on the back for producing quality research via a CV bullet ("published at STOC") and an opportunity to share your work (the poster). But giving a talk is a privilege (you're occupying people's time for slice of a day), not a right, and that has to be earned. 

I also think that a commenter (John) makes a good point when they ask "Who's the audience?". I'm at a point where I don't really enjoy 20 minutes of a dry technical talk and I prefer talks with intuition and connections (partly because I can fill in details myself, and partly because I know I'll read the details later if I really care). I don't know if my view is shared by everyone, especially grad students who have the stamina and the inclination to sit through hours of very technical presentations. 

by Suresh Venkatasubramanian ( at May 19, 2015 05:59 PM UTC

In a Dear Colleagues letter from Jim Kurose, the CISE Directorate at NSF has announced its intention to change the deadlines for a number of its programs, including Algorithmic Foundations (AF) and Secure and Trustworthy Cyberspace (SaTC).  The next deadlines for these programs are expected to be in the following months:

  • Medium and Large proposals: September 2015
  • Small proposals: November 2015.

by salilvadhan at May 19, 2015 04:00 PM UTC

[The following announcement is from Guido Schaefer, who is the General Chair for WINE 2015.]

WINE 2015: The 11th Conference on Web and Internet Economics

Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands
December 9-12, 2015, with tutorial program on December 9, 2015

* Paper submission deadline: July 24, 2015, 11:59pm anywhere on Earth (UTC-12)
* Tutorial proposal submission deadline: July 31, 2015
* Author notification: September 18, 2015
* Camera-ready copy: October 2, 2015

Over the past decade, research in theoretical computer science, artificial intelligence, and microeconomics has joined forces to tackle problems involving incentives and computation. These problems are of particular importance in application areas like the Web and the Internet that involve large and diverse populations. The Conference on Web and Internet Economics (WINE) is an interdisciplinary forum for the exchange of ideas and results on incentives and computation arising from these various fields. WINE 2015 builds on the success of the Conference on Web and Internet Economics (named Workshop on Internet & Network Economics until 2013), which was held annually from 2005 to 2014.

WINE 2015 will take place at CWI in December 2015. The program will feature invited talks, tutorials, paper presentations, and a poster session. All paper submissions will be peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance. Industrial applications and position papers presenting novel ideas, issues, challenges and directions are also welcome. Submissions are invited in, but not limited to, the following topics:

* Algorithmic game theory
* Algorithmic mechanism design
* Auction algorithms and analysis
* Computational advertising
* Computational aspects of equilibria
* Computational social choice
* Convergence and learning in games
* Coalitions, coordination and collective action
* Economic aspects of security and privacy
* Economic aspects of distributed computing
* Network games
* Price differentiation and price dynamics
* Social networks

Authors are invited to submit extended abstracts presenting original research on any of the research fields related to WINE 2015.

An extended abstract submitted to WINE 2015 should start with the title of the paper, each author’s name, affiliation and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work.

The extended abstract should not exceed 14 single-spaced pages using reasonable margins and at least 11-point font (excluding references). If the authors believe that more details are essential to substantiate the claims of the paper, they may include a clearly marked appendix (with no space limit) that will be read at the discretion of the Program Committee. It is strongly recommended that submissions adhere to the specified format and length. Submissions that are clearly too long may be rejected immediately.

The proceedings of the conference will be published by Springer-Verlag in the ARCoSS/LNCS series, and will be available for distribution at the conference. Accepted papers will be allocated 14 pages total in the LNCS format in the proceedings. Submissions are strongly encouraged, though not required, to follow the LNCS format. More information about the LNCS format can be found on the author instructions page of Springer-Verlag, see

To accommodate the publishing traditions of different fields, authors of accepted papers can ask that only a one-page abstract of the paper appear in the proceedings, along with a URL pointing to the full paper. Authors should guarantee the link to be reliable for at least two years. This option is available to accommodate subsequent publication in journals that would not consider results that have been published in preliminary form in a conference proceedings. Such papers must be submitted and formatted just like papers submitted for full-text publication.

Simultaneous submission of results to another conference with published proceedings is not allowed. Results previously published or presented at another archival conference prior to WINE 2015, or published (or accepted for publication) at a journal prior to the submission deadline of WINE 2015, will not be considered. Simultaneous submission of results to a journal is allowed only if the authors intend to publish the paper as a one-page abstract in WINE 2015. Papers that are accepted and appear as a one-page abstract can be subsequently submitted for publication in a journal but may not be submitted to any other conference that has a published proceedings.

WINE 2015 is soliciting proposals for tutorials to be held on December 9, 2015. Tutorial proposals should be no more than 2 pages long and contain the title of the tutorial, a description of the topic matter, the names of the tutor(s), and dates/venues where earlier versions of the tutorial were given (if any). In addition, short biographies of the tutor(s) should be attached to the proposal. Informal suggestions of tutorial ideas can also be sent without a full proposal to the program chairs at any time. Tutorial proposals should be submitted by email to

Papers must be submitted electronically through
Tutorial proposals should be sent to

by robertkleinberg at May 19, 2015 02:38 PM UTC

Over on Windows on Theory, there's a solid discussion going on about possible changes to the format for STOC 2017 to make it more of a 'theory festival'. As Michael Mitzenmacher exhorts, please do go and comment there: this is a great chance to influence the form of our major conferences, and you can't make a change (or complain about the lack of change) if you're not willing to chime in.

I posted my two comment there, and you should go and read number one  and number two. Two things that I wanted to pull out and post here are in the form of a 'meta-suggestion':
1. Promise to persist with the change for a few years. Any kind of change takes time to get used to, and every change feels weird and crazy till you get used to it, after which point it’s quite natural. 
Case in point: STOC experimented one year with a two-tier committee, but there was no commitment to stick to the change for a few years, and I’m not sure what we learned at all from one data point (insert joke about theorists not knowing how to run experiments). 
Another case in point: I’m really happy about the continued persistence with workshops/tutorials. It’s slowly becoming a standard part of STOC/FOCS, and that’s great. 
2. Make a concerted effort to collect data about the changes. Generate surveys, and get people to answer them (not as hard as one might think). Collect data over a few years, and then put it all together to see how the community feels. In any discussion (including this one right here), there are always a few people with strong opinions who speak up, and the vast silent majority doesn’t really chip in. But surveys will reach a larger crowd, especially people who might be uncomfortable engaging in public.

by Suresh Venkatasubramanian ( at May 19, 2015 05:25 AM UTC

NSF CAREER Program Webinar

May 26, 2015 1:00 PM  to 3:00 PM (Eastern Daylight Time, New York, GMT-04:00)

The NSF CAREER Coordinating Committee is hosting a webinar to provide an overview of the NSF Faculty Early Career Development Program (CAREER) and to answer participants’ questions about development and submission of CAREER proposals.

The webinar includes an overview presentation followed by a question-and-answer period.  For more details, see

by salilvadhan at May 19, 2015 01:38 AM UTC

In the fall we list theory jobs, in the spring we see who got them. Like last year, I created a fully editable Google Spreadsheet to crowd source who is going where. Ground rules:
  • I set up separate sheets for faculty, industry and postdoc/visitors.
  • People should be connected to theoretical computer science, broadly defined.
  • Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
  • You are welcome to add yourself, or people your department has hired.
This document will continue to grow as more jobs settle. So check it often.


by Lance Fortnow ( at May 19, 2015 12:24 AM UTC

Authors: Takayuki Iguchi, Dustin G. Mixon, Jesse Peterson, Soledad Villar
Download: PDF
Abstract: Recently, Awasthi et al. introduced an SDP relaxation of the $k$-means problem in $\mathbb R^m$. In this work, we consider a random model for the data points in which $k$ balls of unit radius are deterministically distributed throughout $\mathbb R^m$, and then in each ball, $n$ points are drawn according to a common rotationally invariant probability distribution. For any fixed ball configuration and probability distribution, we prove that the SDP relaxation of the $k$-means problem exactly recovers these planted clusters with probability $1-e^{-\Omega(n)}$ provided the distance between any two of the ball centers is $>2+\epsilon$, where $\epsilon$ is an explicit function of the configuration of the ball centers, and can be arbitrarily small when $m$ is large.

at May 19, 2015 12:43 AM UTC

Authors: Somaye Davari, Nasser Ghadiri
Download: PDF
Abstract: Analyzing huge amounts of spatial data plays an important role in many emerging analysis and decision-making domains such as healthcare, urban planning, agriculture and so on. For extracting meaningful knowledge from geographical data, the relationships between spatial data objects need to be analyzed. An important class of such relationships are topological relations like the connectedness or overlap between regions. While real-world geographical regions such as lakes or forests do not have exact boundaries and are fuzzy, most of the existing analysis methods neglect this inherent feature of topological relations. In this paper, we propose a method for handling the topological relations in spatial databases based on fuzzy region connection calculus (RCC). The proposed method is implemented in PostGIS spatial database and evaluated in analyzing the relationship of diseases as an important application domain. We also used our fuzzy RCC implementation for fuzzification of the skyline operator in spatial databases. The results of the evaluation show that our method provides a more realistic view of spatial relationships and gives more flexibility to the data analyst to extract meaningful and accurate results in comparison with the existing methods.

at May 19, 2015 12:45 AM UTC

Authors: Jian-Jia Chen
Download: PDF
Abstract: Partitioned multiprocessor scheduling has been widely accepted in academia and industry to statically assign and partition real-time tasks onto identical multiprocessor systems. This paper studies fixed-priority partitioned multiprocessor scheduling for sporadic real-time systems, in which deadline-monotonic scheduling is applied on each processor. Prior to this paper, the best known results are by Fisher, Baruah, and Baker with speedup factors $4-\frac{2}{M}$ and $3-\frac{1}{M}$ for arbitrary-deadline and constrained-deadline sporadic real-time task systems, respectively, where $M$ is the number of processors. We show that a greedy mapping strategy has a speedup factor $3-\frac{1}{M}$ when considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time schedulability tests and pseudo-polynomial-time (exact) schedulability tests. Moreover, we also improve the speedup factor to $2.84306$ when considering constrained-deadline task systems. We also provide tight examples when the fitting strategy in the mapping stage is arbitrary and $M$ is sufficiently large. For both constrained- and arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain theoretical benefits (with respect to speedup factors) for an arbitrary fitting strategy.

at May 19, 2015 12:44 AM UTC

Authors: William S. Evans, Giuseppe Liotta, Fabrizio Montecchiani
Download: PDF
Abstract: Let $\langle G_r,G_b \rangle$ be a pair of plane $st$-graphs with the same vertex set $V$. A simultaneous visibility representation with L-shapes of $\langle G_r,G_b \rangle$ is a pair of bar visibility representations $\langle\Gamma_r,\Gamma_b\rangle$ such that, for every vertex $v \in V$, $\Gamma_r(v)$ and $\Gamma_b(v)$ are a horizontal and a vertical segment, which share an end-point. In other words, every vertex is drawn as an $L$-shape, every edge of $G_r$ is a vertical visibility segment, and every edge of $G_b$ is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane $st$-graphs admitting such a representation, (ii) a cubic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive.

at May 19, 2015 12:44 AM UTC

Authors: Sarah R. Allen, Ryan O'Donnell, David Witmer
Download: PDF
Abstract: Let $P$ be a $k$-ary predicate over a finite alphabet. Consider a random CSP$(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m \gg n$ the instance $I$ will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When $P$ is the $3$-ary OR predicate, this is the well studied problem of refuting random $3$-SAT formulas, and an efficient algorithm is known only when $m \gg n^{3/2}$. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a $k$-ary predicate, having $m \gg n^{\lceil k/2 \rceil}$ constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if $P$ fails to support a $t$-wise uniform distribution, then there is an efficient algorithm that refutes random CSP$(P)$ instances $I$ whp when $m \gg n^{t/2}$. Indeed, our algorithm will "somewhat strongly" refute $I$, certifying $\mathrm{Opt}(I) \leq 1-\Omega_k(1)$, if $t = k$ then we get the strongest possible refutation, certifying $\mathrm{Opt}(I) \leq \mathrm{E}[P] + o(1)$. This last result is new even in the context of random $k$-SAT. Regarding the optimality of our $m \gg n^{t/2}$ requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP$(P)$ may be impossible when $m \ll n^{t/2}$. Thus there is an indication our algorithm's dependence on $m$ is optimal for every $P$, at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.

at May 19, 2015 12:00 AM UTC

Authors: Christian Glacet, Avery Miller, Andrzej Pelc
Download: PDF
Abstract: The leader election task calls for all nodes of a network to agree on a single node. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node $v$ of the network must output a simple path, coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees.

Our aim is to establish tradeoffs between the allocated time $\tau$ and the amount of information that has to be given $\textit{a priori}$ to the nodes to enable leader election in time $\tau$ in all trees for which leader election in this time is at all possible. Following the framework of $\textit{algorithms with advice}$, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the $\textit{size of advice}$. For an allocated time $\tau$, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $\tau$.

We consider $n$-node trees of diameter $diam \leq D$. While leader election in time $diam$ can be performed without any advice, for time $diam-1$ we give tight upper and lower bounds of $\Theta (\log D)$. For time $diam-2$ we give tight upper and lower bounds of $\Theta (\log D)$ for even values of $diam$, and tight upper and lower bounds of $\Theta (\log n)$ for odd values of $diam$. For the time interval $[\beta \cdot diam, diam-3]$ for constant $\beta >1/2$, we prove an upper bound of $O(\frac{n\log n}{D})$ and a lower bound of $\Omega(\frac{n}{D})$, the latter being valid whenever $diam$ is odd or when the time is at most $diam-4$. Finally, for time $\alpha \cdot diam$ for any constant $\alpha <1/2$ (except for the case of very small diameters), we give tight upper and lower bounds of $\Theta (n)$.

at May 19, 2015 12:42 AM UTC

Authors: Stefan Langerman, Yushi Uno
Download: PDF
Abstract: We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.

at May 19, 2015 12:41 AM UTC

Authors: Setareh Borjian, Virgile Galle, Vahideh H. Manshadi, Cynthia Barnhart, Patrick Jaillet
Download: PDF
Abstract: The Container Relocation Problem (CRP) is concerned with finding a sequence of moves to retrieve containers in a given order with minimum number of relocations. While the problem is known to be NP-hard, there is much evidence that certain algorithms and heuristics perform reasonably well on many instances of the problem. In this paper, we first focus on the A* search algorithm, and analyze easy to compute lower and upper bounds that can be used to prune nodes and to determine the gap between the solution found and the optimum. Our analysis sheds light on which bounds result in fast computation within a given approximation gap. We also present extensive simulation results that show our method finds the optimum solution on most instances of medium-size bays. On the "hard" instances, our method finds a near-optimal solution with a small gap and within a time frame that is fast for practical applications. We also study the average-case asymptotic behavior of the CRP where the number of columns grows. We show that the optimum number of relocations converges to a simple and intuitive lower-bound. This gives strong evidence that the CRP is "easier" in large instances, and heuristic approach can give near optimal solution.

We further study the CRP with incomplete information in a 2-stage setting where the retrieval order of a subset of containers is known initially and the retrieval order of the remaining containers is observed later at a given revelation time. Before this time, we assume a probabilistic distribution on the retrieval order of unknown containers. We extend the A* algorithm and combine it with sampling technique to solve this 2-stage stochastic optimization problem. We show that our algorithm is fast and the error due to sampling is reasonably small. Using our framework, we study the value of information and the effect of revelation time on the average number of relocations.

at May 19, 2015 12:42 AM UTC

Authors: Bert Besser, Matthias Poloczek
Download: PDF
Abstract: Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio 1/2 whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes.

This motivates an investigation of greedy algorithms on graphs with maximum degree D: We show that MinGreedy achieves a (D-1)/(2D-3)-approximation for graphs with D=3 and for D-regular graphs, and a guarantee of (D-1/2)/(2D-2) for graphs with maximum degree D. Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily.

Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a (D-1)/(2D-3)-inapproximability result for graphs with maximum degree D; thus, these greedy algorithms do not achieve a 1/2+eps-approximation and in particular the 2/3-approximation obtained by the deterministic MinGreedy for D=3 is optimal in this class. For k-uniform hypergraphs we show a tight 1/k-inapproximability bound. We also study fully randomized priority algorithms and give a 5/6-inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.

at May 19, 2015 12:44 AM UTC

Sufficiently many to start a soccer team.

Some constraint satisfaction problems are approximation resistant, in the sense that, unless P=NP, there is no polynomial time algorithm that achieves a better approximation ratio than the trivial algorithm that picks a random assignment. For example, a random assignment satisfies (on average) a {\frac 78} fraction of the clauses of a given Max 3SAT instance, and, for every {\epsilon >0}, it is NP-hard to achieve approximation {\frac 78 + \epsilon}. Max 3LIN is the variant of Max 3SAT in which every constraint is a XOR instead of an OR of variables; it is another example of an approximation resistant problem, because a random assignment satisfies (on average) half of the constraints, and approximation {\frac 12 + \epsilon} is NP-hard for every {\epsilon >0}. (These, and more, hardness of approximation results were proved by Håstad in 1997, in a paper with a notably understated title.)

In 2000, Håstad proved that if we restrict constraint satisfaction problems to instances in which every variable occurs in (at most) a fixed constant number of constraints, then the problem is never approximation resistant. If we have a constraint satisfaction problem in which each constraint is satisfied with probability {p} by a random assignment, and each variable appears in at most {D} constraint, then there is a simple polynomial time algorithm that achieves an approximation ratio {p + \Omega\left( \frac 1 D \right)}. The following year, I showed that if we have a constraint satisfaction problem that is NP-hard to approximate within a factor of {r}, then it is also NP-hard to approximate within a factor {r + \frac c{\sqrt D}}, where {c} is a constant (whose value depends on the specific constraint satisfaction problem), when restricted to instances in which every variable occurs at most {D} times.

Thus, for example, if we restrict to instances in which every variable occurs in at most {D} constraints, Max 3SAT can be approximated within a factor {\frac 78 + \frac{c_1}{D}} but not {\frac 78 + \frac{c_2}{\sqrt D}}, and Max 3LIN can be approximated within a factor {\frac 12 + \frac {c_3}{D}} but not {\frac 12 + \frac{c_4}{\sqrt D}} in polynomial time, unless {P=NP}, where {c_1,c_2,c_3,c_4} are constants.

Last Fall, Prasad Raghavendra and I worked for a while on the problem of bridging this gap. The difficulty with Max 3SAT is that there are instances derived from Max Cut such that every variable occurs in at most {D} clauses, there is no “trivial contradiction” (such as 8 clauses over the same 3 variables, which have a fixed contribution to the cost function and can be eliminated without loss of generality), and every assignment satisfies at most {\frac 78 + \frac {O(1)}{D}} clauses. If we want an approximation ratio {\frac 78 + \Omega(D^{-1/2})}, we need our algorithm to certify that such instances are unsatisfiable. It is probably possible to show that there are simple LP or SDP relaxations of Max 3SAT such that a polynomial time algorithm can find assignments that satisfies a number of clauses which is at least a {\frac 78 + \Omega(D^{-1/2})} times the optimum of the relaxation, but we could not find any way to reason about it, and we gave up. Also, we wrongly assumed that there was the same issue with Max 3LIN.

Meanwhile, Farhi, Goldstone and Gutmann, who had successfully developed a quantum algorithm to approximate Max Cut on bounded degree graphs, were looking for another problem to tackle, and asked Madhu Sudan what was known about NP-hard and Unique Games-hard problems on bounded degree instances. They were particularly interested in Max 3SAT in bounded-degree instances. Madhu referred them to me, Sam Gutmann happened to be in the Bay Area, and so we met in November and I pointed them to the known literature and suggested that they should try Max 3LIN instead.

A month later, I heard back from them, and they had a {\frac 12 + \Omega \left( \frac 1 {D^{3/4}} \right)} approximate algorithm for Max 3LIN. That sounded amazing, so I went looking into the paper for the section in which they discuss their upper bound technique, and there is none. They show that, for every instance that does not have trivial contradictions (meaning two constraints that are the negation of each other), there is an assignment that satisfies a {\frac 12 + \Omega ( D^{-3/4})} fraction of constraints, and they describe a distribution that, on average, satisfies at least as many. The distribution is samplable by a quantum computer, so the approximation, in their paper, is achieved by a quantum algorithm.

After realizing that we had been wrong all along on the need for non-trivial upper bounds for Max 3LIN, Prasad and I tried to find a way to replicate the result of Farhi et al. with a classical algorithm, and we found a way to satisfy a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints in instances of constraint satisfaction problems “without triangles” (a result of this form is also in the paper of Farhi et al.), and then a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints in all Max 3LIN instances.

The day before submitting our paper to ICALP (from which it would have been rejected without consideration anyways), I saw a comment by Boaz Barak on Scott Aronson’s blog announcing the same results, so we got in contact with Boaz, who welcomed us to the club of people who had, meanwhile, gotten those results, which also included Ankur Moitra, Ryan O’Donnell, Oded Regev, David Steurer, Aravindan Vijayaraghavan, David Witmer, and John Wright. Later, Johan Håstad also discovered the same results. If you kept count, that’s eleven theoreticians.

The paper is now online (with only 10 authors, Johan may write posted a separate note); we show that a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints can be satisfied in all Max kLIN instances, with odd {k}, and a {\Omega(D^{-1/2})} advantage over the random assignment can be achieved in all “triangle-free” instances of constraint satisfaction problems. It remains an open problem to improve Håstad’s {\frac 78 + O(D^{-1})} approximation for Max 3SAT.

The argument for Max 3LIN is very simple. Khot and Naor prove that, given a Max 3LIN instance {I}, one can construct a bipartite Max 3LIN instance {I'} such that an assignment satisfying a {\frac 12 + \epsilon} fraction of constraints in {I'} can be easily converted into an assignment satisfying a {\frac 12 + \Omega(\epsilon)} fraction of constraints of {I}; furthermore, if every variable occurs in at most {D} constraints of {I}, then every variable occurs in at most {2D} constraints of {I'}.

An instance is bipartite if we can partition the set of variables into two subsets {X} and {Y}, such that each constraint involves two variables from {X} and one variable from {Y}. The reduction creates two new variables {x_i} and {y_i} for each variable {z_i} of {I}; every constraint {z_i \oplus z_j \oplus z_k = b} of {I} is replaced by the three constraints

\displaystyle  x_i \oplus x_j \oplus y_k = b

\displaystyle  x_i \oplus y_j \oplus x_k = b

\displaystyle  y_i \oplus x_j \oplus x_k = b

Given an assignment to the {X} and {Y} variables that satisfies a {\frac 12 + \epsilon} fraction of the constraints of {I'}, Khot and Naor show that either {X}, or {Y}, or an assignment obtained by choosing {z_i} to be {x_i} with probability {1/2} or {y_i} with probability {1/2}, satisfies at least a {\frac 12 + \Omega(\epsilon)} fraction of constraints of {I}.

It remains to show that, given a bipartite instance of Max 3LIN in which every variable occurs in at most {D} constraints (and which does not contain two equations such that one is the negation of the other), we can find an assignment that satisfies a {\frac 12 + \Omega( D^{-1/2})} fraction of constraints.

The idea is to first pick the {X} variables at random, and then to pick the {Y} variables greedily given the choice of the {X} variables.

When we pick the {X} variables at random, the instance reduces to a series of constraints of the form {y_i = b}. Each variable {y_i} belongs to (at most, but let’s assume exactly, which is actually the worst case for the analysis) {D} such constraints; on average, half of those constraints will be {y_i = 0} and half will be {y_i = 1}. If the fixings of clauses of {y_i} were mutually independent (which would be the case in “triangle-free” instances), then we would expect that the difference between 0s and 1s be about {\sqrt D}, so the greedy fixing has a {\Omega(D^{-1/2})} advantage over the random assignment.

In general instances, although we do not have mutual independence, we do have pairwise independence and “almost four-wise independence.” Fix a variable {y_i}, and let us call {E} the set of pairs {\{ j,k \}} such that constraint {y_i \oplus x_j \oplus x_k = b_{j,k}} is part of the instance, for some {b_{j,k}}, and let us call {R_{j,k}} the random variable which is {1} if {x_j \oplus x_k \oplus b_{j,k}=0} and {-1} otherwise, for a random choice of the {X} variables. We want to argue that, with constant probability, {|\sum_{j,k} R_{j,k}| \geq \Omega(\sqrt D)}.

First, we see that the {R_{j,k}} are unbiased, and they are pairwise independent, so {\mathop{\mathbb E} ( \sum_{j,k} R_{j,k})^2 = D}. The fourth moment of {\sum_{j,k} R_{j,k}} is {3D^2 - 2D} plus the number of 4-cycles in the graph that has vertices {x_j} and the edges in {E}. Now, {E} contains {D} edges, a four-cycle is completely described by the first and third edge of the cycle, so the fourth moment is {O(D^2)}. Finally, it is a standard fact that if we have a sum of {D} unbiased {+/- 1} random variables, and the second moment of their sum is {\Omega(D)} and the fourth moment of their sum is {O(D^2)}, then the absolute value of the sum is, on average (and with constant probability) {\Omega(\sqrt D)}.

The algorithm for general CSPs on triangle-free instances is similarly based on the idea or randomly fixing some variables and then greedily fixing the remaining variables. Without the reduction to the “bipartite” case, which does not hold for problems like Max 3SAT, it is more technically involved to argue the advantage over the random assignment.

Is there a polynomial time algorithm that achieves a {\frac 78 + \Omega(D^{-1/2})} approximation ratio for Max 3SAT in instances such that each variable occurs at most {D} times? This remains an open question.

by luca at May 18, 2015 09:14 PM UTC

I've always been impressed how the SIGCOMM conference accepts a very small number of papers, but many hundreds of people attend the conference.  (This is true for some other conferences as well;  SIGCOMM is just he one I happen to know best.)  The conference is somehow an "attend-if-possible" venue for the networking community.  Most other large conferences I know work instead by accepting a lot of papers.  ISIT is a week-long event with 9 parallel sessions (in 2014).   Location may certainly be helpful;  ISIT was in Honolulu in 2014 and Hong Kong in 2015;  SIGCOMM will be in London this year.  But it also isn't decisive;  the Allerton conference has been steadily growing, so it's a few hundred people, even though Urbana-Champaign, where the conference is held, really can't be the biggest draw.  (No offense to those who are there -- I always enjoy visiting!)  In fact, really, at this point, Allerton has been so successful it has seemingly outgrown the Allerton conference center!

If you have ideas for what makes a conference a "must-attend" venue, I'd be interested in hearing them.  The question has arisen because of a Windows on Theory post about changing the format for STOC 2017;  for those of you on the theory side who haven't seen it, I'd recommend looking at the post and registering an opinion by comment or by e-mail to the appropriate parties, after you've considered the issue.  The underlying question is what role should the STOC/FOCS conferences play in the world these days, and how might we change things to get them to play that role.  I think another way of framing this is that I don't think STOC/FOCS aren't really "attend-if-possible" venues for much of the theory community -- particularly for certain subareas -- and the question is whether this can change.  Again, I'd be happy for insights from other communities as well.  

There are a large number of comments already.  I'd say in terms of my personal opinion on what to do I'm most aligned with Alex Lopez-Ortiz and Eric Vigoda.  Alex's point is straightforward -- accept more papers.  I've been in the accept more papers camp for a while (a very old post on the topic suggests one way it could be done), but for some reason there seems to be huge numbers of people in the theory community against the idea, based on some sort of quality argument. For me, the tradeoffs are pretty simple;  I generally prefer not to travel, so I need a good reason to go to a conference, and one very good reason is that I have a paper in the conference that I or a colleague is presenting.  (I recognize this is not true for everyone, but being selective in travel is an issue that arises for people with families, or other regular obligations.)  Clearly conferences such as SIGCOMM show that there are other paths possible, but I'm not clear on how to reproduce that kind of buy-in from the theory community.  Eric's suggestion was that lots of theory conferences happen during the summer, so instead of trying other ways to create a larger "STOC festival", why not co-locate a number of conferences (that would have parallel sessions) that would get more of the theoretical computer science community together.  That makes sense to me, and seems like it could be particularly beneficial for some of the smaller conferences. 

But my personal opinion, while undoubtedly fascinating to some (most notably myself), is really not the point.  The point is for the community to examine the current situation, think if there are ways to make it better, and then act on what they come up with.  The bet way for this to happen is if people actively participate in discussions.   So please, go opine!  There's no reason the post shouldn't have 100+ comments, so comment away.  

by Michael Mitzenmacher ( at May 18, 2015 08:23 PM UTC