User rune - MathOverflow

Interesting families of sparse graphs?

2009-10-23T14:30:13Z

I'm interested in graph families which are sparse, and by sparse I mean the number of edges is linear in the number of vertices. |E| = O(|V|). Besides non-trivial minor-closed families of graphs (these turn out to be sparse), I don't know any other families. Can anyone suggest any interesting graph families (which are not minor-closed) which are sparse?

Please don't suggest the trivial family ("the family of sparse graphs").

EDIT: Thanks to the first few people who replied, I realized that bounded degree graphs (max degree < k) also form an interesting and large class of sparse graphs. So perhaps I'll refine my question to exclude those too. Any interesting sparse graph families where the max degree isn't bounded? For example the family of star graphs is sparse and not bounded degree. (But they're minor-closed.)

Algorithms on graphs of bounded degeneracy/arboricity

2010-01-02T05:04:57Z

I know that many graph problems can be solved very quickly on graphs of bounded degeneracy or arboricity. (It doesn't matter which one is bounded, since they're at most a factor of 2 apart.)

From Wikipedia's article on the clique problem I learnt that finding cliques of any constant size k takes linear time on graphs of bounded arboricity. That's pretty cool.

I wanted to know more examples of algorithms where the bounded arboricity condition helps. This might even be well-studied enough to have a survey article written on it. Unfortunately, I couldn't find much about my question. Can someone give me examples of such algorithms and references? Are there some commonly used algorithmic techniques that exploit this promise? How can I learn more about these results and the tools they use?

How hard is it to compute the Euler totient function?

2009-10-29T15:45:30Z

Are there any efficient algorithms for computing the Euler totient function? (It's easy if you can factor, but factoring is hard.)

Is it the case that computing this is as hard as factoring?

EDIT: Since the question was completely answered below, I'm going to add a related question. How hard is it to compute the number of prime factors of a given integer? This can't be as hard as factoring, since you already know this value for semi-primes, and this information doesn't seem to help at all. Also, determining whether the number of prime factors is 1 or greater than 1 can be done efficiently using Primality Testing.

How hard is it to compute the number of prime factors of a given integer?

2009-11-02T17:25:18Z

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.

So quoting myself from that thread:

How hard is it to compute the number of prime factors of a given integer? This can't be as hard as factoring, since you already know this value for semi-primes, and this information doesn't seem to help at all. Also, determining whether the number of prime factors is 1 or greater than 1 can be done efficiently using Primality Testing.

A subset of all languages which is uncountable?

2009-11-03T00:20:19Z

Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all languages and remove a few.")

For instance, I thought of the set of recursive or recursively enumerable languages, but these are countable. Perhaps some set in the arithmetic hierarchy?

This is probably a very easy question, and I'm just being silly.

Answer by Rune for Are there other nice math books close to the style of Tristan Needham?

2010-07-16T02:07:54Z

All You Wanted to Know About Mathematics but Were Afraid to Ask: Mathematics for Science Students by Louis Lyons

He explains some basic topics that science students need to know. Excellent explanation, extremely intuitive and beautiful. Too elementary for most readers of this thread, but a good read for an advanced high school student / beginning undergrad.

Answer by Rune for Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T20:14:47Z

A promise problem cannot be in NP, just because NP is defined to be a set of languages (or decision problems). It's like asking if the problem "Given n, output 2n" is in P. It's clearly an easy problem, and has a linear time solution, but it cannot be in P as stated because P is a set of decision problems, and the given problem is not a decision problem.

Your problem is in Promise-NP, since it's a promise problem with an efficiently verifiable certificate. See the wikipedia article on promise problems for some more information. Whether NC is a sufficient condition or a necessary condition or a completely arbitrary condition has nothing to do with the problem belonging to Promise-NP. As long as NC is a non-trivial condition which makes this a promise problem, the problem belongs to Promise-NP.

EDIT 1: I thought I should edit this to better answer Emil's question: I just want to know if Problem 2 is in NP. If you think it is not in NP, please could you explain why? It seems to me that "yes" answers do have succinct certificates.

NP is not the set of all things in the universe with succinct certificates! It is the set of all languages that have succinct certificates. Your problem does not define a language. It defines a promise problem. Therefore it cannot be in NP, not because it does not have a short certificate, but because it is not a language at all.

Answer by Rune for Do all uncountable sets contain elements with infinite Kolmogorov complexity?

2010-07-12T17:23:08Z

I'm not sure if I understand your question, but the set of all finite strings is countable, thus a set in which every element has a name (i.e., a finite description) is countable.

Answer by Rune for Do names given to math concepts have a role in common mistakes by students?

2010-06-18T13:27:03Z

"Open" and "closed". Every reasonable human being on the planet, who has not studied topology, will assume that something can either be open or closed, but not both. This often causes students to make statements like "Set A is open, therefore it is not closed, thus ..."

Answer by Rune for Are there complexity classes with provably no complete problems?

2010-06-14T03:25:37Z

This is more of a comment than an answer, but the comment go too long. From this thread, there seem to be two different themes to coming up with classes without complete problems.

Completeness is defined using two properties. L is X-complete if
(1) L is in X
(2) L is X-hard (under some suitable notion of efficient reductions)

The first theme involves classes which have hard problems, but if the hard problem were a member of the class itself, it would cause problems. The examples of POLYLOGSPACE and ELEMENTARY fall in this category. Both have hard problem, of course, but if the hard problem were a member of the class, some hierarchy theorem would be violated. (Space hierarchy and time hierarchy theorems, respectively.) Similarly one could come up with more examples of this kind.

The second theme involves classes which have no hard problems, such as ALL or P/poly. These classes don't have a complete problem for a fundamentally different reason than the previous case.

It would be interesting to see if there are other classes which fail to have complete problems for completely different reasons.

Super-linear time complexity lower bounds for any natural problem in NP?

2009-11-11T00:27:06Z

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd just like to know any examples of super-linear lower bounds.

I know that the time hierarchy theorem gives us problems which can be solved in O(n^3) but not in O(n^2), etc. Thus I put the word "natural" in the question.

I ask for problems in NP, because otherwise someone would give examples of EXP-complete problems.

I know there are time-space tradeoffs for some problems in NP. I don't know if any of them imply a super-linear time complexity lower bound though.

(To address a question below about machine models, consider either multitape Turing machines or the RAM model.)

Answer by Rune for Can SAT be solved in time n^k, for a specific k?

2010-06-10T13:21:23Z

It seems you are looking for lower bounds on SAT, not upper bounds. In that case, see this question I asked here a while ago. In short, the best lower bounds we have for SAT are linear, so can't even say that SAT cannot be solved in O(n) time.

Secondly I would just like to point out that Ben-David and Halevi's paper does not claim what you wrote. It says that if P vs NP is proved to be independent of PA (or ZFC) using currently known techniques then NP is contained in DTIME($n^{g(n)}$) for infinitely many inputs, where g(n) is an extremely slow growing function. Note the "infinitely many inputs" part, and most importantly, the "using currently known techniques" part.

Answer by Rune for Are there complexity classes with provably no complete problems?

2010-06-09T15:51:41Z

Here's a really simple class that is very natural and has no complete problems: ALL, the class of all languages. The reason is that there are uncountably many problems in ALL, but only countably many Turing machines to go around (for reductions), so every problem in ALL cannot be reduced to a single problem in ALL.

Similarly, any class with advice, like P/poly, L/poly, BQP/qpoly, or even P/1 does not have complete problems (using the same argument).

Efficiently sampling points uniformly from the surface of an n-sphere

2010-05-15T03:34:29Z

Is there an efficient way to sample uniformly points from the unit n-sphere? Informally, by "uniformly" I mean the probability of picking a point from a region is proportional to the area of that region on the surface of the sphere. Formally, I guess I'm referring to the Haar measure.

I guess "efficient" means the algorithm should take poly(n) time. Of course, it's not clear what I mean by an algorithm since real numbers cannot be represented on a computer to arbitrary precision, so instead we can imagine a model where real numbers can be stored, and arithmetic can be performed on them in constant time. Also, we're given access to a random number generator which outputs a real in [0,1]. In such a model, it's easy to sample from the surface of the n-hypercube in O(n) time, for example.

If you prefer to stick with the standard model of computation, you can consider the approximate version of the problem where you have to sample from a discrete set of vectors that $\epsilon$-approximate the surface of the n-sphere.

Answer by Rune for Efficient way of determining isomorphism

2010-05-03T23:45:27Z

As David points out, just knowing that the two graphs are isomorphic can't help you produce an isomorphism, as you could have just assumed this in the first place for any input, and then checked whether your algorithm really produces an isomorphism.

However, if you have an algorithm that always solves the decision problem "is G isomorphic to H?" then it can be used to produce an isomorphism between any two graphs that are isomorphic. This is similar to the fact that if you have some method of answering whether a given 3SAT instance is satisfiable, you can use that method to produce a certificate (an assignment of variables that makes the formula true). This property is known as self-reducibility, and is explained in these lecture notes.

A name for a claw-graph with paths attached to it

2009-11-01T13:54:29Z

I wanted to know if the following family of graphs has a name in graph theory: A claw with paths of any length attached to the three free vertices of the claw. More formally, a connected acyclic graph, with 1 vertex of degree 3 and the rest of degree 2 or less.

They're interesting because they arise in the study of graph minors. (In particular, if a graph of this type is a minor of another graph G, then it is also a subgraph of G.)

Answer by Rune for Is the Jaccard distance a distance?

2010-03-13T19:47:41Z

It is possible to prove this directly too, without invoking the Steinhaus Transform. But that would probably make the proof longer. However, I did once prove it directly, and I think it went a bit like this:

Assume there exist A, B ,C such that d(A,B) + d(B,C) < d(A,C). For such a counterexample, note that A, C and $A\cap C$ have to be nonempty. Now since the right hand side remains unchanged on changing B, we can remove all elements in B which are not in A or C, since that would only further decrease the left hand side. Thus B is contained in $A\cup C$. The final step involves arguing that we can also remove all those elements in B which are only in A or C, as this operation will also only decrease the left hand side. Finally, we will have a B that is supposedly a counterexample to the metric distance claim, but it lies completely in $A \cap C$. This can also be shown to be not possible.

I hope I remember it right, I haven't worked this out recently.

Answer by Rune for How important are publications for undergrads?

2010-01-08T15:58:30Z

I will point out that when Robert Solovay got tenure at Berkeley, he had no published papers.

Answer by Rune for Complexity class of problems solvable using Q&A site

2010-01-08T04:04:52Z

This question doesn't seem to be well-defined. First the poster is being restricted to ask only questions in FNP, i.e., questions whose answers can be verified in polynomial time. If this is the case, then the poster cannot obtain a truly random string from the monkeys, because the poster does not know how to check whether a given string is random or not.

Perhaps the real questions which you wish to ask are explained by the complexity classes that arise in interactive proof systems?

In short, if a probabilistic polynomial-time machine has access to an all-knowing Q&A site, then the polynomial-time question-poster can decide all languages in PSPACE with high probability. Similarly, If the poster has access to two such Q&A sites, then the poster can decide all of NEXP.

Answer by Rune for What programming languages do mathematicians use?

2010-01-08T03:28:42Z

BASIC! Gotta love the "goto" command.

Answer by Rune for BPP being equal to #P under Oracle

2010-01-05T03:14:15Z

First, let's be slightly pedantic and not make statements like P = #P, which cannot possibly be true just because P is a set of decision problems and #P is not. To get a decision version of #P, one can use PP, or something like P^#P.

About your question, BPP^NP is contained in P^PP and P^#P by Toda's theorem. On the other hand, if P^#P were contained in BPP^NP, it would imply that PH is contained in BPP^NP, which would collapse the polynomial hierarchy to the third (or second?) level, which is considered unlikely.

In conclusion, P^#P is considered to be more powerful than NP, BPP, BPP^NP and even NP^{NP^NP}.

Answer by Rune for How unhelpful is graph minors theorem?

2009-12-31T20:31:14Z

To answer some of your questions: 1. Yes, testing such properties is usually hard. For instance, before the graph minors theorem we had properties for which no algorithm was known at all! (Maybe a recursively enumerable algorithm was known, I don't remember.) After the graph-minors theorem, such properties became testable in polynomial time! Now that's a big jump from no algorithm known to polynomial time. (If I remember correctly, the polynomial is like O(n log n), which is almost linear time.)

As for 2. and 3., I don't know any property which we can easily test, for which we don't know the forbidden minors. I'd like to know such properties, if they are known. It seems to me that if we have an algorithm for easily testing a property, we really understand the property, and therefore should be able to come up with a list of forbidden minors somehow. Of course, this is just a feeling.

EDIT: I've been corrected in the comments. Please read Gil Kalai and David Eppstein's comments.

Answer by Rune for What practical applications does set theory have?

2010-01-01T04:47:27Z

Without knowing set theory, speaking to a mathematician will be like speaking to a Frenchman. You don't speak French, and he refuses to speak English.

Nah, just joking; mathematicians are nice people. They will explain in English if you don't speak set theory.

Answer by Rune for Local-Global approach to graph theory

2010-01-01T00:11:52Z

It seems like what you want is the field of Extremal Graph Theory. Most results in the field are about how global properties imply local structures or the reverse. An example of the first type is Turan's theorem, which for instance says that any graph with more than $n^2/4$ edges must contain a clique of size 3. On the other hand, we have Dirac's result, that if the minimum degree of a graph is n/2 then it must contain a Hamiltonian cycle.

A quick reference is Diestel's book which is available online for free. A better reference is Bollobas' book on the subject.

Answer by Rune for How to compute the rank of a matrix?

2009-11-29T05:33:58Z

Do you just want a lower bound on the number of function calls? You say that "we can't do better than m calls to the function in a deterministic algorithm". I would expect the same to be true for a bounded-error probabilistic algorithm as well.

EDIT: I thought I could prove this easily, but now I'm not so sure. Is this what you're asking though?

Answer by Rune for Cocktail party math

2009-11-13T23:27:30Z

If you work in Theoretical computer science (or related fields) you can say what Anup Rao says in this article.

Answer by Rune for Where to find nice diagrams of trees and other graphs?

2009-11-12T19:31:42Z

Wikipedia and Wikimedia Commons.

Erdős–Stone theorem type edge density estimates for bipartite graphs?

2009-11-10T04:07:33Z

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.

However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.

This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says:

"if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."

So can someone point me to the best known results now for bipartite cyclic graphs?

Answer by Rune for Independence from Set Theory Axioms

2009-11-10T20:10:04Z

If you prefer slightly non-technical explanations, the best one I've seen is the book "Gödel, Escher, Bach" by Douglas Hofstadter. It explains Gödel's incompleteness theorems and what it means to be independent of a set of axioms.

In my humble opinion, it is one of the best books ever written, in any field, by anyone.

Answer by Rune for How do you keep your research notes organized?

2009-11-08T23:04:07Z

Research thoughts are like a tree. Thus linear options like notebooks don't seem to work that well. I would suggest writing all your thoughts on loose sheets and filing them like how you would store a tree in memory. Each parent node keeps a pointer to its children. To mark new nodes in the file, use those colorful stickers that can be stuck on pages which can be seen when the file is closed. These stickers can contain labels, like "new approach 2." Since its a file, you can add extra pages whenever you feel like, and rearrange sections to make it coherent whenever you feel like.

Comment by Rune

2010-07-13T03:14:33Z

The decision problem associated with a language $L\subseteq$ {0,1}<sup>*</sup> is the following: Given x in L, output yes. Given x not in L (i.e., given x in the complement of L), output NO. If L is the language you claim -- the set of all strings representing graphs that satisfy NC and are 3 colorable, then the complement of L contains all graphs that do not satisfy NC or are not 3-colorable. Thus the output of the algorithm on such graphs will be NO. This is not what you mean by your problem. You want the output to be NO when the graph satisfies NC but is not 3-colorable.

Comment by Rune

2010-07-12T23:16:21Z

I've added an answer to your question in my original answer. How's that?

Comment by Rune

2010-07-12T20:59:50Z

For any complexity class inside NP one can define a promise version of any NP-hard problem that falls in that class, as pointed out in Scott's answer. Is that what you're asking?

Comment by Rune

2010-07-12T20:57:35Z

I answered the comments after Shreevatsa's answer. The fact that NP is defined using decision problems and not promise problems is just a matter of convention. We could equally well have started complexity theory with only promise problems. There is nothing deep here, it's just a matter of convention and definitions.

Comment by Rune

2010-07-12T20:55:04Z

@shreevatsa: The union of YES and NO instances is not the set of all graphs, it's the set of all graphs satisfying NC. Thus the problem is still a promise problem (unless NC is a trivial condition satisfied by all graphs).

Comment by Rune

2010-07-08T22:28:08Z

+1 for the statement "it is not hard to show that it is in P. Or NP-complete..."

Comment by Rune

2010-06-20T02:13:59Z

Definitely the book I would recommend for non-math majors. It has plenty of examples to motivate topics, which is what non-mathematicians need in order to be interested in linear algebra. Vector space axioms are the absolute worst way to teach linear algebra to any group of people that is not wholly composed of math majors.

Comment by Rune

2010-06-11T02:22:52Z

Corollary 6 also has the "any method known today" clause, which is the most important caveat. As for the best lower bound, it depends on the model -- boolean circuits, one tape TMs, two tape TMs, etc. See the question I linked to for some very good answers by people who understand this area much better than I do.

Comment by Rune

2010-06-09T20:03:31Z

The same argument works for any hierarchy that is known to be infinite. I guess this general method captures most of the examples given in this thread till now, like POLYLOGSPACE, ELEMENTARY, etc.

Comment by Rune

2010-05-15T12:02:16Z

I don't understand what you mean. Obviously some reals can be represented, but those just form a measure 0 set. Most reals cannot be represented finitely.

Comment by Rune

2010-03-25T18:39:56Z

Bourbaki is not an actual person. Who exactly had the right definition before the proper definition was formulated?

Comment by Rune

2010-03-24T14:40:13Z

This "online reading group" sounds like a great idea. If this doesn't exist, someone should start a website like this. Besides the many academic uses, it would be useful for many groups of people too. E.g. Gamers: discuss strategy or the results of the last game Forum users: video debates or discussions instead of a text-only forum Musicians: discuss/perform music over video

Comment by Rune

2010-03-01T23:59:58Z

A linear time algorithm (i.e., O(m+n)) for detecting paths of length k was mentioned in one of Alon et al.'s papers. It just involves choosing a random ordering of the vertices, and making the graph a DAG using this ordering. Since longest path on DAGs can be solved in linear time, a directed path of length k can be found in linear time, if the chosen random ordering works. Repeat the previous step exponentially many times (in k), to get desired randomized algorithm.

Comment by Rune

2010-03-01T23:49:02Z

It is also in co-NP.

Comment by Rune

2010-01-14T05:03:57Z

By arbitrarily large I just meant that for any given k there exists a planar graph with tree width > k. Of course the tree width can never be more than the number of vertices, so that's always an upper bound on the tree width of a graph.