Theory of Computing Blog Aggregator

Ways Scott could have gotten his question answered

In a blog entry of Scott Aaronson's he asks an interesting question (he often does!) about boy-meets-girl type fiction- both film and literature. Later in comment 20 he asks another interesting question (he often has interesting questions in his comments!):

How could I have gotten efficient answers to my question other than blogging it. I don't know of any existing way to search books and movies by plot-structure other than by querying the the humans who've read or watched them. (Then again, this is probably not a common want.)

Rather than be comment 90 on Scotts blog, I share my thoughts on this question here.

Scotts audience is, I assume, mostly CS/Math/Phy people. Not clear if thats really a good target group to ask about literature and film.
Is there some other blog which does have the audience helpful to Scott? I honestly don't know, but that is one answer: Find someone who has a blog with a more appropriate audience and ask to guest blog. (And in exchange that blogger can guest blog on Scott's blog and ask about Quantum Complexity.)
There used to be READNEWS GROUPS (actually there still are) where there is no head person who controls it, people just post stuff. They are not used so much anymore, but Scott could try to post on an appropriate one. (NOTE: thats how I got some of my Bob Dylan satires, by posting a request to rec.music.dementia)
i> Find an expert. I wonder if Google or Google++ or whatever will ever replace asking someone who knows stuff. Scott should just ask Roger Ebert about film. Perhaps for money. Or they could barter since Roger Ebert has always wanted to know about Perfect Completness for QMA. Actually Ebert does have on his webpage a place for people to ask questions; however Scotts question is more complex than the usual How come you recommended movie X when it sucked?-type questions.
Are there already experts on the web who will answer questions, either for free or for money or for barter?

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at August 20, 2008 04:00 PM UTC

NSF Expeditions, Complexity

from My Biased Coin

I'm glad to hear of the news that Sanjeev Arora's team at Princeton was one of the winners for the NSF Expeditions grants, working on the general theme of complexity. I think it shows that some of the public relations work our community has been doing, especially with the NSF, is paying off in concrete ways. I also think that more money for theory generally just has to be a good thing -- it's $10 million more for theory than there was before.

That being said, I'll express two concerns:

1) It's odd to see so much money for theory concentrated into such a small geographic area. I realize that was the nature of the Expeditions program, and I don't fault the proposal for it. It just strikes me as strange when the general budget for CS theory is so small to earmark such a large sum of money to this project. It feels like an over-concentration of resources in what's already a small community.

The solution to this, of course, is to get more money for the general CS theory program. And I'm sure a significant chunk of the Expeditions money will go to open DIMACS-style collaborations like workshops and other events, minimizing this concern.

2) I know it's just the nature of theory, but reading over the blurbs about the various funded Expeditions proposals, I can't help but notice that while the others seem to have some sort of statement of clear goals to take things in new directions ("hope to create a new field of computational sustainability", "It aims to create an "open" alternative to mobile ubiquitous computing and communication that can spur innovations, which will have a dramatic impact on the choices users will have in the way their data and information is computed, stored and communicated", "The project aims to develop tools and theories for molecular programming--such as programming languages and compilers--that will enable systematic design and implementation of technological and biotechnological applications that require information processing and decision-making to be embedded within and carried out by chemical processes."), the complexity grant will "hope to better understand the boundary between the tractable and the intractable" and "attack some of the deepest and hardest problems in computer science". Doesn't that sound, I don't know, just like business as usual? My concern is that it's probably important to the theory community long-term for this Expedition to have some major concrete success attributed to it at the end of the day. I have no doubt that good things will come out of this, just based on the people, who already do good work -- but will the output be the sort of things that in retrospect justify this investment?

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at August 20, 2008 03:04 PM UTC

Two Very Early Problems, a Simple Solution, and a New Problem

from Gil Kalai

As an undergraduate student whenever I studied some subject I tried to come up with problems. Many of these problems were artificial or silly and, of course, I forgot most of them. But a few still make sense. Here are two problems:

1) Let B be the unit ball (or the unit cube) in $R^d$ . Does every function from B to B which is the differential of a real function on B have a fixed point?

2) Is there a common generalization for Sylows’s theorem and Frobenius’ theorem?

1) A fixed point theorem for differentials?

One of the delightful theorems you learn in the first year of undergraduate studies (and later teach as a TA, and later teach as a professor) is the intermediate value theorem. If a continuous function satisfies $f(a)<0$ and $f(b) >0$ then for some point c in the interval [a,b], $f(c)=0$ . Later you learn Darboux’s theorem asserting that if f is a differential function, and $f'(a)<0$ and $f'(b) >0$ then for some point c in the interval [a,b], $f'(c)=0$ . Your first reaction is: “Of course, $f'(x)$ is continuous and we can apply the intermediate value theorem.” But, no, you soon learn some subtle examples where the derivative is not continuous!

One equivalent formulation of the intemediate value theorem asserts that every continuous map from [0,1] to itself has a fixed point. Namely, for some $x \in [0,1]$ , $f(x)=x$ . This is a special case of Brouwer’s fixed point Theorem (which you learn in the second year) which asserts that every map from the unit ball of $R^n$ to itself has a fixed point.

We can ask if every function from the unit ball to itself, which is a differential of a real function on the unit ball, has a fixed point.

There are many very interesting and difficult problems related to basic real analysis. Not many mathematicians are fully aware of the rich and beautiful modern results in real analysis. (Just like many people outside mathematics are not aware that there is more to be discovered in mathematics itself.)

For example, it has only recently been proved by Csörnyei, O’neil, and Preiss and by Elekes, Keleti, and Prokaj, that the composition of derivatives of differential functions has the fixed point property. This is not easy at all. Also, the question regarding connectivity of the graph of differentials of functions was studied extensively. See this paper by Csörnyei and Holický

In Budapest, I mentioned this problem to Miklos Laczkovich. (His UCL home page mentions a few open problems in real analysis.) He asked Marton Elekes (an author of one of the papers I mentioned above, and the son of György Elekes whom we mentioned in connection to product sum theorems). Elekes found a simple proof that the answer is yes - there is always a fixed point . Suppose you want to prove it for a function f(x,y) whose derivative maps the unit square into itself. What you need to do is to inspect the behavior of $f - x^2/2 - y^2/2$ in the boundary of the square.

So this problem was not so good, but the following problem proposed by Laczkovich might be.

Problem: Let X be a set homeomorphic to the unit ball in $R^d$ . Does every function from X to X which is the differential of a real function on X have a fixed point?

2) Joining Frobenius’ and Sylow’ theorems

Sylow’s theorems in group theory, which we studied in the second year of undergraduate studies, always seemed to me as one of the few theorems I did not have a conceptual understanding of. This makes Sylow’s theorems rather mysterious and charming. (A similar impression with the opposite reaction is expressed by Tim Gowers in this interesting post.)

Sylow’s theorem (one of them) asserts: In a group whose order is divisible by $p^i$ there are 1(mod p) subgroups of order $p^i$ .

Frobenius’ theorem asserts: In a group whose order is divisible n, the number of solutions to the equation $x^n=1$ is zero modulo n.

(Thanks, Lior.) (Frobenius was probably inspired by Sylow.)

Sylow intersection with Frobenius: The case i=1 of Sylow’s theorem is the same as the case n=p of Frobenius’ theorem.

Is there a nice (Sylow JOIN with Frobenius) theorem? The case i=2 of Sylow’s theorem is the place to start.

by Gil Kalai at August 20, 2008 02:55 AM UTC

Color these points

from Vanity of Vanities, all is Vanity

Given a set P of n points in the plane (hallelujah!) color them by black and white (or by gold and lavender if your taste is more tacky), so that if a line has more than, say, 50, points on one side of it, then this side contains at least one white point and at least one black point.

Talking points:

This problem is not easy but not too hard. It is taken from some paper. I have my own solution, but its not as elementary as the original solution.
50 is just a convenient constant to talk about. I think 4 or 8 is possible, but if you can do it with any constant thats good.
This problem has interesting connections to discrepancy and similar stuff.
The 3d version is harder (points and planes) - I dont know its status.

by Sariel at August 19, 2008 06:59 PM UTC

Acknowledging anonymous blog comments

from Computational Complexity

Twice times now I have gotten an anonymous comment on this blog that I may want to use in either a paper or my (never-ending) web-monograph on VDW stuff. They are

Anonymous posted a combinatorial proof of a summation. See comment 6.
Former VDW ugrad posted that the exact bound of polyvdw(x2,3)=29. See comment 11. I asked the obvious people, and they all deny they posted it.

If I use these proofs then I will reference the blog link (how long these links last?) and also give the full proof. I would also like to acknowledge the people who came up with those proofs. How to do this

I would like to thank Anonymous ....

and

I would like to thank Former VDW ugrad...

do not seem like I am really giving them credit. So, what to do? I make the following request:

If you are one of the two people above please email me who you are and which entry you posted.

Will this work? There are two concerns.

That nobody will respond.
That too many people will respond. How do they verify who they are?

Will this be a bigger problem in the future? If so then future textbooks may have

P vs NP was resolved by kittykat17.

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at August 19, 2008 03:59 PM UTC

Book by FemaleScienceProfessor

from My Biased Coin

I'm an occasional reader of the blog FemaleScienceProfessor. Often the blog is just about being a science professor, which is interesting, and I can relate to. And sometimes the blog is specifically about being a female science professor, which is also interesting, even if I relate to it less.

Well, FSP has re-worked past blog entries into an on-line book available at lulu.com. I haven't yet bought and downloaded it yet, but from the Table of Contents, it appears to be a particularly worthwhile book for graduate students thinking about a life in academia, and for new faculty. The bulk of the book seems gender-neutral, if that's a concern. I thought I'd give it a free plug.

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at August 19, 2008 07:44 AM UTC

$10 million for complexity theory...

from The Geomblog

Via His Quantum Holiness, news comes of the NSF Expeditions awards: each award is $10 million, and four were given out. One of them was for complexity theory, and the team is a star-studded list of complexity and algorithms folks, led by Sanjeev Arora. Here's the blurb:

In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics

Congratulations ! For getting the award, and demonstrating that hard-core complexity theory CAN get funded...

Subscribe to comments |

Post a comment

by Suresh (noreply@blogger.com) at August 19, 2008 03:39 AM UTC

On NFAs Where All States are Final, Initial, or Both

from arXiv.org: Computational complexity

Authors: Jui-Yi Kao, Andrew Malton, Narad Rampersad, Jeffrey Shallit
Download: PDF
Abstract: We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problem for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.

at August 19, 2008 03:40 AM UTC

Better Bounds for Frequency Moments in Random-Order Streams

from arXiv.org: Data structures and Algorithms

Authors: Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy
Download: PDF
Abstract: Estimating frequency moments of data streams is a very well studied problem and tight bounds are known on the amount of space that is necessary and sufficient when the stream is adversarially ordered. Recently, motivated by various practical considerations and applications in learning and statistics, there has been growing interest into studying streams that are randomly ordered. In the paper we improve the previous lower bounds on the space required to estimate the frequency moments of a randomly ordered streams.

at August 19, 2008 03:41 AM UTC

Every Computably Enumerable Random Real Is Provably Computably Enumerable Random

from arXiv.org: Computational complexity

Authors: Cristian S. Calude , Nicholas J. Hay
Download: PDF
Abstract: We prove that every computably enumerable (c.e.) random real is provable in Peano Arithmetic (PA) to be c.e. random, a statement communicated to one author by B. Solovay. A major step in the proof is to show that the theorem stating that "a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine" can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem.

The result that every c.e. random real is provably c.e. random is in contrast with the case of computable functions, where not every computable function is provably computable. It is even more interesting to compare this result with the fact that--in general--random finite strings are not provably random.

The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as an automatic proof of this theorem written with the interactive theorem prover Isabelle.

at August 19, 2008 03:40 AM UTC

Amihood Amir more famous than Dick Cheney

from Computational Complexity

(Guest post by Richard Beigel.)

Top-9 list of internet fame criteria. You know you are famous when ...

*It was hard deciding which of these two should come first, but Richard Stallman shows up under both and, surprisingly, Don E. Knuth doesn't show up under 2.

Disclaimer: These criteria are intended for the purpose of humor only. They do not represent the opininion of the Natiοnal Science Fοundation or the the Federal Gοvernment, and they will not affect your chances of getting a grant. ~

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at August 18, 2008 03:33 PM UTC

SIGCOMM 2008, Part 3

from My Biased Coin

Here are a few more papers from SIGCOMM which should be of particular interest to a more theoretical audience. (Generally, SIGCOMM papers are interesting -- but again, I'm focusing here on papers that I think might be of special interest to theory people. It strikes me that I should, at some point, similarly summarize papers from a major theory conference -- like STOC 2009 -- that would be of special interest to networking people. Of course, SIGCOMM makes that easier, posting abstracts and all the papers online...)

There's a paper on analyzing BitTorrent in the game-theoretic incentive-style analysis sense. It will require a more careful reading from me, as I'm not a full-fledged game-theory/CS type researcher, but it sure looks interesting on the first perusal. I'm naturally biased to the idea that if all this current effort on game theory that is going on in computer science (and particularly in theory) is to have payoff, real-world protocols must be considered and analyzed. So in that sense, this should be a really interesting paper.

While it doesn't appear particularly theoretical (it looks like what I like to joke is a standard networking paper -- lots of pictures and tables, no equations...) this paper on spamming botnets from Microsoft includes Rina Panigrahy (well known for his work in both theory and practice) as one of the co-authors. (I figure Rina had something to do with where I saw the words "entropy reduction", but that's just a guess...)

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at August 18, 2008 01:18 AM UTC

Surprising Math

from Gil Kalai

1. A pleasant surprise

When I worked on the diameter problem for d-polytopes with n facets. I was aiming to prove an upper bound of the form $n^{\log d}$ but my proof only gave $d^{\log n},$

It was a pleasant surprise to note that $n^{\log d}=d^{\log n}$ .

2. A bigger surprise

A few weeks ago James Lee gave a talk and proved a bound of the form $(\log n)^{\log \log \log n}.$ I was surprised to learn from him that $(\log n)^{\log \log \log n} = ( \log \log n)^{\log \log n} .$

(Update: I got it wrong at first, thanks guys)

This is an even more surprising special case of the formula above.

3. Is it better to have the discount first?

Question: What is a better deal: A store that gives 12% student-discount after it adds a 12% value added tax to the price of the product? Or a store that first adds 12% tax on the entire sum and only then deducts 12% student discount?

Ohh, The way I asked this question the two alternatives are precisely the same. Let me ask it again: What is a better deal: A store that gives 12% student discount after adding a 12% value added tax to the price of the product? Or a store that first deducts the 12% student discount, and only then adds 12% tax on the new price?

Answer: The same, by a surprisingly not obvious special case of commutativity of multiplication.

by Gil Kalai at August 17, 2008 05:21 AM UTC

A fictional gap?

from Shtetl-Optimized

Consider the following template, which (with small variations) might describe a third of the world’s movies and novels:

Girl, the protagonist, is set to marry the well-off, educated Dependable Guy, who does something insufferable for a living such as working. Girl’s parents strongly favor this union.
Girl meets (or re-meets) Dashing Artist Guy, who steals her heart away. In the closing scene, Girl and DAG walk happily into the sunset; Dependable Guy is not shown.

It’s a classic Darwinian tale of female mate selection, pitting the stable, nerdy provider-male against the self-confident lothario—and at least in fiction, the latter appears to win every single contest. Insofar as teenagers are influenced by media at all, I’m guessing this sort of thing has a much larger impact on them than unfortunate public-service billboards.

(Has the popularity of the Girl-Picks-DAG story template been constant at least since Shakespeare, or did it increase with the sexual revolution? Does it represent, in coded form, the triumph of genetic fitness over parenting ability as a selection criterion—despite what may have been the limited value of artist genes on the ancestral savanna?)

Typically the story’s writers stack the deck in Dashing Artist Guy’s favor by making Dependable Guy some combination of mean, old, lecherous, ugly, humorless, or vengeful, or by making Girl’s marriage to him a forced one. (Think of Cal in Titanic or Lazar Wolf in Fiddler on the Roof.) In the more interesting variants, Dependable Guy might have none of the negative qualities, and Girl might be shown agonizing over a genuine choice—but she still always goes for DAG in the end.

Interestingly, the writers invariably stack the deck further by portraying DAG as 100% committed to Girl—even though a realistic assessment might find that if DAG stole one heart, then he can and will steal plenty of others as well, and thus the notion of Girl and DAG living together happily ever after may simply represent audience members’ wish-fulfillment fantasy. Indeed, skepticism about DAG’s long-term motives might be the reason Girl’s parents favor Dependable Guy.

So here’s my question for you: what examples can you come up with, in any of the world’s fiction, where Girl (the protagonist) chooses Dependable Guy—or at least wishes she did?

2 bonus points if Dependable Guy is portrayed as a nerd (and remains so throughout the story)
5 bonus points if he’s the one Girl’s parents are rooting for
10 bonus points if Girl makes her decision by thinking about the likelihood DAG will stay with her, and concluding it’s not that great

Racking my highly-fallible memory for a few minutes, the closest example I could come up with—and it’s not that close—is Gone With The Wind. Sure, there are comedies about a nerdy guy winning the girl of his dreams, but there the protagonist always seems to be the nerd rather than the girl, and by the end the audience discovers that he isn’t ‘really’ a nerd anyway. Also, they’re comedies.

by Scott at August 16, 2008 05:03 PM UTC

SIGCOMM 2008, Part 2

from My Biased Coin

The Accountable Internet Protocol (AIP) paper asks the question: what if we re-architectured the Internet to start with self-certifying addresses, so that there was a layer of accountability -- you'd know where packets are coming from. This paper clearly fits square in the mold of the NSF FIND program. They suggest what a self-certifying architecture would look like, how routing would work with such an architecture, consider potential attacks on the proposed architecture, and discuss whether technology trends would make such an architecture feasible. Certainly interesting, although I admit to high-level unsubstantiated concerns about the specific address architecture they propose. (I suppose as a "kid" I saw too many key-exchange-style protocol papers where a subtle flaw was exposed by a subsequent paper...)

I notice they used a Bloom filter in the paper without even giving a citation. Have Bloom filters now become so successfully widespread in the networking community that no citation is needed? What a nice thought! (Or maybe the authors just ran out of space for the citation.)

Another SIGCOMM paper continues on the path set out by for example Feigenbaum, Papadimitriou, Sami, and Shenker, on using game theory to study the behavior of BGP. They propose a more realistic model (where, for example, Autonomous Systems can be paid for attracting traffic) which, naturally, leads to more negative results in terms of the truth-telling behavior of ASes. (Why is reality so often disappointing this way?)

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at August 16, 2008 04:08 AM UTC

Useful bibliographic search site of the day

from David Eppstein

Crossref.org. You give it author and title, it gives you other bibliographic details including a DOI (the part I was looking for; basically a more-permanent version of the publisher's official web address for the paper). The link is to their "guest query" page; they also have a different interface for batch queries for registered users, but I think that's not intended for individuals.

at August 16, 2008 01:26 AM UTC

Olympic Markets

from Computational Complexity

What do the Olympics have to do with computational complexity? Not much, so while I have spent much more time watching the games than proving theorems this week I couldn't think of the right way to fit it into the blog. Until I got the following email from David Pennock yesterday.

We implemented Olympics medal count prediction on Yoopick. Since it was your idea, you now have a moral obligation to blog about it, use it, and evangelize it to all your friends. :-)

Where most prediction markets track binary events, like whether the Obama will win the election, the Facebook-plugin Yoopick, developed at Yahoo Research in New York, is a fake-money market that predicts distributions over a range like the number of points scored in a basketball game. I suggested using Yoopick to predict the distribution of medals won by county and now you too can make your predictions and win some Yootles. I hear 100 Yootles and 2 Dollars will get you a subway ride in New York.

In other Prediction Market stuff at Yahoo, Sharad Goel used Amazon's Mechanical Turk to offer 100 people three cents each to predict the probability that Obama will win. The predictions were all over the place but average them up and you get exactly the same value as Intrade. Not the first time we've seen this phenomenon and it seems hard to explain.

And don't forget to check our our Electoral Markets Map. Obama has the slight edge as we get closer to the conventions and start of the real campaign season.

Subscribe to comments |

Post a comment

by Lance (noreply@blogger.com) at August 15, 2008 03:19 PM UTC

SIGCOMM 2008, Part 1

from My Biased Coin

About a year ago, I took a look at some SIGCOMM 2007 papers. I won't be attending SIGCOMM this week, unfortunately, so in the interest of self-education, I thought I'd look at some of the papers this year. (The site currently has the papers up. Wow, what a neat idea...)

Before getting into papers, I thought I'd mention that Don Towsley is being given the ACM SIGCOMM award. This is a great choice, and well deserved. And relevant to this site's audience, Don is, in my mind, primarily a theorist. Not a FOCS/STOC theorist to be sure, but a theorist nonetheless. As the award announcement states:

Towsley, who is Distinguished Professor of Computer Science, has made innovative and pioneering contributions in developing foundational modeling and analysis techniques that have enabled a better understanding of some of the most important aspects of today's computer networks, network protocols and networked applications.

Modeling, analysis, understanding... that's what theory is all about. It's people like Don that made networking an open and understanding place for people like me. Thanks! And hooray for Don!

Now for papers. As before, I'll give brief synopses (at the level of the posted abstracts :) ), as I'm just looking at these papers on the fly. The network coding crowd has attacked again with the MIXIT system, which seems to throw together a bunch of ideas in a clever fashion to improve performance on wireless mesh networks. Recall that the basic working definition of network coding is that intermediate nodes do more than store and forward, they can process the packets as they come through (creating encoded packet variations). Here, the basic unit is not taken to be a packet, but a symbol (a small collection of bits), with symbols being packed into a packet. This allows nodes can "take apart" packets; if a whole packet doesn't come in error-free, the node can take symbols that appear to be right with high enough probability (based on information from the physical layer), and re-package (via linear combinations, a la "standard" network coding) and send on only those symbols. Because erroneous symbols might get through, an end-to-end error-correcting rateless code is also used. All of this appears to improve throughput.

The paper seems interesting -- another proof-of-concept paper for network coding in wireless systems, which is where I suspect network coding will be able to make the most inroads over the next few years. I can't tell yet how practical this really seems (without a more detailed reading), but the idea of taking apart packets and sending only the good pieces in combination with multiple coding techniques seems quite nice.

As an aside, the pdf for this paper seems to contain a picture or something that crashes my poor Mac around the 8th or 9th page. Help!

Subscribe to comments |

Post a comment

by Michael Mitzenmacher (noreply@blogger.com) at August 15, 2008 04:19 AM UTC

Nearly Tight Low Stretch Spanning Trees

from arXiv.org: Data structures and Algorithms

Authors: Ittai Abraham, Yair Bartal, Ofer Neiman
Download: PDF
Abstract: We prove that any graph $G$ with $n$ points has a distribution $\mathcal{T}$ over spanning trees such that for any edge $(u,v)$ the expected stretch $E_{T \sim \mathcal{T}}[d_T(u,v)/d_G(u,v)]$ is bounded by $\tilde{O}(\log n)$. Our result is obtained via a new approach of building ``highways'' between portals and a new strong diameter probabilistic decomposition theorem.

at August 15, 2008 03:40 AM UTC

Decision Problems For Convex Languages

from arXiv.org: Computational complexity

Authors: Janusz Brzozowski, Jeffrey Shallit , Zhi Xu
Download: PDF
Abstract: In this paper we examine decision problems associated with various classes of convex languages, studied by Ang and Brzozowski (under the name "continuous languages''). We show that we can decide whether a given language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but that the problem is PSPACE-hard if L is represented by an NFA. In the case that a regular language is not convex, we prove tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages.

at August 15, 2008 03:40 AM UTC

AI Follows Theory

from Computational Complexity

In one of the 2006 AAAI Outstanding Paper Award Winners Model Counting: A New Strategy for Obtaining Good Bounds, Gomes, Sabharwal and Selman show how to approximately count the number of satisfying assignments of a Boolean formula with a SAT solver. They add random parity constraints ala Valiant-Vazirani and approximate the number of solutions based on the number of constraints needed until the formula is not satisfiable.

Sounds like a neat idea that complexity theorists should have come up with in the 80's. And we did, where by "we" I mean Larry Stockmeyer in his 1985 SICOMP paper On Approximation Algorithms for #P. Stockmeyer uses random hash functions from Sipser but it is essentially the same algorithm and analysis as Gomes et. al.

Stockmeyer wrote a purely theoretical paper. Since then we have better algorithms and much faster computers and one can now solve satisfiability on non-trivial input lengths. Gomes et. al. write the paper as a practical technique to approximate the number of solutions and even implement their algorithm and contrast with other programs that exactly count the number of solutions.

Gomes et. al. mention Toda's paper on the hardness of exact counting but don't cite Stockmeyer or any other paper in the vast theory literature on approximate counting.

We complexity theorists know many other nifty things one can do with an NP oracle such as uniform sampling and learning circuits. Read them now so you don't have to reinvent them later.

Subscribe to comments |

Post a comment

by Lance (noreply@blogger.com) at August 14, 2008 01:58 PM UTC

Transitive-Closure Spanners

from arXiv.org: Data structures and Algorithms

Authors: Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Download: PDF
Abstract: Given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in access control, data structures, and property testing, and properties of these spanners have been rediscovered over the span of 20 years. The main goal in each of these applications is to obtain the sparsest k-TC-spanners. We bring these diverse areas under the unifying framework of TC-spanners.

We initiate the study of approximability of the size of the sparsest k-TC-spanner for a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Theta(log n) unless P = NP. For k>2, we present a polynomial-time algorithm that finds a k-TC-spanner with size within O((n log n)^{1-1/k}) of the optimum. Our algorithmic techniques also yield algorithms with the best-known approximation ratio for well-studied problems on directed spanners when k>3: DIRECTED k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k>=3, we show that the size of the sparsest k-TC-spanner is hard to approximate with 2^{log^{1-eps} n} ratio unless NP \subseteq DTIME(n^{polylog n}}). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log^2 n /eps) queries for any poset whose transitive reduction is an H-minor free digraph, improving the Theta(sqrt(n) log n/eps)-queries required of the tester due to Fischer et al (2002).

at August 14, 2008 12:00 AM UTC

A Very Efficient Scheme for Estimating Entropy of Data Streams Using Compressed Counting

from arXiv.org: Data structures and Algorithms

Authors: Ping Li
Download: PDF
Abstract: Compressed Counting (CC) was recently proposed for approximating the $\alpha$th frequency moments of data streams, for $0<\alpha <= 2$, especially $\alpha\approx 1$. One direct application of CC is to estimate the entropy, which is an important summary statistic in Web/network measurement and often serves a crucial "feature" for data mining. The R\'enyi entropy and the Tsallis entropy are functions of the $\alpha$th frequency moments; and both approach the Shannon entropy as $\alpha-> 1$. Previous studies used the standard algorithm based on {\em symmetric stable random projections} to approximate the $\alpha$th frequency moments and the entropy.

Based on maximally-skewed stable random projections, Compressed Counting (CC) dramatically improves symmetric stable random projections, especially when $\alpha\approx 1$. This study applies CC to estimate the R\'enyi entropy, the Tsallis entropy, and the Shannon entropy. Our experiments on some Web crawl data demonstrate significant improvements over previous studies. When estimating the frequency moments, the R\'enyi entropy, and the Tsallis entropy, the improvements of CC, in terms of accuracy, appear to approach "infinity" as $\alpha\to1$.

When estimating Shannon entropy using R\'enyi entropy or Tsallis entropy, the improvements of CC, in terms of accuracy, are roughly 20- to 50-fold. When estimating the Shannon entropy from R\'enyi entropy, in order to achieve the same accuracy, CC only needs about 1/50 of the samples (storage space), compared to symmetric stable random projections. When estimating the Shannon entropy from Tsallis entropy, however, symmetric stable random projections} can not achieve the same accuracy as CC, even with 500 times more samples.

at August 14, 2008 03:40 AM UTC

The Optimal Quantile Estimator for Compressed Counting

from arXiv.org: Data structures and Algorithms

Authors: Ping Li
Download: PDF
Abstract: Compressed Counting (CC) was recently proposed for very efficiently computing the (approximate) $\alpha$th frequency moments of data streams, where $0<\alpha <= 2$. Several estimators were reported including the geometric mean estimator, the harmonic mean estimator, the optimal power estimator, etc. The geometric mean estimator is particularly interesting for theoretical purposes. For example, when $\alpha -> 1$, the complexity of CC (using the geometric mean estimator) is $O(1/\epsilon)$, breaking the well-known large-deviation bound $O(1/\epsilon^2)$. The case $\alpha\approx 1$ has important applications, for example, computing entropy of data streams.

For practical purposes, this study proposes the optimal quantile estimator. Compared with previous estimators, this estimator is computationally more efficient and is also more accurate when $\alpha> 1$.

at August 14, 2008 03:40 AM UTC

Communication Complexities of XOR functions

from arXiv.org: Computational complexity

Authors: Yaoyun Shi, Zhiqiang Zhang
Download: PDF
Abstract: We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$.

We show that for any such function, (a) the deterministic communication complexity is always $\Theta(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are $\Theta(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$.

at August 14, 2008 03:40 AM UTC

Uniqueness of certain polynomials constant on a hyperplane

from arXiv.org: Computational geometry

Authors: Jiri Lebl, Daniel Lichtblau
Download: PDF
Abstract: Let $p(x,y)$ be a polynomial of degree $d$ with $N$ positive coefficients and no negative coefficients, such that $p=1$ when $x+y=1$. It is known that the sharp estimate $d \leq 2N-3$ holds. In this paper we study the $p$ that minimize $N$ and we give complete classification of these polynomials up to $d=17$ by computational methods. We use a linear algebra approach and a mixed linear programming approach. The question is motivated by a question in CR geometry. In particular, a complete classification of polynomials minimizing $N$ is an important first step in the complete classification of CR maps of spheres in different dimensions.

at August 14, 2008 03:40 AM UTC

Front Propagation with Rejuvenation in Flipping Processes

from arXiv.org: Data structures and Algorithms

Authors: T. Antal, D. ben-Avraham, E. Ben-Naim, P. L. Krapivsky
Download: PDF
Abstract: We study a directed flipping process that underlies the performance of the random edge simplex algorithm. In this stochastic process, which takes place on a one-dimensional lattice whose sites may be either occupied or vacant, occupied sites become vacant at a constant rate and simultaneously cause all sites to the right to change their state. This random process exhibits rich phenomenology. First, there is a front, defined by the position of the left-most occupied site, that propagates at a nontrivial velocity. Second, the front involves a depletion zone with an excess of vacant sites. The total excess D_k increases logarithmically, D_k ~ ln k, with the distance k from the front. Third, the front exhibits rejuvenation -- young fronts are vigorous but old fronts are sluggish. We investigate these phenomena using a quasi-static approximation, direct solutions of small systems, and numerical simulations.

at August 14, 2008 03:40 AM UTC

Plans and Updates

from Gil Kalai

Jerusalem and Budapest

Monday, last week was the last day of lectures for the spring term here at the Hebrew U. One outcome of the long professors’ strike was a very fruitful year for research seminars. We ran them during the strike and we run when we taught. I heard about quite a lot of nice developments recently. Zeev Dvir gave a talk on the finite field Kakeya problem. The proof was extremely simple to start with (see Tao’s post ) and Zeev’s presentation was even simpler. It is a very interesting question how, given Dvir’s proof, we should now view the connection between the finite field version of the problem and the original problem. Does Dvir’s proof support the possibility that the original problem is not as hard as feared? Does it support the view that the finite case is not related to the continuous case? (Both Tao and Laba discuss these questions.)

I will tell you in very rough terms (which represent my partial understanding of the matter) one recent wonderful development I heard about. Kolmogorov and Sinai proved that the Entropy is an invariant for Bernoulli shifts under isomorphism. Ornstein celebrated isomorphism theorem asserts that entropy is the only invariant. Orenstein and Weiss studied other group actions, and extended these theorems to amenable groups. There were strong indications that free-group actions behave very differently. (There were examples where the entropy function went the wrong way for “factors”.) However, Lewis Bowen has just shown that for free-group action entropy is an invariant! (OK, I oversimplified matters here for the sake of telling the story.) And he further proved a similar result for all “sofic groups”, a strange notion of groups which is a mixture of amenable and residually finite groups that, as far as we know, may include all groups. Benji Weiss told us about it in the “basic notions seminar”, and a few weeks later another lecture was given by the man himself - Lewis Bowen - who came from Hawaii for a short visit.

And last week I participated in a meeting “Building Bridges” in Budapest honoring Laci Lovász for his birthday. A lot of interesting talks on extremal combinatorics, graph theory, optimization, probabilistic combinatorics, and theoretical computer science. I will come back to this meeting later but let me mention one talk which I found very surprising: Peter Winkler talked about his work with Rick Kenyon on branched polymers. Kenyon and Winkler found startling simple combinatorial proofs to starling results of Brydges and Imbrie, and proved further results. I hope to add a link to the actual presentation. Hungary is the discrete mathematics superpower and on top of that as Einat Wigderson recently made clear “The Hungarians are also much funnier”. It was nice to meet many old friends (and annoy them, at times, with silly jokes). Here is Micky Simonovits and here you can see Endre Szemeredi, Anna Szemeredi, Szemeredi’s jacket and Szemeredi’s tie. I followed the name of the conference and talked about mathematics of social choice.

Plans

We had a few slow weeks on the blog and as the saying goes: “If you cannot do, plan, and if you cannot plan, plan plans.” Together with a little summary of previous posts, I will describe some of the things I plan to write next on this blog.

I plan five posts in the series about Extremal combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult theorems which became quite easy in time. Extremal Combinatorics III will present several basic results in extremal set theory; Part IV will be about POSETS, and part V will present the Frankl-Wilson theorem, or, at least, special cases.

I gave four posts (I, II, III, IV) based on my lecture in Marburg, dealing with high dimensional Cayley formula. Richard Stanley gave a detailed remark on why the fantasy about weighted correct version of MacMahon’s conjecture for solid partitions is not what standard proofs of the plane partition case extend to. I plan a little series of posts on “f-vectors and homology,” which was the title of a paper with Bjorner in 1988 as well as of my talk in Stockholm. However, before that I want to describe the “g-conjecture for spheres” a central problem in algebraic combinaorics.

We had several posts on convex polytopes. I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.) The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm. I also updated the post on five open problems regarding convex polytopes and added two additional problems.

We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. Meanwhile, have a look at the very successful discussion on Secret Blogging Seminar about the shy and secretive mathematicians, and how they triumph again and again.

Let’s talk some more on economics and rationality. And about sociel welfare functions and voting methods. We discussed some controversies related to rationality in this post, and the Notices book-review about economics and common sense supplied a source for two posts (1,2). I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. Sababa!

I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity. Meanwhile, let me link you to the classical post by Aaronson “Reasons to believe” (on why we believe that NP is not P). And while at it, look at “Reason to believe II” (on why many of us believe that quantum computers are feasible.) Read also Bernard Chazelle’s thoughts about alorithms and science.

The most successful link we had so far was “The Sarong Theorem Archive” - an electronic archive of images of people proving theorems while wearing sarongs. More than 100 people clicked on it. Pictures of prominent bloggers proving theorems while wearing sarongs are below.

And more stories in the category “Taxi-and-other-stories” and even “Mathematics-to-the-rescue” are planned. Stay tuned!

(Reminder: Arabic words which are part of Hebrew slang: ashkara - for real; sababa - cool, wonderful; walla - true; ahla - great; yalla - hurry up, c’mon, let’s go.)

Prominent bloggers prove theorems with sarongs

by Gil Kalai at August 13, 2008 06:45 PM UTC

More Art: Tami’s Autoportrait

from Gil Kalai

And in my office, there is a beautiful autoportrait by my sister Tamar Kalai. (Click for a deatiled picture.)

by Gil Kalai at August 13, 2008 04:19 PM UTC

Ridiculously hard proof of easy theorem

from Computational Complexity

Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently.

BILL: Justin, you've seen a proof of VDW's theorem, but there are easier things you haven't seen and should. Can you prove that the number of primes is infinite?

JUSTIN: Thats easy.

BILL: Good. How does it go?

JUSTIN: By the Green-Tao Theorem there are arbitrarily long arithmetic sequences of primes. Hence there are an infinite number of primes.

What to make of this?

Justin does not know how to proof the Green-Tao theorem (neither do I). However, if the proof does not use the fact that there are an infininte number of primes, then Justin's proof is valid. READERS: does anyone know, does it use the infinitude of the primes?
Justin now knows the standard proof. However, he should also learn that, at the level of math where he is at, you should be able to prove everything you use.
When does one start using theorems whose proofs one does not know? In research this is common. For basic coursework it should be rare.

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at August 13, 2008 12:33 PM UTC

There, I fixed that for you.

from Ernie's 3D Pancakes

Might be interesting for a discussion of how teen (if that’s what he’s supposed to be) engineering is portrayed, often as having immediate and irrevocable negative effects that preclude any type of future...though young people practicing engineering often aren’t provided with the resources (math education, access to safety equipment) that would help prevent the negative effects that engineering activity can cause.

Done correctly, it can be fun! Sure, there can be emotional trauma, awkward moments, broken hearts, impetuous late-night phone calls that you wish you could take back the next day. But these are downsides associated with life, not with engineering per se.

[Thanks, Luca]

by Jeff Erickson at August 13, 2008 04:33 AM UTC

Algorithmic Pricing via Virtual Valuations

from arXiv.org: Data structures and Algorithms

Authors: Shuchi Chawla , Jason Hartline, Robert Kleinberg
Download: PDF
Abstract: Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami et al. (2005) propose this problem and give logarithmic approximations (in the number of consumers) when each consumer's values for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic inapproximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter settings; however, logarithmic approximations are inadequate for this purpose. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this problem. Here a consumer has a valuation for each different item and their value for a set of items is simply the maximum value they have for any item in the set. We assume that the preferences of the consumers are drawn from a distribution, the standard assumption in economics; furthermore, the setting of a specific set of customers with known preferences, which is employed in all prior work in algorithmic pricing, is a special case of this general problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.

at August 13, 2008 03:40 AM UTC

Characterization Of any Non-linear Boolean function Using A Set of Linear Operators

from arXiv.org: Computational complexity

Authors: Sudhakar Sahoo, Pabitra Pal Choudhury, Mithun Chakraborty
Download: PDF
Abstract: Global dynamics of a non-linear Cellular Automata is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In the past efforts have been made to systematize non-linear CA evolutions in the light of Boolean derivatives and Jacobian Matrices. In this paper two different efforts have been made: first we try to systematize non-linear CA evolution in the light of deviant states and non-deviant states. For all the non-deviant states the nearest linear rule matrix is applicable where as for the deviant states we have a set of other matrices. Second using algebraic manipulation, an efficient algorithm is proposed by which every Non-linear Boolean function can be characterized by a sequence of binary matrices.

at August 13, 2008 03:40 AM UTC

Finding cores of random 2-SAT formulae via Poisson cloning

from arXiv.org: Computational complexity

Authors: Jeong Han Kim
Download: PDF
Abstract: For the random 2-SAT formula $F(n,p)$, let $F_C (n,p)$ be the formula left after the pure literal algorithm applied to $F(n,p)$ stops. Using the recently developed Poisson cloning model together with the cut-off line algorithm (COLA), we completely analyze the structure of $F_{C} (n,p)$. In particular, it is shown that, for $\gl:= p(2n-1) = 1+\gs $ with $\gs\gg n^{-1/3}$, the core of $F(n,p)$ has $\thl^2 n +O((\thl n)^{1/2})$ variables and $\thl^2 \gl n+O((\thl n))^{1/2}$ clauses, with high probability, where $\thl$ is the larger solution of the equation $\th- (1-e^{-\thl \gl})=0$. We also estimate the probability of $F(n,p)$ being satisfiable to obtain $$ \pr[ F_2(n, \sfrac{\gl}{2n-1}) is satisfiable ] = \caseth{1-\frac{1+o(1)}{16\gs^3 n}}{if $\gl= 1-\gs$ with $\gs\gg n^{-1/3}$}{}{}{e^{-\Theta(\gs^3n)}}{if $\gl=1+\gs$ with $\gs\gg n^{-1/3}$,} $$ where $o(1)$ goes to 0 as $\gs$ goes to 0. This improves the bounds of Bollob\'as et al. \cite{BBCKW}.

at August 13, 2008 03:40 AM UTC

The Peculiar Phase Structure of Random Graph Bisection

from arXiv.org: Computational complexity

Authors: Allon G. Percus, Gabriel Istrate, Bruno Goncalves, Robert Z. Sumi, Stefan Boettcher
Download: PDF
Abstract: The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can find cutsizes that are asymptotically within a factor 1 of optimal -- and possibly even the optimum itself -- in polynomial time for typical instances near the phase transition.

at August 13, 2008 03:40 AM UTC

I want to be an engineer…

from in theory

Discussion here and here

by luca at August 12, 2008 09:25 PM UTC

Puzzles

from WebDiarios de Motocicleta

I have a deep aversion of the "puzzle" concept. Delving into a problem is a very taxing process for me, and I just refuse to do it for the gratification of solving something that people actually expected me to solve fairly quickly. My brain can only internalize so many concepts in one day (like, maybe 2), and I can't waste this resource just so I can feel good about solving a small little problem.

Thus, when I read a recent blog post about how a theorist and two mathematicians spent their time after meeting randomly on a bus tour, I felt as if I was reading about an entirely outlandish experience, and I couldn't stop thinking "Why the heck... I can't believe they actually did this..."

Of course, I reminded myself that many people seem to love puzzles. An old friend used to say that "the brain doesn't rest, it atrophies." My adviser's office is the nightmare of any claustrophobic person: it is overflowing with small physical puzzles. I often fidget with them when I'm talking to Erik. The fact that I usually "solve" these problems by 5 minutes of random hand movement only confirms that I should never think about such things :)

My brain applies the same self-defense strategies when it comes to olympiad problems, which is why you don't see too many olympiad problems on this blog. When I originally read the Dwarves problem, I said "DP" (dynamic programming) and stopped. Only the next day, when 3 IOI guys claimed they really couldn't solve it, did I persuade myself to think about it...

Subscribe to comments |

Post a comment

by MiP (noreply@blogger.com) at August 12, 2008 06:35 PM UTC

Math Problems on vacation

from Computational Complexity

SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We alternated.

I asked them: if there are n couples in a resturant, and everyone sits either across from or next to their darling at a rectangular table (nobody sits at the ends) then how many ways can they be seated?
They asked me: A marathon is 26.2 miles. A runner runs in such a way that during EVERY 1-mile interval he averages exactly 10 miles an hour. But his overall time is better than 10 miles an hour. How can this be?
I asked them: Show that if no matter how your 3-color the numbers {1,...,2006} there will be two points, a square apart, the same color.
They asked me: There is a bus where n people have assigned seats. The first person sits randomly instead of in his assigned seat. Henceforth, every person looks for his assigned seat, and if he does not find it, sits in a random seat. What is the prob that the last person sits in his assigned seat?

How did we do on these problems? They got my problems correctly. I basically got theirs (missed some points).

It was interesting coming up with problems that had not well known. I couldn't ask them truth-teller-and-liar problems or hats problems, since these are well known. Some of the problems above have appeared on this blog before. Not sure if that makes them well-known. At least they didn't know them. I tried asking the following problem that I thought was not so well known (I read it in American Math Monthly and told it to Peter Winkler two years ago-- he had not heard of it), but they had already heard it:

Here is a game: There are initially two piles of stones with a in one pile and b in the other. Every move a player removes a multiple of the smaller pile from the larger. If either pile has 0 in it then you cannot move. THe first player who can't move loses. For which (a,b) does player I have a winning stradegy.

Readers- I am not going to post solution. But you can in the comments!

Subscribe to comments |

Post a comment

by GASARCH (noreply@blogger.com) at August 12, 2008 05:14 PM UTC

Our Department’s Quilt

from

Subscriptions

Theory of Computing Blog Aggregator

1) A fixed point theorem for differentials?

2) Joining Frobenius’ and Sylow’ theorems

1. A pleasant surprise

2. A bigger surprise

3. Is it better to have the discount first?

Jerusalem and Budapest

Plans