User talk:RobinK/Archive 1

Archive 1

Welcome

Hello, RobinK! Welcome to Wikipedia! Thank you for your contributions to this free encyclopedia. If you decide that you need help, check out Getting Help below, ask me on my talk page, or place {{helpme}} on your talk page and ask your question there. Please remember to sign your name on talk pages by clicking or using four tildes (~~~~); this will automatically produce your username and the date. Finally, please do your best to always fill in the edit summary field. Below are some useful links to facilitate your involvement. Happy editing! Verbal chat 07:02, 6 July 2009 (UTC) Getting started A tutorial • Our five pillars • Getting mentored How to: edit a page • upload and use images Intuitive guide to Wikipedia Getting help Frequently asked questions • Tips Where to ask questions or make comments Request administrator attention Policies and guidelines Neutral point of view • No original research Verifiability • Reliable sources • Citing sources What Wikipedia is not • Biographies of living persons Manual of Style • Three-revert rule • Sock puppetry Copyrights • Policy for non-free content • Image use policy External links • Spam • Vandalism Deletion policy • Conflict of interest • Notability The community Build consensus • Resolve disputes Assume good faith • Civility • Etiquette No personal attacks • No legal threats Community portal • Village pump Signpost • IRC channels • Mailing lists Writing articles Be bold in editing • Develop an article The perfect article • Manual of style Stubs • Categories • Disambiguation Pages needing attention • Peer review Miscellaneous User name • User pages • Talk pages Clean up: General • Spam • Vandalism Join a WikiProject • Translation Useful templates • Tools • User scripts

Cluster state

You're right. Sorry about that, I must have been half asleep when I added the non-existent category back in. Euryalus (talk) 22:45, 9 July 2009 (UTC)

Fast algorithms

I have removed the {{prod}} tag from Fast algorithms, which you proposed for deletion. I'm leaving this message here to notify you about it. If you still think the article should be deleted, please don't add the {{prod}} template back to the article. Instead, feel free to list it at Wikipedia:Articles for deletion. Thanks!

Not a subject I know much about but historically fast algorithms were not always desirable because they could be difficult to compute. Whether it is a "field" I an not sure but it is certainly an area of mathematical interest. Thincat (talk) 20:40, 20 August 2009 (UTC)

Encouragement

		The Barnstar of Diligence
		For the systematic effort of reducing the randomness in our articles on computational complexity and analysis of algorithms. Pcap ping 02:44, 23 August 2009 (UTC)

Thank you very much! --Robin (talk) 03:30, 23 August 2009 (UTC)

Separation of concerns

I see you tagged it with a merge tag. Please start a discussion with you rationale on the talk page or the tag will get removed. By the way, it's a well-known concept in some circles e.g. operating systems or networking. (I did not read the wiki article.)Pcap ping 17:47, 25 August 2009 (UTC)

Separation of concerns

I unprodded Rohit Khare, who does seem sufficiently notable. Happy to discuss. MarkBernstein (talk) 14:02, 26 August 2009 (UTC)

Nah, it's fine. I'll trust your judgment. I didn't have any strong feelings on it. --Robin (talk) 14:38, 26 August 2009 (UTC)

Articles you might like to edit, from SuggestBot

SuggestBot predicts that you will enjoy editing some of these articles. Have fun!

Stubs Introduction to Algorithms Bhaskara Mathematical statistics Computation Nevanlinna Prize Persistent data structure P Warwick Arts Centre Online algorithm Superconducting quantum computing Edge Hearts and Bones Charge qubit XTR Set-theoretic limit Coherent information Disperser Kyoto Prize Resource starvation

Cleanup Gödel's incompleteness theorems Orders of magnitude (time) Regular language Merge Tree (data structure) 1 E-2 s Non-standard analysis Add Sources RP (complexity) Data structure RE (complexity) Wikify Gradient descent Keystroke logging Packing problem Expand Clay Mathematics Institute Theoretical computer science Mersenne twister

SuggestBot picks articles in a number of ways based on other articles you've edited, including straight text similarity, following wikilinks, and matching your editing patterns against those of other Wikipedians. It tries to recommend only articles that other Wikipedians have marked as needing work. Your contributions make Wikipedia better -- thanks for helping.

If you have feedback on how to make SuggestBot better, please tell me on SuggestBot's talk page. Thanks from ForteTuba, SuggestBot's caretaker.

P.S. You received these suggestions because your name was listed on the SuggestBot request page. If this was in error, sorry about the confusion. -- SuggestBot (talk) 00:05, 28 August 2009 (UTC)

FL (complexity)

Oddly enough, that one isn't even defined on the zoo, only FNL is. Maybe you know where to look for it? Pcap ping 23:40, 8 September 2009 (UTC)

Tried my sources. Can't seem to find it. Weird. --Robin (talk) 22:40, 12 September 2009 (UTC)

I decided to ask the editor that created the article, User:Creidieki, who apparently does research in this area. But he hasn't done much editing here lately, so it could take a while to hear back. Pcap ping 23:33, 12 September 2009 (UTC)

Church–Turing–Deutsch principle

There seem to be at least two variations of this, one as stated there, and one that is stronger (roughly an equivalent of the strong Church-Turing thesis for quantum computers). Needless to say that Michael Nielsen also gives this stronger version in his book. So, do you have access to the original paper I've added to that article? I probably do too, but I'm not very motivated to go the Physics library just for this (physics journal)... Pcap ping 03:27, 13 September 2009 (UTC)

Do you mean this one? --Robin (talk) 13:51, 13 September 2009 (UTC)

Thanks for the find. Pcap ping 16:20, 13 September 2009 (UTC)

Quantum gravity computers

Do you think this way speculative to even mention in quantum computer? I only have a vague understanding of this, but the argument seems to be that space and time need not be regarded as two separate resources by such a computer (see paper in first hit on gbooks). I don't feel I understand this well enough to write here (or anywhere) about it. Maybe it interests you? Pcap ping 19:14, 13 September 2009 (UTC)

Yeah, I think it is extremely speculative at the moment. We don't even have a theory of quantum gravity that physicists agree on, let alone a computational model that exploits this theory. Consequently we have no idea how such a computer will behave. The only extensions of quantum computing I know are the following:

• What happens when we extend computation to topological quantum field theories? Answer: Equivalent to quantum computers. (Shown by Freedman, Kitaev, Wang in 2000)
• What happens if we allow non-linear quantum mechanics? Answer: This model is too strong. It solves NP-complete problems in polytime. (I think shown by Abrams & Lloyd in 1998)

I don't know of any serious proposals for string theory computers, loop quantum gravity computers, etc. --Robin (talk) 19:26, 13 September 2009 (UTC)

Thanks for the answer(s). L. Hardy indeed speculates that quantum gravity theory will require infinte causal structure, and explores what that may imply for computing. I can't tell if what L. Hardy proposes implies NP-complete problems will be solvable in poly time, since space and time are no longer two different dimensions in his model. Anyway, I found the preprint of his paper on [1]. There's also an older New Scientist article here (did not read it), but that publication often publishes dubious stuff, in part because editors don't always understand what they talk about. However, in Hardy's paper I found a link to a survey paper of Scott Aaronson that discusses NP-completeness and physics in general, including quantum gravity [2]. It looks like a good source for a section in NP-complete... Pcap ping 19:45, 13 September 2009 (UTC)

I had read Scott's paper before; it seems I forgot most of it. But on rereading it, I see that the main point regarding quantum gravity computers is that we don't know how to define what it would mean. And that he tried to do so, but doesn't have a satisfactory way of defining it. He sorta leaves it as an open problem to come up with a way to characterize Quantum Gravity Polynomial Time (QGPT). Until this idea gets more coverage, I would hesitate to add it to a Wikipedia article. --Robin (talk) 19:57, 13 September 2009 (UTC)

Decision tree complexity

Please split out the page Quantum decision tree, since there is enough text already, leaving a summary in the corresponding section Decision tree complexity, per wikipedia:Summary style. I could have done this myself, but I don't want to deprive you of the glory of article creation :-) - Altenmann >t 23:29, 6 October 2009 (UTC)

The "properties" section is actually a list of properties of all decision trees, quantum, random and deterministic. Most of them are relationships between the three. So it's much better that they're all in the same article. --Robin (talk) 01:58, 7 October 2009 (UTC)

Translation of the complexity theory article

Dear RobinK,

I cannot guarantee that I will continue to translate chunks from the German article in the near future. At the moment, my time and energy I can spend on this is very limited. So, please feel free to make changes and improvements to the structure of the article. I hope that the quality of the article will be once upon a time on par with its relevance. Best wishes, Hermel (talk) 21:13, 14 October 2009 (UTC)

On proofs of Goödel's theorem

This is off topic so I thought I would put it here. In the lecture notes you linked, Aaronson says,

"People always say, "the proof of the Incompleteness Theorem was a technical tour de force, it took 30 pages, it requires an elaborate construction involving prime numbers," etc."

but then he goes on to say,

"(This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.)"

It is that latter part that is the issue, both in those notes and in Likebox's edits. The part of the proof of the incompleteness theorem that uses the diagonal lemma is very short and easy; this is the part that Aaronson wants to replace by talking about the halting problem.

The difficulty in the proof sketched by Aaronson is entirely in showing that statements about computer programs halting can be translated into statements about natural numbers in a way that the statements about natural numbers can be expressed within formal theories of arithmetic. Aaronson skips this step by giving just a parenthetical comment.

To complete this step rigorously requires developing a Gödel numbering for programs, and then showing that these Gödel numbers can be manipulated via formulas in a formal theory of arithmetic. Showing this is not particularly easier or shorter than showing that it is possible to set up Gödel numbers for formulas, as is done in the original proof. If anything, it is more difficult, because either way one has to know about formulas, but Aaronson's proof also requires proofs of a large number of facts about computability before one can prove the incompleteness theorem.

So the stuff that Aaronson describes as "an elaborate construction involving prime numbers" is still required in Aaronson's proof; Aaronson simply skips it to present a short summary. That is fine for a set of lecture notes, but not for a text nor for an encyclopedia article. Once one adds this back to Aaronson's proof, it is neither shorter nor easier than the standard proof. — Carl (CBM · talk) 03:07, 15 October 2009 (UTC)

Oh, I see. Thanks for the explanation. --Robin (talk) 03:36, 15 October 2009 (UTC)

Please do not be intimidated by CBM. He opposes the text and wants to drive away supporters. With only two more voices on the opposite side, he would be outnumbered.

CBM's position is that the two statements:

1. Computations are statements about integers
2. Logical deductions are statements about integers

are both equally difficult to make precise. Both require an arbitrary encoding into integers of something or other. This is true--- but only if you are a newborn baby.

Any person who has lived in this world has had experience with computers. Anyone who has programmed a computer at even the most rudimentary level knows that they are only manipulating integers inside. The processor makes simple changes to the memory, according to a well-defined rule which can be computed in a short time by pencil and paper. This fact is so obvious today, that it does not require detailed explanation. Turing and Intel tell us how to do this, not only in theory, but in practice.

Once you know that programs manipulate integers, the specific program that performs logical deductions is obviously a special case. But Godel was writing before computers, and he had to show that logical deduction can be represented as a manipulation of integers. In order to do this, he could not use a pre-existing computer, so he had to design his own. He did this in an arbitrary, unreadable, and completely uninteresting way.

Once he defines a notion of computation which is enough for his purposes (he only defines primitive recursive computations in 1931, in modern terms, he allows for-loops, but no while loops), he then constructs a Godel sentence G. This construction involves a second trick, self-reference. The two sticking points for reading Godel's paper traditionally are understanding his computer, and understanding his self-reference trick.

Assuming that the modern notion of a computer is already understood, the first technical complexity vanishes, the computer is obvious. To get around the second technical complexity, one way is to replace the self-reference in the Godel sentence G with self-reference in a computer program. A computer program can talk about itself, because a computer program can print its own code. In order for a sentence G to talk about itself requires a peculiar trick involving logical variables, which is both specific to logic, and entirely equivalent to printing your own code.

Once you make these two simplifications, both of which are obvious today within computer science, Godel's theorem is trivial. In order to prove that a formal system S is incomplete, construct the code SPITE to do the following:

1. Print its own code into a variable R
2. Deduce all the theorems of S, looking for "R does not halt"
3. if it finds this theorem, halt.

Then the Godel sentence for S is "SPITE does not halt".

By shunting the self-reference and the arithmetization into the computer program, where it is obvious, instead of the logical deduction, where it is not, you simplify the presentation to the point where it is understandable by anyone.

In order to incorporate these discussions into Wikipedia, there is a barrier. Some people oppose any text that does not look like a textbook in a knee-jerk way, regardless of clarity or correctness. In the past, these people joined forces with people who thought that this proof "is too simple to possibly be correct" or "is obviously incorrect". The latter category of editors are mostly gone, so now the only objection is "This is not what they taught me in school". It is very important that this objection be opposed.

The reason is (and I am sorry for being so long winded) that Godel's work was expanded greatly by computer scientists and computationally minded mathematicians in the 1940s,1950s and 1960s. This work, due to great mathematicians like Friedmann and Muchnik, Spencer, Post, Wang and many others, is not often properly understood nowadays. Mathematicians have actively resisted language which uses computer science notions, like "memory" or "loop", requiring that any theorem be phrased in a certain way, which only uses admissible notions first presented by Godel, like "recursive function". The logic of the proofs is obfuscated enough by these language restrictions, that great theorems have been lost through obscurity. Hardly anybody understands them anymore, even though they are classics in the field.

Wikipedia, in its role of preserving and tranmitting human knowledge, must fix this problem. In order to do this, text must not be deleted based on how close it is to textbooks. Text explaining intermediate steps in proofs of well known sourced results should be judged on its accuracy and clarity, not on how close it is to textbooks.

This position is in a new proposed guideline WP:ESCA. I support this guideline. I hope that the short proof can be added to the text of Godel's incompleteness theorems, so that similar proofs can then be provided for injury-priority method, for turing degree theory, and other unfortunately obscure topics in computational mathematics.Likebox (talk) 23:36, 15 October 2009 (UTC)

Regardless whether one is a newborn baby, one still has to prove that "SPITE does not halt" can actually be expressed as a formula in the language of arithmetic. This, in turn, requires developing something like Kleene's T predicate, which is not a trivial task. The language of Peano arithmetic include constants for 0 and 1, addition and multiplication functions, and the equality relation; and existantial and universal quantifiers over individual numbers. The fact that one can express in that language that a particular program halts is far from obvious. One cannot push this arithmetization inside the computer program, because the Gödel sentence must actually be a sentence in the formal theory of arithmetic under consideration. — Carl (CBM · talk) 00:03, 16 October 2009 (UTC)

While one should not engage in debates on another user's talk page, I would like to quickly respond: "Kleene's T predicate" is the object that makes that the operation of a code "C" on input "I" after N steps an object of arithmetic.

To see that it can be constructed in arithmetic with multiplication/addition existential/universal is a little bit of a headache. But within primitive recursive arithmetic it is trivial, because primitive recursive arithmetic includes the elementary processor step of any computer as a primitive idea, and Godel's theorem works for any arithmetic that can describe a computer.

If you just have addition and multiplication, you need to show that a computer can be encoded using only that. It's not difficult, and it can be done in umpteen different ways. The main point is that any primitive recursive function on a sequence of integers can be written as a sentence of arithemtic involving only writing an integer I in the form I= 2^a0 3^a1 5^a2 7^a3 ,etc. Any primitive recursive operation on the finite sequence a0,a1,a2,...,ak is an operation on I which can be written in terms of addition and multiplication only (essentially because finding the ak's can be expressed in a finite way in logic using only the idea of multiplication). Then any instruction set of a modern computer can be expressed as an operation on a0,a1,...,ak.

But this is it. If CBM wants this included in the text, it would take only a paragraph to insert, and it would complete the proof of Godel's theorem. As it stands, the proof is complete for primitive recursive arithmetic, which is the arithmetic that people have in their heads anyway.Likebox (talk) 00:27, 16 October 2009 (UTC)

I'm going to agree with CBM on this one. Let me make a very general argument. You say this proof is a lot easier than the "standard" proof which appears in many textbooks. Surely you can't have been the first person to observe this? (If you are, then please publish it.) Surely this appears some where in print, in a paper or book, written by someone else? If you can provide verifiable sources which have your proof, that would be great. If not, and you are the only person to have ever come up with this, then please go ahead and publish it. If neither is the case (i.e., lots of people know this proof, but no one has written it up anywhere), then there is a good reason no one has written it up anywhere. Thus it shouldn't be on WP either. --Robin (talk) 01:06, 16 October 2009 (UTC)

I do happen to be the first person to state the proof in exactly this language, however there are many people who understand the proof in exactly this way. I was told that when explaining Godel's theorem, Solovay does this, and there are several articles which explain Godel's theorem in similar ways. I would never publish this as a self-contained work (perhaps in an introduction to a longer work), because I would be embarassed. There is no original idea here.

Although this exact argument is not written up this way, equivalent arguments are made often in slightly different language. You are wrong in your sociological observations. People are stupid, and don't make efforts in clarity and pedagogy as they should. Since the only innovation in the proof is pedagogical, it is not surprising that it is not found everywhere.

However on Wikipedia, clear pedagogy can be put in place. For example, the presentation of the BKL results on BKL singularity is novel, and very clear, but it does not extend the ideas in BKL in any significant way. This exposition is of the same type. These things must be protected.

If you still agree with CBM, then hopefully you will change your mind. If not, well, I am just sorry.Likebox (talk) 01:28, 16 October 2009 (UTC)

Well, I'm going to stick with my "sociological observations." I do believe that text book authors are intelligent people and usually professors who have had years of experience teaching courses to students. I consider their judgment to be superior in this regard. --Robin (talk) 17:04, 16 October 2009 (UTC)

You can check your sociology with a simple test: present the two proofs of the incompleteness theorems side by side to any mathematics undergraduate (or even graduate student). See which one is clearer. I have done this hundreds of times, and I already know the answer.

In order to get a complete understanding of, Godel's theorem and Rosser's theorem from a standard textbook takes about two weeks of intensive study. Most of this time is spent re-proving obvious computer science trivialities, which are given ponderous recursion theoretic names. The final proof does not follow Godel 1931, but Kleene's presentation some decades later. The proof of Rosser's theorem is usually just left out.

I get motivated to edit this article whenever I meet yet another undergraduate that failed to understand the proof of Godel's theorem. Usually they have taken a course on the subject, and still don't understand the proof.

Strangely enough, other subfields of mathematics don't get bogged down like this. Logic has been different, because in the 1950s and 1960s, in order to prevent encroachment on their field by computer science, mathematics purged all proofs that involve computer programs, only allowing algorithmic proofs which are phrased in recursion theoretic language. This was done for political reasons: to clearly separate math and CS literature. The discussion about this separation are preserved in the logic literature. There is no reason that Wikipedia should follow mathematicians on this. Wikipedia includes mathematics and computer science equally, and for a theorem like Godel's, which belongs to both fields, one should not be allowed to elbow out the other.Likebox (talk) 21:07, 16 October 2009 (UTC)

Start-class assessment of Equitable coloring

I'm trying to understand your recent assessment of equitable coloring as Start class, not so much because I care much about that specific article (it is as you accurately assessed it of low priority) but in order to try to understand how my writing might be improved. Specifically, according to Wikipedia:Version 1.0 Editorial Team/Assessment, a start-class article is one that is obviously incomplete and obviously lacking in reliable sources; a C-class article still lacks coverage of some of the important aspects of the subject, is inadequately referenced, and needs cleanup, and a B-class article (the standard I was aiming for in this article) is mostly complete and has no major stylistic issues. In this case I don't know of any important aspects of equitable coloring that are not covered, there are many references (in harvard parenthesized style, one of the standard styles considered acceptable on Wikipedia), and if there are major problems with the quality of my writing I'd like to know what they are. Can you explain your rating, please? —David Eppstein (talk) 00:44, 22 October 2009 (UTC)

That would be an error on my part. I was going through all the unassessed discrete math articles, and marking the non-stubby ones as either Start or B (with the simple algorithm of giving an article a B if it has refs/citations, doesn't look obviously bad and has pictures if appropriate). I should have marked it as a B-class article. I've fixed the assessment now. --Robin (talk) 00:58, 22 October 2009 (UTC)

Oh, ok. Thanks. —David Eppstein (talk) 01:15, 22 October 2009 (UTC)

Discussion text on QM introductory articles

Hi Robin,

Here's the text I promised to draft suggesting a discussion on the readership of the QM introductory articles.

For a variety of reasons, there are currently two different introductory articles on Quantum Mechanics on Wikipedia (in addition to the Quantum mechanics article itself):

• Introduction to quantum mechanics, which aims to be accessible to those with a command of high school algebra, but which has been criticised for going into too much technical detail and mathematics for an introductory article.
• Basic concepts of quantum mechanics, a more descriptive article with less mathematical detail, but which has been criticised for going too much into the history and a lack of mathematical detail.

Arguably this is at least one too many introductory articles, and various ways of dealing with this issue (by merging, moving content, deleting, etc.) have been suggested without ever coming to a consensus view. Possibly the problem is that we haven't yet answered the more fundamental question: what level(s) of readership should the introductory article(s) be targeted at?

This discussion has been raised in order to generate a consensus view on this issue, which can then inform discussion of what to do with the articles. In order to avoid having the same discussion taking place on three different talk pages, please direct all comments to TBD.

I'd like to get your opinion / agreement on this before posting it to the talk page - I'm aiming for a neutral summary of the question at this point, not to push my opinion (though I will post an answer to my own question with my views in it!).

Thanks! Djr32 (talk) 11:43, 24 October 2009 (UTC)

Yeah, this looks fine and summarizes the problem well. Perhaps it should be posted on Talk:QM and Talk:Intro, and have the discussion on Talk:Basics? --Robin (talk) 14:32, 24 October 2009 (UTC)

About Quantum Walks for Computer Scientists

My name is Professor Salvador Venegas-Andraca and I am the author of the book "Quantum Walks for Computer Scientists".

According to the history of quantum walk page in Wikipedia, you deleted my book entry. I want to know why you did so. My book is a fully verifiable and reliable scientific source published by Morgan and Claypool, a serious editorial company. I am truly expecting an explanation as that deletion was tremendoulsy annoying. Nobody owns Wikipedia and I have the right to advertise my publications.

Do not delete my book entry again, otherwise I shall be forced to make a serious and formal complain for such an outrageous behavior. You are not the owner of any Wikipedia page and have no right to censor information.

Professor Salvador Venegas-Andraca, DPhil (Oxon) —Preceding unsigned comment added by Salvador.venegas (talk • contribs) 07:08, 1 November 2009 (UTC)

Reply to your criticism made on 1 November 2009

I have replied in Quantum Walk discussion page. —Preceding unsigned comment added by 189.144.33.80 (talk) 15:31, 1 November 2009 (UTC)

Replies to your and Verbal's posts made on 1 and 2 November 2009

Hi RobinK,

I delivered my reply to your and Verbal's posts, about including my book on quantum walks in the survey section of Wikipedia article on quantum walks, here. I do not mean to pressurize or be taken as pushy, I just want to make sure you know that my answer is already in the quantum walk talk page.

Best regards,

Salvador

Salvador.venegas (talk) 23:13, 3 November 2009 (UTC)

Answer and question

I have replied to your answer (3 November 2009). Please let me know.

S.

Salvador.venegas (talk) 06:48, 4 November 2009 (UTC)

One more question

Hi RobinK,

I apologize for pestering you with one more question, but my lack of knowledge about Wikipedia's nomenclature and my wish to make things fine with you and Verbal make me ask the following:

In your last post about my book being included in the quantum walk article, you said that "This doesn't mean that I'll object to its addition by another editor". My question is: what is the definition of a Wikipedia editor?

Basically, I want to know whether I have to wait for a certified editor (i.e. a person who has been apppointed as editor by Wikipedians/Wikipedia governing body) to put my paper under the reference section or, alternatively, if an editor is just a Wikipedia contributor, whether it would be fine for me or another contributor to put my book back under the references section.

I want to stick to the rules, so please give me some guidance here.

I will work on expanding the quantum walk article regardless of whether I can see my book on the reference section now or later on, so this question is not about my willingness to do as told, but only about doing what I am truly expected to do.

Finally, please accept my apologies for placing my question here (I understand you like having messages posted in the article talk area), I just thought this question of mine did not contribute to the previous discussion, about whether it was fair to cite my book or not, any longer.

Cheers,

S. Salvador.venegas (talk) 05:23, 5 November 2009 (UTC)

A Wikipedia editor is just anyone. You and me included. But as Verbal said, you should generally not add your own book back, because of WP:COI. Even if you feel that you're not exactly violating COI, it would violate the spirit of that document. So what I meant is that if some other editor (besides you) feels that it should be added, I wont object to that.

Yes, I usually prefer discussions on the talk page, but if it's a specific question that you feel is inappropriate for the talk page then it's fine to have the discussion here. If it's a general question, it's usually better on the talk page since more people can read and reply to it. --Robin (talk) 13:46, 5 November 2009 (UTC)

Doctoral students of Richard M. Karp

Why did you remove the link to Karp's list of graduate students at the Mathematics Genealogy Project? Karp's wiki page now lists just four of his students. Are these ones special somehow? Quantling (talk) 20:17, 16 November 2009 (UTC)

Yes, they're special because they are notable (and have Wikipedia pages of their own). For instance, Andrey Kolmogorov has 79 students. Only a few are listed on his page. All the listed ones have their own articles. In general, the doctoral students entry is for "Names of any notable doctoral students advised by the scientist." (Template:Infobox_scientist) --Robin (talk) 21:36, 16 November 2009 (UTC)

Might we add Dan Gusfield, Ron Shamir, and Abhijit Sahay, even though they have no Wikipedia pages? They are notable doctoral students advised by the scientist. Can we add also add a link like this: Full List Quantling (talk) 17:56, 17 November 2009 (UTC)

The full list is probably not useful, since the idea is to list notable students. The references already have a link to his MathGenealogy page, which contains the full list. Usually links to uncreated pages aren't added in infoboxes; the pages are created first and then linked to. If you do add them, someone might revert your edit or question notability. --Robin (talk) 19:45, 17 November 2009 (UTC)

PPAD

My reasoning was that the closest area of mathematics to complexity theory is computability theory, and computability theory articles are all classified under mathematical logic (or should be). Mathematicians don't usually consider computability to be part of "discrete mathematics". The American mathematical society subject classification puts complexity theory under two primary classifications: 03 (mathematical logic) and 68 (computer science). [3] — Carl (CBM · talk) 15:51, 22 November 2009 (UTC)

Basic concepts of quantum mechanics (again!)

It doesn't look like this discussion is going any further! Perhaps it's time to try something else. Would you object if I started by proposing a merger between the basic concepts article and the intro article? (This shouldn't stop you using text from the basic concepts article to improve the timeline / history articles if you still want to do this.) Djr32 (talk) 21:14, 30 November 2009 (UTC)

Yeah, that's fine. There should only be one intro. I'm not sure how you will appease the people who want math in the intro and those who don't. --Robin (talk) 21:17, 30 November 2009 (UTC)

Wow, that was quick! Hopefully we can reach a sensible compromise - but there's a reason I only said I'd propose the merger... Djr32 (talk) 21:25, 30 November 2009 (UTC)

collaboration?

Improving the article extremal graph theory sounds good to me. I'll start working on it a bit. Best, ExtremalGraphTheory (talk) 19:24, 28 December 2009 (UTC)

Actually, we should probably figure out right from the start what we mean by "extremal graph theory". The term is slightly vague, and in its most include interpretation, is much to large for one article. I would prefer being on the restrictive side of the definition. ExtremalGraphTheory (talk) 20:02, 28 December 2009 (UTC)

Sounds good, let us start the discussion on the talk page of the article, so that other interested editors may also join in. --Robin (talk) 20:07, 28 December 2009 (UTC)

Mathematicians

This is one of the reasons that the term "priority" is better than "importance", which sounds much more judgmental. I don't have any sound way of determining priority for mathematician biographies, since I have only had to rate a handful of them at most. But my general opinion would be to look at the awards the person has received. So a Fields medalist is probably going to be a high-priority article, and someone who is well known in his or her area but not well-known among mathematicians in general would be low priority.

On the other hand, I try not to worry too much about making perfect assessments. The overall idea is that other people can correct the ratings, os that over time the settle into the correct values. — Carl (CBM · talk) 02:51, 4 January 2010 (UTC)

Project Recognized Content & A-Class Articles

You had asked about adding support for A-Class articles in my bot. It was a popular request and I finally implemented it as I was able to allocate some time. I added a new content type parameter that allows you to specify a category for A-Class articles. See the template for how to use. If there are any questions or issues with the results, let me know. -- JLaTondre (talk) 00:20, 8 January 2010 (UTC)

ratemath and empty talk pages

The problem with ratemath and empty talk pages has been fixed, thanks to help from AzaToth. This was what caused it – you can see why I was confused about what was wrong with my code. — Carl (CBM · talk) 19:54, 9 January 2010 (UTC)

Nice, thanks. Works fine now. --Robin (talk) 21:39, 9 January 2010 (UTC)

Additional; WoRC Request

I've received an additional request for the WoRC bot task. I'd like to get some additional input before implementing. If you wish, please comment at this discussion. -- JLaTondre (talk) 22:22, 11 January 2010 (UTC)

Computational complexity of mathematical operations

re: recent revert. I overlooked the definition of M(n) because it's buried in a specific table, yet used throughout the article. Maybe it should be moved out of the table in question? -kj (talk) 18:38, 30 January 2010 (UTC)

Yes, feel free to do so. I just reverted because what you wrote was incorrect; I don't object to changing the placement of that text. --Robin (talk) 23:34, 30 January 2010 (UTC)

Positive definiteness

Your comments are requested on a discussion about whether or not a particular page is a disambiguation page or a stub here. Neelix (talk) 20:06, 14 February 2010 (UTC)

DSPACE, etc.

Thanks for several corrections and a {{dn}} fix. I don't know why I didn't see Alternation (complexity)...

CRGreathouse (t | c) 05:56, 5 March 2010 (UTC)

No problem. You didn't see it because I fixed the disambiguation page for Alternation to list Alternation (complexity) instead of (algorithms), and created a redirect from (complexity) -> Alternating TM, after you were done disambiguating. --Robin (talk) 13:54, 5 March 2010 (UTC)

AM,MA

Hi Robin, thanks for the fix in Arthur–Merlin_protocol. I saw that the current condition for AM reads as follows (and is correct)

• if x is not in L, then $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.$

I wanted to note that it can be equally written as

• if x is not in L, then $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.$

However, the second condition seems to go well together with the x is in L condition, as 2/3 and 1/3 add up to 1. —Preceding unsigned comment added by Sg313d (talk • contribs) 07:37, 2 June 2010 (UTC)

I felt the first one contrasts better with the condition for x in L, since for x in L, the condition says that "there exists" something, I felt the condition for x not in L would look better if it said something like "for all". Both are correct though, and I wouldn't mind changing to the other definition if that seems clearer. Also, this way it looks similar to the definition of MA. --Robin (talk) 13:17, 2 June 2010 (UTC)

I decided to add both definitions, since there's no harm giving extra information. --Robin (talk) 13:50, 18 June 2010 (UTC)

I have marked you as a reviewer

I have added the "reviewers" property to your user account. This property is related to the Pending changes system that is currently being tried. This system loosens page protection by allowing anonymous users to make "pending" changes which don't become "live" until they're "reviewed". However, logged-in users always see the very latest version of each page with no delay. A good explanation of the system is given in this image. The system is only being used for pages that would otherwise be protected from editing.

If there are "pending" (unreviewed) edits for a page, they will be apparent in a page's history screen; you do not have to go looking for them. There is, however, a list of all articles with changes awaiting review at Special:OldReviewedPages. Because there are so few pages in the trial so far, the latter list is almost always empty. The list of all pages in the pending review system is at Special:StablePages.

To use the system, you can simply edit the page as you normally would, but you should also mark the latest revision as "reviewed" if you have looked at it to ensure it isn't problematic. Edits should generally be accepted if you wouldn't undo them in normal editing: they don't have obvious vandalism, personal attacks, etc. If an edit is problematic, you can fix it by editing or undoing it, just like normal. You are permitted to mark your own changes as reviewed.

The "reviewers" property does not obligate you to do any additional work, and if you like you can simply ignore it. The expectation is that many users will have this property, so that they can review pending revisions in the course of normal editing. However, if you explicitly want to decline the "reviewer" property, you may ask any administrator to remove it for you at any time. — Carl (CBM · talk) 12:33, 18 June 2010 (UTC) — Carl (CBM · talk) 13:00, 18 June 2010 (UTC)

Alright, thanks. --Robin (talk) 13:36, 18 June 2010 (UTC)

Quantum phase estimation algorithm

H Robin. Thanks for having a go at improving this article. However in doing so you have inadvertantly reverted some of my encyclopedic tone edits. Please restore these if you can in order to avoid the use of personal pronouns such as you and we and phrases that could be considered to be the opinion of the author: ( {{cn}} tags). Thanks. --Kudpung (talk) 04:10, 25 September 2010 (UTC)

Ok, I got rid of the "we" in the lead. I did not remove any of your {{cn}} tags, only a {{whom}} tag, because the previous line proves the assertion. --Robin (talk) 04:22, 25 September 2010 (UTC)

File:Decision Problem.png listed for deletion

A file that you uploaded or altered, File:Decision Problem.png, has been listed at Wikipedia:Files for deletion. Please see the discussion to see why this is (you may have to search for the title of the image to find its entry), if you are interested in it not being deleted. Thank you. The Haz _talk 04:10, 2 January 2012 (UTC)

Simon's algorithm

We have a random oracle relative to which BPP and BQP are separated. This is an improvement over the Deutsch-Jozsa algorithm separating P from EQP. The oracle needs to be quantum and nondecohering.

I think what this is saying is that given a quantum oracle (running in BQP time?), the classic algorithm can't solve the problem as efficiently as quantum algorithm. It's a stronger example of the power of QC than the Deutsch-Jozsa algorithm. I don't quite understand the sentence either, but if you have another idea about how to capture this concept, it would be helpful. I don't know enough about quantum complexity to craft a sentence myself. Skippydo (talk) 14:43, 19 August 2012 (UTC)

The first sentence is vague, but a fairly common interpretation of it would be that there is a random oracle separation between BQP and BPP. This is not known to be true, and conjectured to be false. The second sentence is OK, so I didn't remove it -- although I'll try to reword it to make it clearer. The last one about the oracle being quantum and decohering makes very little sense to me. If it just means that the oracle has to allow the quantum computer to make queries in quantum superposition, then that's part of the definition of what it means to give BQP oracle access. --Robin (talk) 15:07, 19 August 2012 (UTC)

Thank you for the explanation and the edits. You've been very helpful. Skippydo (talk) 20:29, 19 August 2012 (UTC)

File:Theoretical computer science.svg missing description details

Dear uploader: The media file you uploaded as:

• File:Theoretical computer science.svg

is missing a description and/or other details on its image description page. If possible, please add this information. This will help other editors make better use of the image, and it will be more informative to readers.

If the information is not provided, the image may eventually be proposed for deletion, a situation which is not desirable, and which can easily be avoided.

If you have any questions, please see Help:Image page. Thank you. Theo's Little Bot (error?) 09:16, 14 April 2013 (UTC)

ArbCom elections are now open!

Hi,
You appear to be eligible to vote in the current Arbitration Committee election. The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to enact binding solutions for disputes between editors, primarily related to serious behavioural issues that the community has been unable to resolve. This includes the ability to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail. If you wish to participate, you are welcome to review the candidates' statements and submit your choices on the voting page. For the Election committee, MediaWiki message delivery (talk) 14:05, 24 November 2015 (UTC)

ArbCom elections are now open!

Hi,
You appear to be eligible to vote in the current Arbitration Committee election. The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to enact binding solutions for disputes between editors, primarily related to serious behavioural issues that the community has been unable to resolve. This includes the ability to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail. If you wish to participate, you are welcome to review the candidates' statements and submit your choices on the voting page. For the Election committee, MediaWiki message delivery (talk) 14:09, 24 November 2015 (UTC)

ArbCom Elections 2016: Voting now open!

Hello, RobinK. Voting in the 2016 Arbitration Committee elections is open from Monday, 00:00, 21 November through Sunday, 23:59, 4 December to all unblocked users who have registered an account before Wednesday, 00:00, 28 October 2016 and have made at least 150 mainspace edits before Sunday, 00:00, 1 November 2016.

The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail.

If you wish to participate in the 2016 election, please review the candidates' statements and submit your choices on the voting page. MediaWiki message delivery (talk) 22:08, 21 November 2016 (UTC)

ArbCom 2017 election voter message

Hello, RobinK. Voting in the 2017 Arbitration Committee elections is now open until 23.59 on Sunday, 10 December. All users who registered an account before Saturday, 28 October 2017, made at least 150 mainspace edits before Wednesday, 1 November 2017 and are not currently blocked are eligible to vote. Users with alternate accounts may only vote once.

The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail.

If you wish to participate in the 2017 election, please review the candidates and submit your choices on the voting page. MediaWiki message delivery (talk) 18:42, 3 December 2017 (UTC)

ArbCom 2018 election voter message

Hello, RobinK. Voting in the 2018 Arbitration Committee elections is now open until 23.59 on Sunday, 3 December. All users who registered an account before Sunday, 28 October 2018, made at least 150 mainspace edits before Thursday, 1 November 2018 and are not currently blocked are eligible to vote. Users with alternate accounts may only vote once.

The Arbitration Committee is the panel of editors responsible for conducting the Wikipedia arbitration process. It has the authority to impose binding solutions to disputes between editors, primarily for serious conduct disputes the community has been unable to resolve. This includes the authority to impose site bans, topic bans, editing restrictions, and other measures needed to maintain our editing environment. The arbitration policy describes the Committee's roles and responsibilities in greater detail.

If you wish to participate in the 2018 election, please review the candidates and submit your choices on the voting page. MediaWiki message delivery (talk) 18:42, 19 November 2018 (UTC)

Your access to AWB may be temporarily removed

Hello RobinK! This message is to inform you that due to editing inactivity, your access to AutoWikiBrowser may be temporarily removed. If you do not resume editing within the next week, your username will be removed from the CheckPage. This is purely for routine maintenance and is not indicative of wrongdoing on your part. You may regain access at any time by simply requesting it at WP:PERM/AWB. Thank you! — MusikBot II ^talk 17:19, 28 December 2021 (UTC)

Proposed deletion of List of important publications in cryptography

The article List of important publications in cryptography has been proposed for deletion because of the following concern:

WP:NOTDATABASE

While all constructive contributions to Wikipedia are appreciated, pages may be deleted for any of several reasons.

You may prevent the proposed deletion by removing the {{proposed deletion/dated}} notice, but please explain why in your edit summary or on the article's talk page.

Please consider improving the page to address the issues raised. Removing {{proposed deletion/dated}} will stop the proposed deletion process, but other deletion processes exist. In particular, the speedy deletion process can result in deletion without discussion, and articles for deletion allows discussion to reach consensus for deletion.

This bot DID NOT nominate any of your contributions for deletion; please refer to the history of each individual page for details. Thanks, FastilyBot (talk) 09:01, 16 August 2022 (UTC)

Nomination of List of important publications in theoretical computer science for deletion

A discussion is taking place as to whether the article List of important publications in theoretical computer science is suitable for inclusion in Wikipedia according to Wikipedia's policies and guidelines or whether it should be deleted.

The article will be discussed at Wikipedia:Articles for deletion/List of important publications in theoretical computer science (2nd nomination) until a consensus is reached, and anyone, including you, is welcome to contribute to the discussion. The nomination will explain the policies and guidelines which are of concern. The discussion focuses on high-quality evidence and our policies and guidelines.

Users may edit the article during the discussion, including to improve the article to address concerns raised in the discussion. However, do not remove the article-for-deletion notice from the top of the article until the discussion has finished.

_{Piotr Konieczny aka Prokonsul Piotrus| reply here} 10:16, 31 January 2023 (UTC)