Theory of Computing Blog Aggregator

Models for discrete metric spaces

It is good to have random models to test algorithms.

For graph algorithms, the G(n,p) model is like an old friend. For network algorithms, the analog is the complete graph with i.i.d. exponentially distributed edge weights. For algorithms on discrete metric spaces, what's a good model for a random discrete metric space?

Is there a model such that the marginal distribution of the distance between any pair of vertices has an exponential distribution? If so, then what would be a maximum entropy distribution that would have those marginals?

Post a comment

by Claire Mathieu (noreply@blogger.com) at November 08, 2011 12:58 PM UTC

§4.1: DNF formulas

from Ryan O'Donnell

Perhaps the commonest way of representing a boolean function $f : \{0,1\}^n \to \{0,1\}$ is by a DNF formula:

Definition 1 A DNF (disjunctive normal form) formula over boolean variables $x_1, \dots, x_n$ is defined to be a logical OR of terms, each of which is a logical AND of literals. A literal is either a variable $x_i$ or its logical negation $\overline{x}_i$. We insist that no term contains both a variable and its negation. The number of literals in a term is called its width. We often identify a DNF formula with the boolean function $f : \{0,1\}^n \to \{0,1\}$ it computes.

Example 2 Recall the function $\mathrm{Sort}_3$, defined by $\mathrm{Sort}_3(x_1, x_2, x_3) = 1$ if and only if $x_1 \leq x_2 \leq x_3$ or $x_1 \geq x_2 \geq x_3$. We can represent it by a DNF formula as follows: \[ \mathrm{Sort}_3(x_1, x_2, x_3)\ =\ (x_1 \wedge x_2)\ \vee\ (\overline{x}_2 \wedge \overline{x}_3)\ \vee\ (\overline{x}_1 \wedge x_3). \] The DNF representation says that the bits are sorted if either the first two bits are $1$, or the last two bits are $0$, or the first bit is $0$ and the last bit is $1$.

The complexity of a DNF formula is measured by its size and width:

Definition 3 The size of a DNF formula is its number of terms. The width is the maximum width of its terms. Given $f : \{-1,1\}^n \to \{-1,1\}$ we write ${\mathrm{DNF}_{\mathrm{size}}}(f)$ (respectively, ${\mathrm{DNF}_{\mathrm{width}}}(f)$) for the least size (respectively, depth) of a DNF formula computing $f$.

The DNF formula for $\mathrm{Sort}_3$ from Example 2 has size $3$ and width $2$. Every function $f : \{0,1\}^n \to \{0,1\}$ can be computed by a DNF of size at most $2^n$ and width at most $n$ (see the exercises).

There is also a “dual” notion to DNF formulas:

Definition 4 A CNF (conjunctive normal form) formulas is a logical AND of clauses, each of which is a logical OR of literals. Size and width are defined as for DNFs.

Some functions can be represented much more compactly by CNFs than DNFs (see the exercises). On the other hand, if we take a CNF computing $f$ and switch its ANDs and ORs, the result is a DNF computing the dual function $f^\dagger$ (recall Exercise 1.9). Since $f$ and $f^\dagger$ have essentially the same Fourier expansion, there isn’t much difference between CNFs and DNFs when it comes to Fourier analysis. We will therefore focus mainly on DNFs.

DNFs and CNFs are more powerful than decision trees for representing boolean-valued functions, as the following proposition shows:

Proposition 5 Let $f : \{0,1\}^n \to \{0,1\}$ be computable by a decision tree $T$ of size $s$ and depth $k$. Then $f$ is computable by a DNF (and also a CNF) of size at most $s$ and width at most $k$.

Proof: Take each path in $T$ from the root to a leaf labelled $1$ and form the logical AND of the literals describing the path. These are the terms of the required DNF. (For the CNF clauses, take paths to label $0$ and negate all literals describing the path.) $\Box$

Example 6 If we perform this conversion on the decision tree computing $\mathrm{Sort}_3$ in the figure from Chapter 3.2 we get the DNF \[ (\overline{x}_1 \wedge \overline{x}_3 \wedge \overline{x}_2)\ \vee\ (\overline{x}_1 \wedge x_3)\ \vee\ (x_1 \wedge \overline{x}_2 \wedge \overline{x}_3)\ \vee\ (x_2 \wedge x_3). \] This has size $4$ (indeed at most the decision tree size $6$) and width $3$ (indeed at most the decision tree depth $3$). It is not as simple as the equivalent DNF from Example 2, though; DNF representation is not unique.

The class of functions computable by small DNFs is intensively studied in learning theory. This is one reason why the problem of analyzing spectral concentration for DNFs is important. Let’s begin with the simplest method for this: understanding low-degree concentration via total influence. We will switch to $\pm 1$ notation.

Proposition 7 Suppose that $f : \{-1,1\}^n \to \{-1,1\}$ has ${\mathrm{DNF}_{\mathrm{width}}}(f) \leq w$. Then $\mathbf{I}[f] \leq 2w$.

Proof: We use Exercise 2.9 which states that \[ \mathbf{I}[f] = 2\mathop{\bf E}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[\# \text{ $(-1)$-pivotal coordinates for $f$ on ${\boldsymbol{x}}$}], \] where coordinate $i$ is “$(-1)$-pivotal” on input $x$ if $f(x) = -1$ (logical $\mathsf{True}$) but $f(x^{\oplus i}) = 1$ (logical $\mathsf{False}$). It thus suffices to show that on every input $x$ there are at most $w$ coordinates which are $(-1)$-pivotal. To have any $(-1)$-pivotal coordinates at all on $x$ we must have $f(x) = -1$ ($\mathsf{True}$); this means that at least one term $T$ in $f$’s width-$w$ DNF representation must be made $\mathsf{True}$ by $x$. But now if $i$ is a $(-1)$-pivotal coordinate then either $x_i$ or $\overline{x}_i$ must appear in $T$; otherwise, $T$ would still be made true by $x^{\oplus i}$. Thus the number of $(-1)$-pivotal coordinates on $x$ is at most the number of literals in $T$, which is at most $w$. $\Box$

Since $\mathbf{I}[f^\dagger] = \mathbf{I}[f]$ the proposition is also true for CNFs of width at most $w$. The proposition is very close to being tight: The parity function $\chi_{[w]} : \{-1,1\}^n \to \{-1,1\}$ has $\mathbf{I}[\chi_{[w]}] = w$ and ${\mathrm{DNF}_{\mathrm{width}}}(\chi_{[w]}) \leq w$ (the latter being true for all $w$-juntas). In fact, the proposition be improved to give the tight upper bound $w$ (see the exercises).

Using Proposition 3.2 we deduce:

Corollary 8 Let $f : \{-1,1\}^n \to \{-1,1\}$ have ${\mathrm{DNF}_{\mathrm{width}}}(w) \leq w$. Then for $\epsilon > 0$, the Fourier spectrum of $f$ is $\epsilon$-concentrated on degree up to $2w/\epsilon$.

The dependence here on $w$ is of the correct order (by the example of the parity $\chi_{[w]}$ again), but the dependence on $\epsilon$ can be significantly improved as we will see in a later section.

There’s usually more interest in DNF size than in DNF width; for example, learning theorists are often interested in the class of $n$-variable DNFs of size $\mathrm{poly}(n)$. The following fact (similar to Exercise 3.22) helps relate the two, suggesting $O(\log n)$ as an analogous width bound:

Proposition 9 Let $f : \{-1,1\}^n \to \{-1,1\}$ be computable by a DNF (or CNF) of size $s$ and let $\epsilon \in (0, 1]$. Then $f$ is $\epsilon$-close to a function $g$ computable by a DNF of width $\log(s/\epsilon)$.

Proof: Take the DNF computing $f$ and delete all terms with more than $\log(s/\epsilon)$ literals; let $g$ be the function computed by the resulting DNF. For any deleted term $T$, the probability a random input ${\boldsymbol{x}} \sim \{-1,1\}^n$ makes $T$ true is at most $2^{-\log(s/\epsilon)} = \epsilon/s$. Taking a union bound over the (at most $s$) such terms shows that $\mathop{\bf Pr}[g({\boldsymbol{x}}) \neq f({\boldsymbol{x}})] \leq \epsilon$. (A similar proof works for CNFs.) $\Box$

By combining Proposition 9 and Corollary 8 we can deduce (using Exercise 3.16) that DNFs of size $s$ have Fourier spectra $\epsilon$-concentrated up to degree $O(\log(s/\epsilon)/\epsilon)$. Again, the dependence on $\epsilon$ will be improved in a later section. We will also later show in a later section that size-$s$ DNFs have total influence at most $O(\log s)$, something we cannot deduce immediately from Proposition 7.

In light of the Kushilevitz–Mansour learning algorithm it would also be nice to show that $\mathrm{poly}(n)$-size DNFs have their Fourier spectra concentrated on small collections (not necessarily low-degree). In a later section we will show they are $\epsilon$-concentrated on collections of size $n^{O(\log \log n)}$ for any constant $\epsilon>0$. It has been conjectured that this can be improved to $\mathrm{poly}(n)$: \renewcommand{testing}{Mansour’s Conjecture} Let $f : \{-1,1\}^n \to \{-1,1\}$ be computable by a DNF of size $s > 1$ and let $\epsilon \in (0,1/2]$. Strong conjecture: $f$’s Fourier spectrum is $\epsilon$-concentrated on a collection $\mathcal{F}$ with $|\mathcal{F}| \leq s^{O(\log(1/\epsilon))}$. Weaker conjecture: if $s \leq \mathrm{poly}(n)$ and $\epsilon > 0$ is any fixed constant then we have the bound $|\mathcal{F}| \leq \mathrm{poly}(n)$.

by Ryan O'Donnell at January 27, 2012 09:46 PM UTC

Guest post on ITCS by Chazelle

from Computational Complexity

(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012. Applications are due on: Feb 29, 2012. Go here for all the relevant information. Hoping to see you in June. From: Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin.)

(Guest Post by Bernard Chazelle) Why ITCS?

Thanks to Lance and Bill for their kind hospitality. I am delighted to be here. With the third edition of ITCS (formerly ICS) behind us, I thought it would be good to share a few personal, biased thoughts on the subject -- "personal" because I do not claim to speak for the Steering Committee; "biased" because I happen to chair that august body.

First, let me reach for my big bucket of gratitude. Shafi Goldwasser and Silvio Micali did an amazing job as PC & local chairs and I cannot thank them enough. A big shout-out to both. Toda Raba to Yael Kalai, too, for her great help, and to Omer Reingold, Nir Shavit, and their fellow actors for a fabulous "playback" show. If you missed it, fret not. If future organizing committees have any sense, the Nir-Omer show will soon come to a conference near you.

This year's ITCS had about 100 submissions, roughly a 20% growth from previous years, and 118 registrants. Talk attendance never seemed to dip below 90, a heart-warming figure that would be the envy of many conferences. In Shafi's and Silvio's deft hands, innovation came out swinging in all sorts of endearingly creative ways, from session chairs giving annotated previews of the talks to postdocs and graduating students making 5-min pitches to introduce themselves and their research. Brilliant! After watching the new generation of theorists in action, I can tell you that the future of theoretical computer science looks very bright, indeed!

And the future of ITCS, you'll ask, how bright is that? When I chaired the PC last year, a reviewer's comment struck a chord: "This submission would be good for STOC but might not be innovative enough for ICS." Now, that's the spirit! Of course, plenty of ITCS papers would fit in nicely at STOCS/FOCS. (Apparently, more than a few tried to fit in.) That said, it would take an advanced case of color blindness to miss the contrasting hues between ITCS and the rest. All PC members were instructed to add an innovation axis to their evaluation space, and, by golly, they did! (And when I use the word "golly," you know I mean business.)

STOC/FOCS has been accused of all sorts of dastardly deeds unmentionable on a family blog -- from accepting too few papers to boosting trends to rewarding technical wizardry. No less. STOC and FOCS might be four-letter words to some, but to me they're venerable legacy institutions that serve worthy professional functions, such as allowing junior researchers to trade these four-letter words for Theory Club membership cards. Nothing to sneer at. Over at Michael Mitzenmacher's corner, here, Umesh Vazirani bravely suggested merging STOC and FOCS into one mega-conference --- SFOCS, I guess. Much as I love the idea, beginning with the soothing effect of pronouncing the word SFOCS out loud, I didn't come here for a food fight, so I'll fall back on old New Jersey wisdom and say we cross that landfill when we come to it. Yet definitely something to mull over.

ITCS provides a venue for quality outside-the-box thinking. Not without reason, a few have wondered whether the best place outside the box is inside a new conference. On the plus side, conferences provide ideal platforms to publicize new work and, for younger scholars, increase the visibility of their research. With its particular focus on the uncharted, ITCS offers a welcome new outlet for a glut of quality papers. A conference is a big heads-up, a "breaking news" banner flashing on the Theory Channel. It's also a chance to initiate lasting collaborations and meet extraordinary people in pursuit of extraordinary ideas. It's fun.The downside is that a human being can attend only so many conferences before "their budget glares red and their head bursts in air" (as they say before kick-off at the Super Bowl).

This dichotomy, however, isn't quite right. It ignores the tangled web the online revolution has woven into our lives. Whereas in the past I'd have to go to a conference to hear a new result, this is no longer so. The PDF will come to me. It's a given that attendees at many talks will already know the results, perhaps even the proofs. This has diminished the relative importance of attending a conference while at the same time increasing its reach, and hence its influence. Don't get me wrong. I am not saying ITCS is so cool you don't even have to go. I am saying that, in the age of instant downloads, missing this month's Jay-Z & Kanye West "UGC" gig at the Garden ain't gonna be the heartbreak it would have been in the days of old. So, while I recognize that the burden of extra travel is a drawback and the timing always an issue, our wired world alleviates these concerns somewhat. And if you find this argument too subtle for its own good, well, remember, there's always the Umesh option.

Another worry heard on Theory Street is fragmentation. I don't get that. The sociological makeup of all these conferences is pretty much the same, anyway, so the risk of fragmentation is about as high as that of Dr. Jekyll and Mr. Hyde parting ways -- OK, make that Superman and Clark Kent if you prefer. In fact, this has it exactly backwards. Theory has yet to penetrate many geographical markets. Eurotheory shares a name with our kind, and little else. With Asia a promising growth area for our field, it is of more than symbolic value that ITCS was born in China. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc). Maybe ITCS can be the exception. At any rate, to expand both the intellectual footprint and the geographical reach of Theory is a central goal of this conference.

To close on a personal note, let me get my crystal ball out of its dusty case and tell you what I see. As the new sciences of the 21st century further embrace their algorithmic nature, I see ITCS getting enriched with a growing flow of conceptual imports from physics, biology, economics, etc (and vice-versa). While the letter T was added to ICS for mundane reasons -- an ACM conference had a previous claim on the acronym -- I hope ITCS remains unabashedly theoretical. Yes, you heard right. And as you watch me adroitly duck the tomatoes sure to be hurled my way for this impolitic stand, you might even spot a contradiction or two. I mean, how can computing theory reach out to the sciences without losing its theoretical core? Well, well... Leaving aside the fact that math developed with precisely that sort of outreach, the answer is easy. What the "new" sciences (bio, neuro, socio, and all that) lack more than anything is a conceptual framework. Theoretical computer science can do for them what mathematics did for physics. Why? Because algorithms are the differential equations of the 21st c. They are the language of modern science. That's why. At this point, you expect me to clear my throat and indulge in a tasteful round of name dropping: "Moreover, as Newton and Einstein used to say, blah blah..." (I got that from my physicist friends. Works every time.)

But not today. Truth is, delusion won't help our cause one bit. Neither will diffidence or skittishness, however. These are heady times for computing theory, my friends. Hand wringing over fine tactical points should not distract us from our common goal, which is to allow Theory to expand and flourish, to unite and conquer. ITCS aims to do just that. It is an exciting experiment worthy of your support.

Thanks for your attention and, in a nod to ITCS' roots, a happy Year of the Dragon to all!

Bernard Chazelle

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at January 27, 2012 03:18 PM UTC

Watermarking molecules

from Aaron Sterling

I’ve posted twice about Anonymous hacking into Stratfor — and, more generally, their hacktivism has been making bigger and bigger waves. CNN recently ran a fairly positive story on the support hacktivists are providing the Occupy movement. Many of these hacktivists are quite active on Twitter and elsewhere. However, from the perspective of both international and corporate espionage, the “quiet” hacks are the worst: someone makes off with information and the victim never knows. As security expert Kevin Mandia told the New York Times:

The hacks that do the most damage don’t have Twitter feeds.

Another security expert, Jeremy Falkenrath, in an interview on Bloomberg News (at about 7:00 into the video), discussed, quite matter-of-factly, the hacker-for-hire market that companies in the chemical industry deploy against one another to learn trade secrets. With this as the backdrop, I’d like to discuss one of the main open questions of cheminformatics: Is secure encryption of molecules possible? For example, it would be nice if a company could encrypt a molecule, but then allow some third party to run in silico tests with it, having access to the molecule’s properties but not the structure itself.

Encryption of molecules

Part of the reason for the traditional closed-data policies of pharmaceutical companies is the total absence of any way to encrypt chemical structural information. This has been recognized as an open problem for many years, the American Chemical Society held a special meeting in 2005 about it, a summary of which appeared in Nature. While there were presenters at that meeting who felt molecular encryption was possible, and others who felt it was impossible, the practical reality as we enter 2012 is that, so far, the voices in favor of “impossible” have been correct. Almost no new theoretical literature has been produced since 2005, and the industry appears no nearer a practical solution than it was in, say, 1975.

I recently had an idea to expand upon a proposal by Eggers et al. in 2001, to watermark in silico representations of molecules. My idea, however, is going nowhere — just like all other attempts so far to implement chemical watermarking. At least I can get a blog entry out of my failure though! I hope readers of this page find my little attempt entertaining or informative.

Acknowledgement: The material in this post is based on conversations I have had with cheminformaticians Rajarshi Guha and Jörg Kurt Wegner.

Watermarking molecules

A digital watermark, of course, is a special code embedded into a file so that its provenance can be determined. The file has to be large enough so that perturbations to individual data points are not feasibly discoverable to a would-be forger, even though there are enough data points to produce a unique fingerprint for that file, at least with high probability. In 2001, Eggers et al. published Digital Watermarking of Chemical Structure Sets, which proposed the use of SCS watermarking on databases of molecules, so that the company that had created or owned the molecules would be able to prove that another company’s claim to independent discovery was, in fact, infringement.

A single molecule is not large enough to embed an indiscernible watermark, which is why Eggers et al. considered “structure sets” — a large list of molecules that are somehow related. Technically, each molecule is considered as a graph embedded into three-dimensional space. (In fact, this graph may be the “reduced graph,” or a graph of the molecule with all hydrogen atoms removed, because reduced graphs performed better on one empirical test in their study.) I will ignore a lot of technical details here, but the core idea behind their watermarking process is to perturb the 3D coordinate of specially-chosen atoms by a small, “random-appearing” amount. If enough locations of atoms in the structure set are modified this way, it produces a digital watermark.

More interesting to me than the watermarking method was the list of potential attacks Eggers et al. considered. If the attacker can do anything, it is famously difficult to encrypt data while still providing functionality. However, we are working in the chemistry domain. On the one hand, this adds technical obstacles (due to “real-world messiness”), but, on the other hand, it may limit the attacks that can be performed on the system, since the attackers need to obtain a structure that is chemically useful, not just some fragment of plaintext. Eggers et al. tried to provide a watermarking method resilient to the following attacks.

Removal of data from the original dataset.
Injection of non-watermarked structures into the dataset.
Reordering of individual records in the dataset.
Reordering of atoms and bonds in the structure records.
Global 3D transforms, e.g., rotations or translations.
Changes of structural notation conventions.
Removal of hydrogen atoms from structures.

My new idea and why it fails

I will cut to the chase and explain why my idea doesn’t work — and why, perhaps, no watermarking concept is feasible in the chemical domain. Then I will conclude, anticlimactically, by describing my idea, in case someone can get something out of it.

Consider the domain of music piracy. The attacker can hear the music, and perhaps even has access to guitar tabs or a symphony score. However, it would not be cost-benefit for the attacker to hire a brand-new orchestra to re-record the original piece of music — and, even if the attacker did that, the new track would not sound exactly the same. By contrast, in chemistry, every carbon atom is identical to every other carbon atom. So in the case of a chemikcal structure set, the attacker could choose a molecule(s) of interest, and then just rebuild the structure from scratch, and use the 3D coordinates (and all other information) from the brand new molecule. Presto, no watermark.

Eggers et al. consider this attack, sort of. They say:

We assume that no unlicensed copies of the software used to generate the original protected dataset are provided in circulation. Furthermore, the computation time for large datasets in often significant. Depending on the type of algorithm used and the size of the dataset, it can be up to several CPU months. Thus, simple regeneration of the data is often not a feasible approach.

While the claim about significant recomputation time may have been true in 2001, it no longer appears to be. As one chemist said to me, recomputation of a molecular structure “wouldn’t be hard at all.” This leaves the only defense of a watermark the unavailability of licensed software to perform the recomputation. That, however, relies on an attacker who is willing to perform industrial espionage but who draws the line at software piracy. So, no go.

Now we get to my idea. In the field of image processing there has been a lot of work since 2001 on 3D watermarking. One survey is 3D Watermarking: Techniques and Directions, by Koz et al., which considers strengths and weaknesses of many different watermarking techniques. One method that caught my eye was Robust Image Watermarking Based on Generalized Radon Transformations, by Simitopolous et al., because it is specifically designed to be resistant to “geometric attacks” like rotation, scaling, translaton and cropping, which closely follow the list of anticipated attacks in the Eggers et al. paper. Applying this to chemistry might provide a much better watermarking tool than the more generic watermarking method chosen by Eggers et al.

However, I’ve decided not to consider this further, because it seems that the most I could get out of it would be a paper that would be theoretically “cute,” with no chance of being practical, ever. I would love to be proven wrong, so if you can think of a way to get around the “rebuild the molecule from scratch” attack, please do comment. In the meantime, I am on to other things.

Joachim J. Eggers, W.D. Ihlenfeldt, & Bernd Girod (2001). Digital Watermarking of Chemical Structure Sets Information Hiding, 200-214 DOI: 10.1007/3-540-45496-9_15

Tagged: cheminformatics, chemoinformatics, cryptography

by Aaron Sterling at January 27, 2012 03:00 PM UTC

Boycott Elsevier!

from Scott Aaronson

If you’re in academia and haven’t done so yet, please take a moment to sign this online petition organized by Tyler Neylon, and pledge that you won’t publish, referee, or do editorial work for any Elsevier journals. I’ve been boycotting Elsevier (and most other commercial journal publishers—Elsevier is merely the worst) since 2004, when I first learned about their rapacious pricing policies. I couldn’t possibly be happier with my choice: unlike most idealistic principles, this one gets you out of onerous work rather than committing you to it! Sure, Elsevier is huge and we’re tiny, but the fight against them is finally gathering steam (possibly because of Elseiver’s support for SOPA, PIPA, and the “Research Works Act”), years after the case against them became inarguable. Since their entire business model depends on our donating free labor to them, all it will take to bring them down is for enough of us to decide we’re through being had. We can actually win this one … Yes We Can.

For more information, see this wonderful recent post by Fields medalist and Shtetl-Optimized commenter Timothy Gowers, entitled “Elsevier — my part in its downfall.” (Added: also check out this great post by Aram Harrow.) You might also enjoy a parody piece I wrote years ago, trying to imagine how Elsevier’s “squeeze those dupes for all they’ve got” business model would work in any other industry.

by Scott at January 27, 2012 04:05 AM UTC

Faculty Applications

from Michael Mitzenmacher

An anonymous commenter asked how we evaluate faculty applications. While it's a little late, it's a valid question, so here are some high-level thoughts. Here I'm speaking only for myself, of course.

First, I should point out that ideally, we're not reading your application from scratch -- we already know you. We've seen you give a talk we like, or enjoyed one of your papers, or otherwise formed a (positive) impression. The most important things you can do when applying come well before you write up your application. If you're not taking advantage of opportunities to make yourself known in the community as a graduate student, you're not doing your job. [Obviously, we don't only look at applications of people we already know. But that just makes our job harder, and makes it harder for you to get picked out of the crowd.]

After that, it's not exactly rocket science. I'm looking for a strong record, and the first things I'm looking for are good publications and good letters. Applicants on the first pass are usually sorted into 3 basic categories: invite for an interview, decline, or study further. The publications and letters are the best guide for what pile you'll go into.

Once the pack is cut down, more details will come into play. Some of us will probably read your papers to get a better idea your work. Natural more detailed questions come up: How interesting is your work? How well do you fit our department needs? What teaching experience do you have? Is Harvard a place where we think you would be successful? (For example, what other areas of Harvard might serve as possible points of collaboration?)

The interview helps us answer these questions further. At the end of the day, what we're deciding is if we want you as a member of our department. Research quality is a primary issue, and usually the primary issue. But at this point, hopefully all of the people we're looking at have high-quality research records, with results that we collectively find compelling. So the secondary issues I mentioned -- are you a good fit for us, are we a good fit for you? -- do matter.

In the end, I don't think there's too much you can do to "strategize" your application -- because the main issues are to have a good work record, get people who can write you good letters, and be an interesting person who seems like they'd make a good colleague. I expect that's not surprising anyone. Though I'm sure since I wrote this a bit hurriedly, someone will point out where I've not described things suitably carefully or in enough detail.

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at January 27, 2012 12:35 AM UTC

BIN@ERN: Binary-Ternary Compressing Data Coding

from arXiv.org: Data structures and Algorithms

Authors: Igor Nesiolovskiy, Artem Nesiolovskiy
Download: PDF
Abstract: This paper describes a new method of data encoding which may be used in various modern digital, computer and telecommunication systems and devices. The method permits the compression of data for storage or transmission, allowing the exact original data to be reconstructed without any loss of content. The method is characterized by the simplicity of implementation, as well as high speed and compression ratio. The method is based on a unique scheme of binary-ternary prefix-free encoding of characters of the original data. This scheme does not require the transmission of the code tables from encoder to decoder; allows for the linear presentation of the code lists; permits the usage of computable indexes of the prefix codes in a linear list for decoding; makes it possible to estimate the compression ratio prior to encoding; makes the usage of multiplication and division operations, as well as operations with the floating point unnecessary; proves to be effective for static as well as adaptive coding; applicable to character sets of any size; allows for repeated compression to improve the ratio.

at January 27, 2012 01:40 AM UTC

Faster and Simpler Minimal Conflicting Set Identification

from arXiv.org: Data structures and Algorithms

Authors: Aida Ouangraoua, Mathieu Raffinot
Download: PDF
Abstract: Let C be a finite set of N elements and R = r_1,r_2,..., r_m a family of M subsets of C. A subset X of R verifies the Consecutive Ones Property (C1P) if there exists a permutation P of C such that each r_i in X is an interval of P. A Minimal Conflicting Set (MCS) S is a subset of R that does not verify the C1P, but such that any of its proper subsets does. In this paper, we present a new simpler and faster algorithm to decide if a given element r in R belongs to at least one MCS. Our algorithm runs in O(N^2M^2 + NM^7), largely improving the current O(M^6N^5 (M+N)^2 log(M+N)) fastest algorithm of [Blin {\em et al}, CSR 2011]. The new algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs instead of Tucker matrices.

at January 27, 2012 01:40 AM UTC

Chapter 4: DNF formulas and small-depth circuits

from Ryan O'Donnell

In this chapter we investigate boolean functions representable by small DNF formulas and constant-depth circuits; these are significant generalizations of decision trees. Besides being natural from a computational point of view, these representation classes are close to the limit of what complexity theorists can “understand” (e.g., prove explicit lower bounds for). One reason for this is that functions in these classes have strong Fourier concentration properties.

by Ryan O'Donnell at January 26, 2012 11:16 PM UTC

Chapters 1–3: pdf draft

from Ryan O'Donnell

By popular request, here is a draft of Chapters 1–3 of the Analysis of Boolean Functions book.

by Ryan O'Donnell at January 26, 2012 11:08 PM UTC

the new theorymatters

from Luca Trevisan

The theorymatters.org site has been redesigned as a blog. Watch it for informations about funding, jobs, and other stuff from the committee for the advancement of theoretical computer science.

by luca at January 26, 2012 10:22 PM UTC

Postdoc at Saarland University, Saarbruecken

from CCI: jobs

3 year position in algebraic complexity theory at Saarland University, Saarbruecken. Screening starts immediately until the position is filled. Send application including cv and potential references by email to Markus Bläser (mblaeser*at*cs.uni-saarland.de)

by tdomf_3bd55 at January 26, 2012 08:38 PM UTC

Postdoc positions

from Theory Matters

A quick roundup of postdoc and faculty positions currently advertised at http://intractability.princeton.edu/jobs/ whose deadlines have not yet passed:

Postdoc at KTH Royal Institute of Technology (deadline Jan 31)
Postdoc at Cornell at the interface of networks, computing, and economics (deadline Jan 30)
Simons postdoc at Carnegie Mellon (deadline Jan 31)
Postdoc at LIAFA (Paris) (deadline Feb 1)
Theory Postdoc at EPFL and Faculty positions at EPFL (no deadline stated)
Postdoc in Theory/Practice of Differential Privacy at UPenn (no deadline stated)
Postdoc in Cryptography at Tel-Aviv University (no deadline stated)
Faculty positions at Northeastern University, Boston. (no deadline stated)
Tenure-track Faculty Position at Purdue (Krannert School of Management) (no deadline stated)

Check http://intractability.princeton.edu/jobs/ for further updates.

by avrimblum at January 26, 2012 03:56 PM UTC

Scrabble is PSPACE-Complete

from arXiv.org: Computational complexity

Authors: Michael Lampis, Valia Mitsou, Karolina Sołtys
Download: PDF
Abstract: In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Erik Demaine and Robert Hearn.

at January 26, 2012 01:40 AM UTC

Finding short vectors in a lattice of Voronoi's first kind

from arXiv.org: Data structures and Algorithms

Authors: Robby McKilliam, Alex Grant
Download: PDF
Abstract: We show that for those lattices of Voronoi's first kind, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.

at January 26, 2012 01:40 AM UTC

Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

from arXiv.org: Data structures and Algorithms

Authors: Richard Peng, Kanat Tangwongsan
Download: PDF
Abstract: This paper studies the problem of finding a (1+eps)-approximation to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraints and objective are positive semidefinite and all scalars are non-negative. Previous work (Jain and Yao, FOCS'11) gave an NC algorithm that requires at least Omega((1/eps)^13\log^{13}n) iterations. The algorithm performs at least Omega(n^\omega) work per iteration, where n is the dimension of the matrices involved, since each iteration involves computing spectral decomposition.

We present a simpler NC parallel algorithm that requires O((1/eps)^4 \log^4 n \log(1/eps)) iterations. Moreover, if the positive SDP is provided in a factorized form, the total work of our algorithm can be bounded by \otilde(n+M), where M is the total number of nonzero entries in the factorization. Our algorithm is a generalization of Young's algorithm and analysis techniques for positive linear programs (Young, FOCS'01) to the semidefinite programming setting.

at January 26, 2012 01:40 AM UTC

Collective Coordination of Conferences?

from Michael Mitzenmacher

Around this time of year, I get a number of messages from students: I want to take your class, but there's a conflict with this other class I want to take, what can be done... Sometimes a solution can be worked out, sometimes not. It's not an easy issue to deal with. In Computer Science, we take a look at our own schedule of classes, and try to make sure there aren't any particularly bad time conflicts among our own classes, although inevitably there are some hopefully minor ones. Then we try to look at other big classes in related areas -- try not to have our intro classes the same time as the intro economics, physics, statistics courses, etc. Of course we also try to let them know when our big intro courses are, so they don't reschedule classes into those time slots as well. In the end I think we do a reasonably good job.

That was a long-winded roundabout to where I wanted to get to, which is conference scheduling. It's something that I think is becoming increasingly broken -- at least for theory conferences* -- due to the fact that there is (as far as I know) minimal coordination going on with respect to the calendar, and there's an ever-increasing number of conferences and workshops. The near-overlap of ITCS and SODA is one obvious example. The nearly-overlapping SPAA and PODC deadlines are another.** I'm sure one can come up with hosts of others, and that's excluding the issue of trying to coordinate with other adjacent fields. (For many years, INFOCOM and SODA deadlines, as I recall, were within a couple of days of each other -- and July 4th! Not friendly, especially not family friendly.)

I'm not claiming we want full centralization of conference scheduling. But I do think there should be a lot more of it than we have. A lot of aspects of the conference calendar -- dates, how many conferences we have, where they're located -- don't make a lot of sense to me, and I think that's because they don't make a lot sense. I don't know how we arrange for a body to try to look at where we're at and figure out how to make it globally better. But I wish someone would!

* I haven't noticed this so much for other areas -- in networking, SIGCOMM, INFOCOM, NSDI, IMC, and even Allerton have always seemed reasonably spread out to me, but perhaps I just haven't noticed the problem.

** I've thought SPAA and PODC should have some sort of "merge" for almost 20 years now. You're different communities? Fine. Then arrange a permanent co-location agreement. It would be better for both conferences.

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at January 25, 2012 11:34 PM UTC

Report from SODA 2012: Part 2

from Noam Nisan

Guest post by Ashwinkumar Badanidiyuru.

There has already been some info on the blogs on SODA here. The conference was well organized and the number of researchers attending the conference was also considerable. I really liked the cleanliness of Kyoto and the punctuality of trains.

The negative things were that the conference did not organize a breakfast and coffee was not available at all breaks. I and a couple of my friends also felt a terrible jet lag. Another problem which we faced while roaming around was the availability of vegetarian food.

There were two main sessions related to game theory and mechanism design. I will blog here about one of the sessions and my colleague Hu Fu has already blogged about the other.

The Notion of a Rational Convex Program, and An Algorithm for the Arrow-Debreu Nash Bargaining Game. (Vijay Vazirani):A nice blog post about this line of work has already been written here. This paper introduces the notion of a rational convex program (RCP). RCP is a convex program that is guaranteed to have an optimal solution, which is rational and has polynomially non-zero bits given any setting of its parameters to rational numbers and the optimal solution is bounded. This paper defined a new Nash bargaining game and shows that it is logarithmic RCP (Objective function is a sum of logarithm of linear functions). It also gives a combinatorial algorithm to compute an equilibrium of such a game.
Beyond Myopic Best Response in Cournot Competition. (Svetlana Olonetsky, Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour): This paper studies the best response strategies when the best response is non-myopic. (i.e. depends on how the other player could potentially choose the strategy in the next round). Consider the Cournot competition game where two firms produce oil, Firm1 at a cost of 0.3 dollars/barrel and Firm2 at a cost of 0.5 dollars/barrel. Let the price set by the market be 1-(number of barrels produced). In a Nash equilibrium Firm1 produces 0.3 barrels and Firm2 produces 0.1 barrels. But if Firm1 produced 0.5+ε barrels then Firm2 would drop out and Firm1gets a better return. This hints that Nash might not be the right solution concept.The solution concept proposed and studied in this paper is a delegation game where in the first round it is decided if each player is supposed to maximize his profit or revenue and in the second round the game is played. The part which confuses me is that this looks like something in between a one shot and a multi-round game.
Metastability of Logit Dynamics for Coordination Games. (Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano): Usually in learning in games we study the stationary distribution of some noisy response strategy. This becomes not so interesting if the mixing time is very large. This paper studies the transient phase for Logit Dynamics for Coordination Games. It studies something called metastable distribution in which the game is present for a time-scale shorter than the mixing time. As an example it gives Ising’s game (similar to Ising’s model) where it takes exponential time to mix (under suitable parameters), while there are meta stable distributions. An interesting question would be computing a meta-stable distribution if the pseudo-mixing time is not polynomial.
Sketching Valuation Functions. (Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden): We study the problem of storing an approximate version of different classes of valuation functions in polynomial space. The problem is motivated by sealed bid combinatorial auctions in which the bidders first write some version of their valuation and then send it to auctioneer. Then, the auctioneer uses this to allocate the items. This research is along the lines of a paper by Goemans, Harvey, Iwata and Mirrokni which gives an algorithm to find a -sketch for submodular functions using polynomially many value queries. There is also a lower bound of using arbitrary communication, stemming from the work of Balcan and Harveyon learning submodular functions in the PMAC model. Some of the interesting results in this paper are:
A very recent arXiv paper on learning valuation functions in the PMAC model, by Balcan, Constantin, Iwata, and Wang, contains a set of closely related (and in a few cases, overlapping) results that were independently discovered at the same time.
Voting with Limited Information and Many Alternatives. (Jon M. Kleinberg, Flavio Cherichetti): In this work an adversary first chooses an urn from a set of urns, each containing red and blue balls. Each voter knows the set of urns, but not the urn chosen by adversary. Then, each voter chooses a random ball from the chosen urn and votes for his/her guess for the right urn. The voters win if the chosen urn gets the maximum number of votes. The paper proves that ${O(n^5 \log(1/\delta))}$ voters are enough for this and surprisingly if each person gets to divide his vote among multiple urns then ${O(n^2 \log(1/\delta))}$ voters are enough to win with probability 1-δ. The second result is surprising since even a single person drawing random ball from the urn requires so many draws. The main motivation for this result is the problem where a set of jurors vote in a criminal trial. This is related to the Condorcet Jury Theorem.

There were some other interesting papers, a couple of which are described below.

Popularity Vs Maximum Cardinality in the Stable Marriage Setting. (Telikepalli Kavitha).Extends Gale-Shapley algorithm to compute matching with small unpopularity. The algorithm is roughly a multi round GS algorithm where an unmatched boy re-proposes in the next round and any boy in round i gets preference over any boy in round j<i. The interesting feature of this algorithm is that at round i all augmenting paths of length i are avoided.
Gathering Despite Mischief. (Yoann Dieudonne, Andrzej Pele and David Peleg).Consider a group of individuals, each moving synchronously in a network. The goal is for them to meet together at a node. There could be byzantine individuals which are either making incorrect moves or are sharing wrong information with other individuals. This paper gives upper and lower bounds (mostly not matching) for the total number of individuals necessary for a protocol to exist. An interesting result is a tight bound of f+2 in one of the models. Most bounds in this area do not seem to be of this form.
Private Data Release Via Learning Thresholds. (Moritz Hardt, Guy Rothblum and Rocco A. Servedio).This paper gives a computationally efficient reduction from differentially private data release to learning thresholded sums of predicates.
Matroidal Degree-Bounded Minimum Spanning Trees. (Rico Zenklusen).This paper generalizes the classic problem of degree bounded spanning tree to the case where we need to have a spanning tree with a matroid constraint for every node over which edges can be chosen. It gives an algorithm which returns a spanning tree of cost at most OPT and which violates each matroid constraint by at most eight elements. Seems to use similar techniques as Lau-Singh with non-trivial generalizations.
Submodular Functions are Noise Stable. (Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee).This paper is a simple observation that submodular functions are noise stable and hence can be agnostically learned.
Random Walks, Electric Networks and The Transience Class Problem of Sandpiles. (Ayush Choure, Sundar Vishwananthan).In the sandpiles model you have a grid and sand particles are added one by one to some square in the grid. When the number of particles reaches a threshold they flip to adjacent squares. This paper studies and gives a bound for number of particles to be added to one corner of a square grid for the other corner to flip. I am curious if this model is also applicable to certain settings in social networks.
Information Dissemination Via Random Walks in D-Dimensional Space. (Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiarui Sun, Yajun Wang).This paper considers the problem of m agents placed uniformly at random in a d-dimensional (d>2) hypercube and gives nearly tight bounds on the time required for information dissemination when one agent holds it. The interesting phenomenon for d>2 is a phase transition not seen when d=2. The asymptotic rate for time required follows different functions in two different ranges for m.
Rumor Spreading and Vertex Expansion. (George Giakkoupis, Thomas Sauerwald).Gives nearly tight bounds on round complexity of rumor spreading in terms of vertex expansion. The lower bound for parameters such as vertex expansion only happen in specific class of graphs. It is interesting if there is a graph parameter which tightly bounds rumor spreading in every graph.
Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation. (Shayan Oveis Gharan, Vahab Mirrokni, Morteza Zadimoghaddam).This paper analyses an existing algorithm for the online budgeted allocation and proves that it has a simultaneous approximation for adversarial as well as stochastic version of the problem.
Improved Competitive Ratio for the Matroid Secretary Problem. (Oded Lachish, Sourav Chakraborty).This paper improves the competitive ratio of the matroid secretary problem to √log(rank). The surprising fact is that the paper is able to do so using some variant of binning.

by robertkleinberg at January 25, 2012 10:44 PM UTC

Guest post by Oded Goldreich II

from Luca Trevisan

[Oded Goldreich has written a new essay, which he summarizes in the guest post below. Oded looks at the distinction between "primary" and "secondary" accomplishments, that is between doing good stuff and receiving "awards", where "award" should be taken broadly to mean something that is given after a competition that has no other purpose than choosing a winner. Oded points to the negative effects of having important decisions, e.g. about jobs, funding and promotions, be based on "secondary" rather than "primary" accomplishments, because it pushes researchers to optimize the former, which is not good for anybody. This is a broad problem with "secondary" metrics, e.g. when schools are evaluated based on test scores or police departments based on crime statistics. (I assume we have all watched The Wire.) Oded concludes that we should abolish "awards" whenever possible; I disagree with this conclusion and I will write about it in the comments. L.T.]

The purpose of this post is to call your attention to my essay “On Struggle and Competition in Scientific Fields”, which is available from the web-page www.wisdom.weizmann.ac.il/~oded/on-struggle.html

The current essay is only remotely related to my essay “On the status of intellectual values in TOC”. So I do hope that those who misunderstood and/or disagreed with the prior essay will not hold this against the current one.

The current essay is pivoted at notions such as achievement, importance, and competition. It addresses question such as the following ones. What is the difference between struggling for achievements and competing for success? What is the effect of competitions on a scientific field? What are the specific implications on TOC?

Of course, my issue is not with the semantics of (the colloquial meaning of) the forgoing words, but rather with fundamentally different situations which can be identified by referring to these words.

Loosely speaking, by struggle I mean an inherent conflict between different people who attempt to achieve various goals and positions relative to a given setting. That is, the achievements determine the outcome of the struggle. In contrast, by competitions I mean artificial constructs that are defined on top of the basic setting, while not being inherent to it, and success typically refer to winning these competitions. That is, success is determined by the outcome of the competition.

Of course, once these competitions are introduced, the setting changes; that is, a new setting is constructed in which these competitions are an inherent part. Still, in some cases — most notably in scientific fields, one may articulate in what sense the original (or basic) setting is better that the modified setting (i.e., the setting modified by competitions). These issues as well as related ones are the topic of the current essay.

The core of the essay is Section 2.1, which provides a theoretical framework in which all these notions are discussed. This framework is used in Sections 2.2 and 2.3, which revisit familiar issues such as the evolution of the FOCS/STOC conferences, the effects of awards, and why is excessive competition bad. In particular, I trace several negative social phenomena in TOC to the growing dominance of various competitions in TOC. In Section 3, I discuss the possibility of reversing the course of this evolution and reducing the dominance of competitions in TOC.

Indeed, I have expressed similar opinions regarding the evolution of FOCS/STOC and awards in the past, but I feel that the framework presented in Section 2.1 provides a better articulation of these opinions as well as a wider perspective on them. Actually, my first, initial, and most important goal in writing this essay is to clarify to myself and to other interested readers a few issues that are quite central to our professional life. My hope that I may contribute to a change in hearts, and then to a change in reality, only comes second.

Oded Goldreich

by luca at January 25, 2012 06:55 PM UTC

The next Women in Theory Workshop

from Luca Trevisan

[I am happy to relay this announcement from Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin]

Calling all Women PhD Students (and a few undergrads)

We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton.

The dates are June 23-27, 2012.

Applications are due on: Feb 29, 2012.

Go to: http://womenintheory.wordpress.com/ for all the relevant information.

by luca at January 25, 2012 06:35 PM UTC

Ernst Specker (1920-2011)

from Computational Complexity

Martin Fürer remembers his former advisor.

While traveling, I received the unexpected sad news that Ernst Specker passed away on December 10, 2011. He was born in Zürich in 1920. After receiving his doctoral degree at ETH Zürich in 1949, he spent a year at the Institute for Advanced Study in Princeton. Then he returned to ETH in 1950 and stayed there with the exception of two visiting appointments at Cornell University.

Ernst Specker was teaching Linear Algebra when I started my studies at ETH Zürich in 1967. His teaching style was different from the typical polished and streamlined presentations of that time. He was looking for interaction, and did not hesitate to interrupt a proof to insert an example when he sensed that the audience was not following.

Outside the classroom, it was a turbulent time. The youth movement started to question many long established rules of society. For a long time, it seems that the majority of people, without ever thinking about it, had accepted the claim that the US with its war in Vietnam was defending western values. Quite suddenly, this consensus was widely questioned.

ETH had its own little problem. A new law governing the ETH (the only federal university in Switzerland) had just been adopted by the parliament. Many students took issue with the idea that the main goal of ETH was not to satisfy a general human right for education, but to prepare the students to serve the interests of business and industries.

Ernst Specker, who always liked discussions, never accepted anything based on authority without asking some critical questions, had quickly established a relationship with the young students at this time of evolving political turmoil.

Here are two examples, typical for Ernst. The mathematics and physics students of each semester had an open discussion about the ETH law. One professors came to our group to tell us, we should not complain, its our fault, we should have had this discussion a year ago, when it was the proper time to voice any opposition. He was not happy, when Ernst disagreed, noticing that this group of students has only been here for half a year.

A more important move was Ernst Specker's engagement for the Manifesto of Zürich, a public declaration against police brutality after some excesses when the "establishment" was shocked and fearful of the demonstrations in downtown Zürich.

During our studies, we all had to give talks in four seminars in different areas of mathematics. This rule was widely followed with one exception. A large group of students participated in the logic seminar, and they came back ever since (naturally in addition to the other seminars). Every semester, there was a different theme. My first subject was the solution of Hilbert's tenth problem, presented with all background information and details. The seminar was conducted with Hans Läuchli. Paul Bernays, who had started the seminar when he came from Göttingen before the second world war, was still a regular participant. He often followed the talks reading the blackboard with a two minute delay.

Ernst conducted the seminar still long after his retirement, because unfortunately ETH no longer had a position for mathematical logic. I participated in Ernst’s last logic seminar during my sabbatical in 2002. We ended the semester with a talk of Ernst that was intended for a general mathematical audience. I reserved the beautiful and rather spacious Aula of the ETH for this purpose. Luckily, we could still switch to the Auditorium Maximum, in the last minute, when we saw the people arriving.

Scientifically, Ernst Specker has worked in many areas as illustrated in by the Selecta volume published by Birkhäuser on the occasion of his 70th birthday. In his dissertation with Heinz Hopf, Ernst worked on cohomology groups. Then he moved on to investigate constructively in analysis, and the foundation of set theory, in particular Quine's new foundations. He also solved one of the early Erdős problems. Ernst’s most famous results are the works with Simon Kochen on the foundations of quantum mechanics, proving that certain hidden variable theories are not possible, and thus colliding with the assumptions made in the famous Einstein-Podolsky-Rosen paper. The results of Kochen and Specker are still discussed today in the physics literature. Early on and in his additional weekly seminar with Volker Strassen starting in the early seventies, he reached out to complexity theory.

Ernst Specker will always be remembered for his teaching and his scientific work, but most of all for his friendship, his openness and his engaging discussions.

Martin Fürer
Pennsylvania State University

Subscribe to comments |

Post a comment

by Lance Fortnow (noreply@blogger.com) at January 25, 2012 02:19 PM UTC

Two announcements of interest

from Jonathan Katz

Cybersecurity Research Experience for Undergraduates in Science and Engineering at the University of Maryland (Note: I am one of the faculty mentors for this.)
Women in Theory Workshop

See below for more details.

Cybersecurity Research Experience for Undergraduates in Science and Engineering at the University of Maryland

We are looking for Cybersecurity Scholars for the 2012 summer research experience for undergraduates (REU) program at the University of Maryland.

APPLICATION DEADLINE: February 15, 2012

The Clark School of Engineering at the University of Maryland is seeking applications for scholars to become integral members of team-based research projects in cybersecurity coordinated by faculty in the Maryland Cybersecurity Center (MC2). Students majoring in engineering, computer science, math, and physical science are strongly encouraged to apply.

Teams conduct research from June 4 through August 3, 2012. The program offers multiple tiers of mentorship and training in team skills and project organization, as well as addressing issues of concern to women and minorities in science and engineering. Each Scholar receives a $4,500 stipend, a $300 food allowance, and housing. Funding is available for transportation.

For additional information and applications, please review the Cybersecurity REU website or contact Dr. Michel Cukier (mcukier@umd.edu or 301-314-2804).

This program is funded by the National Science Foundation and the Clark School of Engineering.

Women in Theory Workshop

Calling all Women PhD Students (and a few undergrads). We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012.

Applications are due on Feb 29, 2012.

See here for all the relevant information.

Hoping to see you in June!
Shubhangi Saraf, Lisa Zhang, Moses Charikar, and Tal Rabin

by jonkatz at January 25, 2012 01:33 AM UTC

Online Multi-Commodity Flow with High Demands

from arXiv.org: Data structures and Algorithms

Authors: Guy Even, Moti Medina
Download: PDF
Abstract: This paper deals with the problem of computing, in an online fashion, a maximum benefit multi-commodity flow (\ONMCF), where the flow demands are bigger than the edge capacities of the network.

We present an online, deterministic, centralized, "all or nothing", bi-criteria algorithm \alg. The competitive ratio of the algorithm is constant. The algorithm augments the capacities by a logarithmic factor.

A new technique presented in this paper is that the online algorithm invokes a \emph{tri-criteria} oracle. The algorithm uses the primal-dual scheme of Buchbinder and Naor \cite{BN06,BN09,BNsurvey} for online algorithms and is based on an extension of the oracle to a tri-criteria oracle.

The techniques in this paper can be applied to general packing problems, whenever a tri-criteria oracle exists.

at January 25, 2012 01:40 AM UTC

Gaming is a hard job, but someone has to do it!

from arXiv.org: Computational complexity

Authors: Giovanni Viglietta
Download: PDF
Abstract: We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collecting items, doors activated by switches or pressure plates, etc.. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.

at January 25, 2012 01:40 AM UTC

Universal Meshes: A new paradigm for computing with nonconforming triangulations

from arXiv.org: Computational geometry

Authors: Ramsharan Rangarajan, Adrian J. Lew
Download: PDF
Abstract: We describe a method for discretizing planar C2-regular domains immersed in non-conforming triangulations. The method consists in constructing mappings from triangles in a background mesh to curvilinear ones that conform exactly to the immersed domain. Constructing such a map relies on a novel way of parameterizing the immersed boundary over a collection of nearby edges with its closest point projection. By interpolating the mappings to curvilinear triangles at select points, we recover isoparametric mappings for the immersed domain defined over the background mesh. Indeed, interpolating the constructed mappings just at the vertices of the background mesh yields a fast meshing algorithm that involves only perturbing a few vertices near the boundary.

For the discretization of a curved domain to be robust, we have to impose restrictions on the background mesh. Conversely, these restrictions define a family of domains that can be discretized with a given background mesh. We then say that the background mesh is a universal mesh for such a family of domains. The notion of universal meshes is particularly useful in free/moving boundary problems because the same background mesh can serve as the universal mesh for the evolving domain for time intervals that are independent of the time step. Hence it facilitates a framework for finite element calculations over evolving domains while using a fixed background mesh. Furthermore, since the evolving geometry can be approximated with any desired order, numerical solutions can be computed with high-order accuracy. We demonstrate these ideas with various numerical examples.

at January 25, 2012 01:40 AM UTC

I Like Her more than You: Self-determined Communities

from arXiv.org: Data structures and Algorithms

Authors: Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, Shang-Hua Teng
Download: PDF
Abstract: In this paper we define what we call an affinity system, which is a set of individuals, each with a vector characterizing its preference for all other individuals in the set. The preference of a member can be given either by a ranking of all members or by a weighted vector that defines the degrees of its affinity to others. Affinity systems are useful for modeling social systems as well as general data sets, as social interactions are often determined by affinities among the members. We also define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are "self-determined" or "self-certified" by the affinity system. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. Moreover, we present a polynomial-time algorithm for enumerating these communities, as well as a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community.

Our analysis also sheds light on the ({\alpha}, {\beta})-clusters introduced by Mishra, Schreiber, Stanton, and Tarjan [21, 22] for analyzing social networks. We prove that there exists a family of networks with superpolynomial number of ({\alpha}, {\beta})-clusters. We also show that under the assumption that the planted clique problem is hard, even finding an ({\alpha}, {\beta})-cluster is computational hard. In contrast, we show that self-determined communities of a social network can be enumerated in polynomial time.

at January 25, 2012 01:40 AM UTC

Report from SODA 2012: Part 1

from Noam Nisan

Guest post by Hu Fu.

SODA took place in the charming city of Kyoto. The conference was well attended and was meticulously organized, as so many things in Japan are. The hotel was located right in Higashiyama (east hill), with a few major attractions in walking distance. A walk around the area quickly brings one to the most serene other world of temples and gardens.

The afternoon of the second day was packed with two game theory sessions. Here I’m going to report from the first one on mechanism design, and my colleague Ashwinkumar Badanidiyuru will cover the second session.

Berthold Vöcking started the first session with a superbly clear presentation of a universally truthful mechanism for multi-unit auctions, which gives a PTAS for social welfare maximization. This answers a question left open by Dobzinski and Dughmi, who showed a by-now well-known truthful-in-expectation FPTAS for the problem and a separation between universal truthfulness and truthfulness-in-expectation in approximation power for a restricted version of multi-unit auctions. Vöcking’s work shows that there is essentially no such separation if one considers general multi-unit auctions. A starting point of the work is the observation from smoothed analysis that the computational problem of social welfare maximization is solvable in expected polynomial time if the valuations are perturbed by some random noise. However, the magnitude of the noise needs to depend on the maximum value, while truthfulness disallows “naive” use of such private data. Two ideas combined to solve the problem. One is a subjective variant of VCG mechanisms, in which different affine maximizers are used for different bidders; the other is the use of consensus estimate functions, which was first introduced in mechanism design by Goldberg and Hartline.

Another talk in the same session by Bach Ha also involves consensus estimates. This work with Jason Hartline gives a 30.5 approximation for revenue maximization in prior-free downward closed environments. Following the approach in Hartline and Yan (EC 11), the benchmark is the revenue of an envy-free mechanism. When applying consensus estimates, this work and the previous talk both face feasibility problems when there is no consensus. Vöcking solved the problem by designing new consensus functions, while Ha and Hartline introduced a cross-checking process.

The second talk in the session was by Balu Sivan on his work with Shuchi Chawla and Jason Hartline on optimal crowdsourcing contests. As pointed out in previous works, crowdsourcing has much similarity with all-pay auctions, but the auctioneer benefits only from the highest payment. Sivan first shows that the optimal static contest lets the winner take all bonus. For contests that are allowed to set up concrete rules after seeing the bids, the optimal contest is shown to be a “virtual valuation” maximizer.

Our Cornell colleague Vasilis Syrgkanis talked about his work with Renato Paes Leme and Eva Tardos on sequential auctions. In combinatorial auctions, much work has been done on simultaneous auctions for each item, and this work shows that if these auctions are run sequentially and the bidders are foreseeing what’s going to happen later, then sequential auctions behave quite differently and may have very good properties. Two such examples from the talk: pure subgame perfect Nash equilibrium always exists for sequential first price auctions, and in a matroid setting such an auction implements exactly the VCG outcome at equilibrium.

Chaitanya Swamy‘s talk concludes the session on mechanism design. In his work with Konstantinos Georgiou, Swamy gives black-box reductions that essentially reduce strategyproof cost-sharing mechanism design problems to the algorithmic problem of social welfare minimization, with a logarithmic loss in the approximation ratio. The reduction comprises of two reductions, taking as bridge the problem of truthful mechanism design with a slight technical constraint. As is true for black-box reductions in general, this reduction finds applications in a variety of problems.

Besides the main game theory sessions, there were other talks on topics that have economics applications, two of which took place towards the very end of the conference in an on-line algorithm session. Vahab Mirrokni talked about his work on on-line matching with Shayan Oveis Gharan and Morteza Zadimoghaddam. They aim at algorithms which perform well in both the adversarial model and the random arrival model. For unweighted matchings, they showed that the existing algorithm Balance achieves optimal competitive ratios in both models, while for weighted matching this is not possible, though the algorithm in the classic Mehta-Saberi-Vazirani-Vazirani paper was shown to be 0.76-competitive in the random arrival model. In the last talk of the conference, Sourav Chakraborty presented his result with Oded Lachish, which was the first improvement on the competitive ratio for general matroid secretary problem since the problem was posed in 2007 by Babaioff, Immorlica and Kleinberg. Chakraborty and Lachish improved the ratio from O(log ρ) to O(√log ρ), where ρ is the rank of the matroid. The appealing question whether there is O(1)-competitive algorithm is left open.

by robertkleinberg at January 24, 2012 03:28 PM UTC

Ode To The Math Monthly

from Richard Lipton

Some fun results on matrices

Olga Taussky-Todd was one of the leading experts on all things related to matrix and linear algebra in the middle and late 1900′s. She was born in the Austro-Hungarian Empire in what is now the Czech Republic, and obtained her doctorate in Vienna in 1930. She attended the Vienna Circle while fellow student Kurt Gödel was proving his greatest results, and recalled that Gödel was very much in demand for help with mathematical problems of all kinds. She left Austria in 1934, worked a year at Bryn Mawr near Philadelphia, then held appointments at the universities of Cambridge and London until after World War II, when she and her husband John Todd emigrated to America.

Today I want to present a couple of simple, but very cool results about matrices.

Taussky-Todd once said in the American Mathematical Monthly—from now on the Monthly:

I did not look for matrix theory. It somehow looked for me.

That is to say, her doctorate was on algebraic number theory, and then she progressed to functional analysis. Heading in the direction of continuous mathematics was the available path. According to these biographical notes, the field of matrix theory did not really exist at the time. The notes hint that matrix theory was too light to be a main subject for graduate education unto itself, so perhaps the Monthly was a needed vehicle to help to launch it.

Matrix and Monthly

One of Taussky-Todd’s great papers is “A recurring theorem in determinants,” which proved a variety of simple, but fundamental, theorems about matrices. It appeared, as did many of her papers, in the Monthly. One of these theorems is a famous non-singularity condition:

Theorem: Let ${A}$ be a complex ${n \times n}$ matrix, and let ${A_{i}}$ stand for the sum of the absolute values of the non-diagonal elements in row ${i}$ , namely
$\displaystyle A_{i} = \sum_{j \neq i} |a_{ij}|, \ \ i=1,\dots,n.$

If ${A}$ is diagonally dominant, meaning.
$\displaystyle |a_{ii}| > A_{i}, \ \ i=1,\dots,n,$

then
$\displaystyle \det(A) \neq 0.$

I recall as a student “meeting” Taussky-Todd’s work in a book on algebraic number theory. Somehow many of the results in that area could be reconstructed as theorems on matrices, and the resulting proofs sometimes were much more transparent.

Ivars Peterson has a nice discussion of her work here. The same biographical notes referenced above have this revealing passage:

Olga Taussky always wished to ease the way of younger women in mathematics, and was sorry not to have more to work with. She said so, and she showed it in her life. Marjorie Senechal recalls giving a paper at an AMS meeting for the first time in 1962, and feeling quite alone and far from home. Olga turned the whole experience into a pleasant one by coming up to Marjorie, all smiles introducing herself, and saying, “It’s so nice to have another woman here! Welcome to mathematics!”

Let’s look at two simple but I believe interesting results about matrices. One is from the Monthly, and perhaps Olga would appreciate them.

A Matrix Result

Consider the two matrices ${A}$ and ${B}$ over the integers:

$\displaystyle A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \text{ and } B = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}.$

The question is it possible for a sequence of ${A}$ ‘s and ${B}$ ‘s to equal another distinct sequence of ${A}$ ‘s and ${B}$ ‘s? For example, is:

$\displaystyle ABABBBABBABBAAA = BAAABBAABBBA \ ?$

The answer is ${\bf no}$ , and see the next paragraph for the cool proof. One way to think about this is that the two matrices generate the free semigroup. There are pairs of matrices that generate the free group, but the proof that they do that is harder, in my opinion. I once used that the free group is generated by matrices to solve an open problem—see here. What is cool is that the proof is quite unexpected.

$\displaystyle \S$

The key is to look at the action of the matrices on positive vectors: the vector ${v}$ is positive provided

$\displaystyle v = \begin{bmatrix} x \\ y \end{bmatrix}$

where ${x > 0}$ and ${y > 0}$ . Note that both ${A}$ and ${B}$ map positive vectors to positive vectors.

Also define ${\mathsf{TOP}}$ to be those vectors whose first coordinate is strictly larger than its second and define ${\mathsf{BOT}}$ to be those whose second coordinate is strictly larger than its first. Thus,

$\displaystyle \begin{bmatrix} 11 \\ 9 \end{bmatrix} \in \mathsf{TOP} \text{ and } \begin{bmatrix} 4 \\ 23 \end{bmatrix} \in \mathsf{BOT}.$

Let ${S}$ and ${T}$ be distinct sequences of the matrices ${A}$ and ${B}$ that are equal: we plan to show that ${S = T}$ . If they both start with the same matrix, since the matrices are invertible, we can find shorter such sequences. Thus, we can assume that ${S = AS'}$ and ${T=BT'}$ for some ${S'}$ and ${T'}$ . Let ${v}$ be any positive vector. Define

$\displaystyle x = S'v \quad\text{ and }\quad y = T'v.$

It follows that both vectors ${x}$ and ${y}$ are positive. But we note that ${Ax}$ is in ${\mathsf{TOP}}$ and ${By}$ is in ${\mathsf{BOT}}$ , which is impossible since ${Ax = By}$ by assumption.

This neat argument is due to Reiner Martin answering a question in the Monthly—the question was raised by Christopher Hillar and Lionel Levine.

Another Matrix Result

There are many normal forms for matrices of all kinds. I recently ran into the following question, which was quickly solved by Mikael de la Salle. Let ${M}$ be an ${n \times n}$ matrix. Prove that there is a ${\lambda>0}$ and two unitary matrices ${U}$ and ${V}$ so that

$\displaystyle \lambda M = (U + V)/2.$

This says that any matrix, up to scaling, is the average of two unitary matrices. It seems this should be a useful fact, but I have not applied it yet.

$\displaystyle \S$

We can find unitary matrices ${U}$ and ${V}$ and a real diagonal matrix ${D}$ so that

$\displaystyle M = UDV.$

This is the famous Singular Value Decomposition. We can assume that the values on the diagonal are all at most ${1}$ in absolute value, by using ${\lambda}$ to re-scale ${M}$ if needed. The key is that

$\displaystyle D = D^{(1)} + D^{(2)},$

where each ${D^{(1)}}$ and ${D^{(2)}}$ are unitary. This insight is based on the fact that if ${ |r| \le 1}$ for a real ${r}$ , then there is a real ${s}$ so that

$\displaystyle r = (z + \bar{z})/2,$

where ${z = r + is}$ has absolute value ${1}$ . This follows since there is a real ${s}$ so that ${r^{2} + s^{2} = 1}$ . We can now use this term-by-term on the diagonal of ${D}$ to construct the diagonal matrices ${D^{(1)}}$ and ${D^{(2)}}$ . Then it follows that

$\displaystyle M = (UD^{(1)}V + UD^{(2)}V)/2.$

Open Problems

Which matrices are averages—or sums—-of some given fixed number of unitary matrices? With ${\lambda = 1}$ , that is. Is there a good way to characterize them?

Do you have your own favorite matrix results that have a simple proof, but may not be well known to all? If so please share them with all of us.

Finally, I would suggest that you read the Monthly regularly, since it is filled with gems.

by rjlipton at January 24, 2012 12:45 PM UTC

TR12-006 | Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise | Gregory Valiant

from ECCC papers

Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< d n^{1.8} \cdot poly(\frac{1}{\rho}),$ where $\omega<2.4$ is the exponent of matrix multiplication. This is the first subquadratic-time algorithm for this problem with polynomial dependence on $\frac{1}{\rho},$ and improves upon $O(d n^{2-O(\rho)}),$ given by Paturi et al., the `Locality Sensitive Hashing' approach of Gionis et al., and the `Bucketing Codes' approach of Dubiner. This basic algorithm also applies to the adversarial setting, and extensions of this algorithm yield improved algorithms for several other problems, including learning sparse parities with noise, and learning juntas with noise.

at January 24, 2012 04:37 AM UTC

A PSPACE-Complete First Order Fragment of Computability Logic

from arXiv.org: Computational complexity

Authors: Matthew S. Bauer
Download: PDF
Abstract: In a recently launched research program for developing logic as a formal theory of (interactive) computability, several very interesting logics have been introduced and axiomatized. These fragments of the larger Computability Logic aim not only to describe "what" can be computed, but also provide a mechanism for extracting computational algorithms from proofs. Among the most expressive and fundamental of these is CL4, known to be (constructively) sound and complete with respect to the underlying computational semantics. Furthermore, the fragment of CL4 not containing blind quantifiers was shown to be decidable in polynomial space. The present work extends this result and proves that this fragment is, in fact, PSPACE-complete.

at January 24, 2012 01:40 AM UTC

Matroid Prophet Inequalities

from arXiv.org: Data structures and Algorithms

Authors: Robert Kleinberg, S. Matthew Weinberg
Download: PDF
Abstract: Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of p matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most O(p), and this factor is also tight.

Beyond their interest as theorems about pure online algorithms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate Bayesian optimal mechanisms in both single-parameter and multi-parameter settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.

at January 24, 2012 01:40 AM UTC

Is Turing's Thesis the Consequence of a More General Physical Principle?

from arXiv.org: Computational complexity

Authors: Matthew P. Szudzik
Download: PDF
Abstract: We discuss historical attempts to formulate a physical hypothesis from which Turing's thesis may be derived, and also discuss some related attempts to establish the computability of mathematical models in physics. We show that these attempts are all related to a single, unified hypothesis.

at January 24, 2012 01:40 AM UTC

An efficient parallel algorithm for the longest path problem in meshes

from arXiv.org: Data structures and Algorithms

Authors: Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri
Download: PDF
Abstract: In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. This algorithm can be considered as an improvement of [13]. Then based on this sequential algorithm, we present a constant-time parallel algorithm for the problem which can be run on every parallel machine.

at January 24, 2012 01:40 AM UTC

Halting Poetry

from Sariel Har-Peled

For people that believe only in things they can sing: The halting theorem proof as a poem.

by Sariel at January 23, 2012 08:19 PM UTC

Is the British government hiring Italian political consultant?

from Luca Trevisan

David Willetts, the British minister for higher education, has recently announced that the government was “inviting proposals for a new type of university with a focus on science and technology and on postgraduates.” The NYT article on the matter may be biased, but it looks like this announcement could have come from the Italian ministry of university and research, and I mean it as an offense.

So, how much will the government invest in this new university? “There will be no additional government funding,” Mr. Willetss says, and all the funding will have to come from the private sector. And what is the government’s vision and plan for this new university? Mr. Willetts says that “We are not intending to issue any guidelines. We want people to come to us with ideas.”

So the idea of the minister for higher education is that the private sector comes up with all the funding and all the planning for a new university. (Imagine the home secretary stating the goal of increasing the police force, but all the new police force would be paid for by the private sector, which, after all, has an interest in reducing street crime, and that it is not the intention of the home office to dictate how this private police force should operate.) This is exactly what an Italian minister would talk about at a press conference, only to be forgotten the following week.

The reaction from the academia, however, is different. In Italy, you would see people throw their hands in the air and say “madonna mia, in mano a chi siamo,” while the British are masters of understatement.

“We at Oxford feel that keeping the U.K. a world leader in science and research is a very important objective,” Ian Walmsley, Oxford’s chief research officer, “and we’re pleased that the government agrees with that.”

Stephen Caddick, for the University College at London says the proposal is “not uninteresting”.

by luca at January 23, 2012 04:38 PM UTC

What should we do?

from Computational Complexity

Time for a post by tweet request.

Is a wave of action against big publishers' practices brewing?gowers.wordpress.com/2012/01/21/els…thecostofknowledge.com Should CS do more? @fortnow
— Tugkan Batu (@tugkanbatu) January 22, 2012

Quite a lot on the Internets on Tim Gowers' promise not to work with Elsevier anymore. I'm not as anti-Elsevier as Gowers or many of my readers but I understand the frustrations.

It's easy to make a promise not to publish, edit or referee papers, especially when you don't need to improve your academic reputation. Still a mathematician of his magnitude really puts a spotlight on that publisher.

Because of the Elsevier stigma we've had for several years, all the theoretical CS journals of Elsevier are not nearly as strong as they have been in the past. So you don't accomplish much more just by boycotting Elsevier.

Making a difference means what you do, not what you don't do. Be sure and support journals that are worthy of support by submitting and refereeing papers and serving on editorial boards. The best attack on publishers that you don't like is to have several strong alternatives. The best way to make them strong is by having your support.

No journals is completely free of cost, they require money or time. Open access journals without page charges generally have no revenue stream and require effort to make to publish the journal. For these journals you can volunteer your time as well as submitting, refereeing and editing.

Remember it's easy to complain and say what you won't do but it is what you do do that makes the difference.

Subscribe to comments |

Post a comment

by Lance Fortnow (noreply@blogger.com) at January 23, 2012 02:31 PM UTC

Ladner's Theorem vs. Schaefer's Theorem

from CS Theory StackExchange (Q&A)

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, googling and wikipeding, I came across Ladner's Theorem:

Ladner's Theorem: If ${\bf P} \ne {\bf NP}$, then there are problems in ${\bf NP} \setminus {\bf P}$ that are not ${\bf NP}$-complete.

and to Schaefer's theorem:

Schaefer's Dichotomy Theorem: For every constraint language $\ \Gamma $ over $\{0, 1\}$, if $\ \Gamma $ is Schaefer then ${\bf CSP}(\Gamma)$ is polynomial time solvable. Otherwise, ${\bf CSP}(\Gamma)$ is ${\bf NP}$-complete.

I read this to mean that, by Ladner's, there are problems that are neither ${\bf P}$ nor ${\bf NP}$-complete, but by Schaefer's, problems are either ${\bf P}$ and ${\bf NP}$-complete only.

What am I missing? Why don't these two results contradict each other?

I took the condensed version of the above theorem statements from here. In his "Final Comments" section, he says "Thus, if a problem is in ${\bf NP} \setminus {\bf P}$ but it is not ${\bf NP}$-complete then it can not be formulated as CSP".

Does this mean ${\bf SAT}$ problems miss some instances that are in ${\bf NP}$? How is that possible?

by user834 at January 23, 2012 09:59 AM UTC

On groups that have normal forms computable in logspace

from arXiv.org: Computational complexity

Authors: Murray Elder, Gillian Elston, Gretchen Ostheimer
Download: PDF
Abstract: We consider the class of finitely generated groups which have a normal form computable in logspace. We prove that the class of such groups is closed under finite extensions, finite index subgroups, direct products, wreath products, and also certain free products, and includes the solvable Baumslag-Solitar groups, as well as non-residually finite (and hence non-linear) examples. We define a group to be logspace embeddable if it embeds in a group with normal forms computable in logspace. We prove that finitely generated nilpotent groups are logspace embeddable. It follows that all groups of polynomial growth are logspace embeddable.

at January 23, 2012 01:40 AM UTC

On the intrinsic complexity of elimination problems in effective Algebraic Geometry

from arXiv.org: Computational complexity

Authors: Joos Heintz, Bart Kuijpers, Andres Rojas Paredes
Download: PDF
Abstract: The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.

at January 23, 2012 01:40 AM UTC

A simple D^2-sampling based PTAS for k-means and other Clustering Problems

from arXiv.org: Data structures and Algorithms

Authors: Ragesh Jaiswal, Amit Kumar, Sandeep Sen
Download: PDF
Abstract: Given a set of points $P \subset \mathbb{R}^d$, the $k$-means clustering problem is to find a set of $k$ {\em centers} $C = \{c_1,...,c_k\}, c_i \in \mathbb{R}^d,$ such that the objective function $\sum_{x \in P} d(x,C)^2$, where $d(x,C)$ denotes the distance between $x$ and the closest center in $C$, is minimized. This is one of the most prominent objective functions that have been studied with respect to clustering.

$D^2$-sampling \cite{ArthurV07} is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points $P \subseteq \mathbb{R}^d$, the first point is chosen uniformly at random from $P$. Subsequently, a point from $P$ is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled points.

$D^2$-sampling has been shown to have nice properties with respect to the $k$-means clustering problem. Arthur and Vassilvitskii \cite{ArthurV07} show that $k$ points chosen as centers from $P$ using $D^2$-sampling gives an $O(\log{k})$ approximation in expectation. Ailon et. al. \cite{AJMonteleoni09} and Aggarwal et. al. \cite{AggarwalDK09} extended results of \cite{ArthurV07} to show that $O(k)$ points chosen as centers using $D^2$-sampling give $O(1)$ approximation to the $k$-means objective function with high probability. In this paper, we further demonstrate the power of $D^2$-sampling by giving a simple randomized $(1 + \epsilon)$-approximation algorithm that uses the $D^2$-sampling in its core.

at January 23, 2012 01:41 AM UTC

Blogs/feeds

Theory of Computing Blog Aggregator

Matrix and Monthly

A Matrix Result

Another Matrix Result

Open Problems