About Us
I am Dick Lipton, a Professor of Computer Science at Georgia Tech. I have worked in the area of theory of computation since 1973. I find the whole area exciting and want to share some of that excitement with you. I hope that these blogs inform and entertain you. I hope that you not only learn some new ideas, hear some interesting open problems, but also get some of the history of the area. One of the things I think people sometimes forget is that research is done by people. One of my goals—perhaps the main one—is to get you to be able to see behind the curtain and understand how research works.
I am Ken Regan, also in Computational Complexity Theory at the University at Buffalo (SUNY). I have been delighted to help this blog since mid-2009, and now honored to join the masthead as an author. I have shared the same values and desires as Dick mentions—also attending to the personal side—and have found the partnership congenial as well as collegial.
Pip is both of us, and his story is here.
197 Comments
leave one →
Trackbacks
- The most important Theoretical Computer Science problem is inconsequential
- Da blogosfera: a carta recente de Alexandre Grothendieck « problemas | teoremas
- P ≠ NP ? [ Vinay Deolalikar from HP Labs Publishes His Proof to the Web, $1Million Clay Institute Prize May Very Well Await ] | Computational Legal Studies™
- One Heckler and My Answer | Sun Ju's Blog
- Are MOOC Students Cheating Or Mastering the Material? « Gödel’s Lost Letter and P=NP « Computing Education Blog
- Обработка ошибок и безопасные состояния в программировании | Yasik.org
- Blog Free or Die « Pink Iguana
- Bounded rationality: systematic mistakes and conflicting agents of mind | Theory, Evolution, and Games Group
- Frankl, My Dear : 1 | Inquiry Into Inquiry
- Frankl, My Dear : 2 | Inquiry Into Inquiry
- Frankl, My Dear : 3 | Inquiry Into Inquiry
- How to stay updated about big-data and analytics | Useful Stuff
- Frankl, My Dear : 4 | Inquiry Into Inquiry
- Frankl, My Dear : 5 | Inquiry Into Inquiry
- Frankl, My Dear : 6 | Inquiry Into Inquiry
- Frankl, My Dear : 7 | Inquiry Into Inquiry
- Frankl, My Dear : 8 | Inquiry Into Inquiry
- Frankl, My Dear : 9 | Inquiry Into Inquiry
- Frankl, My Dear : 10 | Inquiry Into Inquiry
- Frankl, My Dear : 11 | Inquiry Into Inquiry
- Inquiry Into Inquiry
- Animated Logical Graphs : 7 | Inquiry Into Inquiry
- Animated Logical Graphs : 8 | Inquiry Into Inquiry
- Animated Logical Graphs : 9 | Inquiry Into Inquiry
- Considerate Reason • 1 | Inquiry Into Inquiry
- Considerate Reason • 2 | Inquiry Into Inquiry
- Riffs and Rotes : 3 | Inquiry Into Inquiry
- Problems In Philosophy • 1 | Inquiry Into Inquiry
- Problems In Philosophy • 2 | Inquiry Into Inquiry
- Problems In Philosophy • 4 | Inquiry Into Inquiry
- Abduction, Deduction, Induction, Analogy, Inquiry : 3 | Inquiry Into Inquiry
- Blog Free or Die (graded) « Pink Iguana
- Kathryn Farley, Richard Lipton | Castwb
- Kathryn Farley, Richard Lipton | EssentialsEcho
- Kathryn Farley, Richard Lipton | Fitness Athlet
- Kathryn Farley, Richard Lipton | Column Diary
- Kathryn Farley, Richard Lipton
- Kathryn Farley, Richard Lipton - Forctr
- Kathryn Farley, Richard Lipton | Ac Stories
- Kathryn Farley, Richard Lipton | Dolilodge
- Kathryn Farley, Richard Lipton - On The Rise
- Kathryn Farley, Richard Lipton | ABC Featured
- Kathryn Farley, Richard Lipton | Bradspe
- C.S. Peirce : Information = Comprehension × Extension | Inquiry Into Inquiry
- I Wonder, Wonder Who | Inquiry Into Inquiry
- How To Succeed In Proof Business Without Really Trying | Inquiry Into Inquiry
- Architectonics of Inquiry : 1 | Inquiry Into Inquiry
- Differential Analytic Turing Automata : 1 | Inquiry Into Inquiry
- Objects, Models, Theories : 2 | Inquiry Into Inquiry
- Alpha Now, Omega Later : 3 | Inquiry Into Inquiry
- Alpha Now, Omega Later : 5 | Inquiry Into Inquiry
- Paradigms, Playgrounds, Programmes, Programs | Inquiry Into Inquiry
- Alpha Now, Omega Later : 7 | Inquiry Into Inquiry
- Slip Slidin’ Away | Inquiry Into Inquiry
- All Process, No Paradox : 6 | Inquiry Into Inquiry
- Propositions As Types : 1 | Inquiry Into Inquiry
- Duality Indicating Unity : 1 | Inquiry Into Inquiry
- Riffs and Rotes : 1 | Inquiry Into Inquiry
- One Hundred Statistics Inequalities – Algo-Stats
- Wherefore Aught? | Inquiry Into Inquiry
- Indicator Functions : 1 | Inquiry Into Inquiry
- Animated Logical Graphs • 9 | Inquiry Into Inquiry
- Animated Logical Graphs • 24 | Inquiry Into Inquiry
- Animated Logical Graphs • 28 | Inquiry Into Inquiry
- Finding a Needle in a Cactus Patch | Inquiry Into Inquiry
- Pragmatic Theory Of Truth • 23 | Inquiry Into Inquiry
- Animated Logical Graphs • 32 | Inquiry Into Inquiry
- Differential Logic • Discussion 3 | Inquiry Into Inquiry
- Architectonics of Inquiry • 1 | Inquiry Into Inquiry
- Differential Analytic Turing Automata • Discussion 1 | Inquiry Into Inquiry
- Animated Logical Graphs • 35 | Inquiry Into Inquiry
- Animated Logical Graphs • 36 | Inquiry Into Inquiry
- Animated Logical Graphs • 37 | Inquiry Into Inquiry
- Animated Logical Graphs • 28 | Inquiry Into Inquiry
- Animated Logical Graphs • 38 | Inquiry Into Inquiry
- Animated Logical Graphs • 39 | Inquiry Into Inquiry
- Animated Logical Graphs • 40 | Inquiry Into Inquiry
- Fourier Transforms of Boolean Functions • 1 | Inquiry Into Inquiry
- Animated Logical Graphs • 41 | Inquiry Into Inquiry
- Fourier Transforms of Boolean Functions • 2 | Inquiry Into Inquiry
- Pragmatic Semiotic Information • Discussion 20 | Inquiry Into Inquiry
- Animated Logical Graphs • 42 | Inquiry Into Inquiry
- Theme One • A Program Of Inquiry 19 | Inquiry Into Inquiry
- Theme One • A Program Of Inquiry 20 | Inquiry Into Inquiry
- Problems In Philosophy • 6 | Inquiry Into Inquiry
- Problems In Philosophy • 12 | Inquiry Into Inquiry
- Animated Logical Graphs • 45 | Inquiry Into Inquiry
- Animated Logical Graphs • 46 | Inquiry Into Inquiry
- Animated Logical Graphs • 47 | Inquiry Into Inquiry
- Animated Logical Graphs • 48 | Inquiry Into Inquiry
- Animated Logical Graphs • 49 | Inquiry Into Inquiry
- Animated Logical Graphs • 50 | Inquiry Into Inquiry
- Abduction, Deduction, Induction, Analogy, Inquiry • 30 | Inquiry Into Inquiry
- Animated Logical Graphs • 51 | Inquiry Into Inquiry
- Animated Logical Graphs • 52 | Inquiry Into Inquiry
- Animated Logical Graphs • 59 | Inquiry Into Inquiry
- Animated Logical Graphs • 60 | Inquiry Into Inquiry
- Animated Logical Graphs • 61 | Inquiry Into Inquiry
- Animated Logical Graphs • 62 | Inquiry Into Inquiry
- Animated Logical Graphs • 62 | Inquiry Into Inquiry
- Animated Logical Graphs • 63 | Inquiry Into Inquiry
- Animated Logical Graphs • 64 | Inquiry Into Inquiry
- Animated Logical Graphs • 65 | Inquiry Into Inquiry
- Animated Logical Graphs • 66 | Inquiry Into Inquiry
Your posts are just too good. And I like the way you write too. Very hard to find that combination in many tcs blogs. Do keep posting them. Keeps people like me who once had a brief glimpse of tcs want to keep reading.
Thanks for your kind comment.
Your posts are joyful to read. You really can share your excitement with your blog readers, and do it very well. Thank you for your effort!
This is truly amazing. Well written, narrative and absolutely delightful. A theory blog, I will surely follow, Professor.
I got addicted to all your blogs. You care for others a lot.
Best,
R.K.
Thank is one of the nicest comments I can imagine…thank you
rjlipton
I’m just telling the truth at my side which is I get happy when I see your new blogs at the aggregator and I come here to learn more; then it became almost a daily habit.
Awesome!
I have never seen a blog of such high quality.
The superb technical quality aside, it is also a pleasure to read
what has — it appears to me — been written by an absolute gentleman.
Wonderful. Thank you.
My deepest congratulations for your blog, which I find truly interesting and elegant, really well done. I’m consulting it almost every day. I am not aware of any other TCS blog having such a global quality (contents, explanation brightness, real life stories, graphical layout) and being updated with such a high frequency.
Thanks for your effort, and please keep it on!
Best regards,
Giorgio
Hello,
This is Armine Hareyan writing from http://www.huliq.com. I visited your blog and liked your content.
Would you be interested to send us a guest post on any of the issues related to the topics that you cover in your blog. We will publish it in our site http://www.huliq.com
In return with each guest blog we will give one link in the author’s biline back to your blog. We only ask that the guest post ( we prefer it be a news coverage, sources can be Google News, CNN, MSNBC, Yahoo News, BBC and others) be a unique story and not be published in your blog.
Please let me know if you may have any questions about http://www.huliq.com.
If you want to consult the topic with me first that’s perfectly fine as well.
Many thanks
Best regards
Armine Hareyan
http://www.huliq.com
I love your blog, Prof Lipton. You da man!
Hello Dick:
I think you should learn more about the new set theory history. We are right in the middle of a renewed interest in this history. A lot of work is being done, for some reason, in Spain and Mexico.
Above all read A. Garciadiego, BERTRAND RUSSELL AND THE ORIGINS OF THE SET-THEORETIC ‘PARADOXES.’ I don’t know where he is now. He was at Dibner for a while.
Godel’s theorems rely on the idea that there is logical content in the paradoxes. If there is NONE, his project is unmotivated.
And yet the new history shows that he was a very sloppy investigator when it came to finding out whether these “paradoxes” actually possessed logical content, or whether their compulsion was simply an artifact of their rhetoric.
I think if you read Garciadiego you will see that their compulsion was simply an artifact of their rhetoric.
Nevertheless, although not only the “paradoxes” had their critics but also, Cantor’s whole set theory notion (see particularly Grattan-Guinness on some of these unsung critics), constructivism forged ahead with new terms of art. Your term “computation” is one of these set theory generated constructivist notions. I think you will wind up concluding that it has no logical content.
It’s probably expecting too much for you to go back, look at Zeno again, and conclude that the trouble that “paradox” caused Aristotle was no trouble at all.
However, even the notes editors in the Godel edition often fault Godel’s sloppiness, his lack of inquisitiveness, the unclarity of his ideas. If you look at what Richard said about his own “paradox” (quoted in Garciadiego), you will see how inappropriate it was for Godel to mention this nonsense in his paper. And that is not the only nonsense in Godel’s paper.
You should ask yourself (and it is the million dollar question with regard to Godel’s theorems):
where is the constructivist intervention in Godel’s argument?
That is, where does he make an arbitrary intervention in his logic in order to keep his conclusions from becoming paradoxical? This was the method handed down by the set theorists.
Einstein, for one, used the method in constructing the relativity of simultaneity. He called his constructivism “practical geometry” and as I say in the last part of the article linked below, he used it to insert an undefined “natural” coincidence into the relativity of simultaneity. As you will see, this causes insurmountable problems for the relativity of simultaneity. I am gratified to see that this has put a monkey wrench in research into relativity.
I am interested in an identification of Godel’s constructivist intervention in his argument, at the same level of precision.
Identifying these constructivist interventions has become the project of 21st century inquiry. As you will see from the paper, it is going on with respect to many major ideas, as we boot constructivism out of our discourse. I am especially interested in the progress it is making with respect to both Motoo Kimura and Darwin. You will see the references in the paper.
Ryskamp, John Henry,Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas(June 17, 2008). Available at SSRN: http://ssrn.com/abstract=897085
Keep it up. Great post today!
I’ve been watching Star Trek since I was 6 years old and love science fiction.
I believe that P = NP. I wouldn’t bet a dollar though. It’s true and might take more than 1 lifetime to prove. Given the relevance…
Well, I’m working on it. Not that this is a scary news but it’s tons of fun.
Congrats on your link from Harper’s (http://www.harpers.org/#hbc-90005787)! (Though they likely intend irony, I enjoyed your post.)
thanks for your intellectual sharing, i enjoyed the reading very much indeed.
This page is a blast, I really appreciate what you are doing here. Too often it seems that the excitement of academia is locked behind the walls of pay journals and jargon.
Great blog. I would have bee searching for a long time a web site like this. Thank you
Thank you so much for running this blog.
I don’t deeply grok most of the topics you write on. But it opens a window into fascinating new territory that I occasionally venture into and derive a lot of learning and joy from.
It inspires me to see someone putting so much effort and producing quality work when there is no obvious economic incentive.
This had been one of my favorite blogs for a while. Much of it is difficult reading for me (parts are just plain over my head), but it’s fascinating stuff and for clear, genial presentation it’s a model.
And then I realized: you’re the professor who taught me Theory of Computation back at Yale around 1977. It finally connected when you mentioned working with David Dobkin.
Congratulations for the excellent blog. It is definitely one of my favorites. The areas of complexity and algorithms are fascinating and your blog emphasizes the beauty that they entails. Right now I’m attending Prof. Karp’s class in combinatorial algorithms and data structures. Thus, reading your blog is for me a mixture of pleasure and study. Thank you.
Best wishes,
Elói Pereira
PhD Student
Systems Engineering, CEE
UC Berkeley
Thanks very much. Must be great to be in Karp’s class.
Love your fascinating blog. Wrote a post today to recommend it. Thank you very much.
Hear hear! This is really a great blog. You tend to bring across many important and technical things in a very lucid and attractive way, and with nice personal stories: a lot of fun to read. I was warned about your blog by couple of your students: Atish and Danupon, and sure enough, it is addictive!
I learnt computation complexity by reading books only, and I don’t have a solid background in this area. But I am quite interested in the problem and NP=P, and I am so glad to find your blog which is dedicated to the problem.
I have written an article about permanent, Calculation of Permanent with new method (with complexity the same as the Ryser’s formula). I know this is not a very useful method, but I just would like to know if the article and the claim, with complexity the same as the Ryser’s formula, is indeed correct. If you can have a look and give me a some comments, it would be very great. Thank you.
I’m very happy to see much more helpful articles here.
Dear Mr. Lipton.
Considering the recent uproar about the P \neq NP proof I thought it would help many people to get an understandable explanation of what P and NP actually mean. Since I do a podcast about some scientific and social topics I thought it might be interesting to get an expert to try to communicate to “normal” people what all the fuss is about.
Looking at your writing I think you’d be perfect for this task, sadly I couldn’t find an email address here to talk to you directly, so I’ll try it this way.
If you might find the time to talk to me (via Skype or something similar) about P and NP please drop me an email to jgeuter(at)monkeycode.org. Thanks!
Thank you for your blog, very informative and engaging!
Dear Professor Dick Lipton:
I know that you are a great specialist in theoretical computer science。I have a procedure hp4.exe (in VC++,my many years job), which can calculate Hamilton Path from vertex 0 to vertex n-1 for any kind of undirected graphs, very quick, smooth, I have calculated almost 1 billion inputs, no fail. If you have interest, I can mail hp4.exe to you immediately. Only after you run the hp4.exe, then you can trust me. Then, we can exchange ideas!
I appreciate you if you can agree.
sincerely yours,
Lizhi Du
I am an associate professor in China, my email: edw95@yahoo.com
Lizhi Du:
LOL. Nice attempt at getting a trojan on Lipton’s box.
Your blog is definitely among the top sites on computational complexity &etc. I would rate it among Scott Aranson’s and Lance Fortnow’s blogs’ league… These few websites have piqued my interest in the field and hope they continue to do so.
Your article on Deolikar’s proof was quite informative… Unlike newspaper reports of it being solved!!!
Best wishes
Shabbeer Hassan,
Bangalore,
India.
Dear Prof Lipton:
first of all, thanks for your blog which I enjoy reading on a regular
basis. – I decided to start my own blog called “Order, topology, and other
basics” in which I want to write musings on topics of point-set
topology and order theory.
I took your blog on my blogroll and want to ask you if you could take
me on yours? That would be very kind.
Many thanks,
Dominic
PS: sorry for posting this here, in what seemed like a fit of Google illiteracy, I was unable to find your e-mail address.
Dear Professor Lipton:
I know that you are a great and busy scientist。I have a procedure hp4.exe (in VC++), which can calculate Hamilton Path from vertex 0 to vertex n-1 for any kind of undirected graphs, very quick, smooth, I have calculated almost 1 billion inputs, no fail. Now, I want to mail hp4.exe to you . Only after you run the hp4.exe, then you can trust me. Then, we can exchange ideas!
I know you are busy, you only need to let one of your students to do it!
This procedure can calculate Hamilton Path in polynomial time for all kinds of undirected graphs, no matter how dense they are or how sparse they are or how uneven their edges’ distribution is. Utterly correct and quick, no exception.
This procedure works very smooth for all kinds of undirected graphs, i.e., for graphs with the same number of vertices, except for a little trivial instances which are very easy to calculate, their running time are very close to one another. So using my procedure, there is no graph to cost much more time than others, i.e., there is no “dead angle” for my procedure.
I assert: my procedure hp4.exe is the best one, the excellent one, the wonderful one. No other procedure for finding Hamilton path can be as good as my hp4.exe in all of this world!
Sincerely yours,
Lizhi Du
College of Computer Science and Technology,
Wuhan University of Science and Technology, Wuhan 430081, P.R. of China
Tel: 86 13554171855
My email: edw95@yahoo.com
Again I know you are busy, you only need to let one of your students to do it!
Your site has allowed me to look in another way at many things. Thanks, Dick!
Hello,
Your RSS feeds do not work (the last update is galactic algorithm), i missed three updated due to that… 🙂
Thanks alot and thanks for that great blog!!!!!
They work for me (main one and comments, although the latter sometimes misses comments due to a 10 item cutoff). I often force update my RSS’s rather than wait for the schedule though.
You are right, the rss works – just my foxi did not update them 😉
Like I mentioned in November, the comment RSS feed keeps on occasionally losing comments due to this 10 item cutoff. However I have the impression it’s rarely missing by much. I don’t know how this really works, but is there any chance you could increase it to 20 or so?
Thank you for the most excellent mathematical blogging!
I knew Zeke Zalcstien in the late 70’s and early 80’s. If you could let him know I would like to say hi, I’d appreciate it. I haven’t been in contact since then. I’d tell him “It is around the corner.” He’ll know what I mean. We were both getting deep into nutrition.
Thanks.
P.Bauter, pbauter@net66.com
Georgia Tech doesn’t pay enough:
Dick, this blog is an outstanding resource. Thanks. One quibble. How disappointing that it includes advertisements. For example, almost all the others on your blog roll choose not to. While I don’t want to begrudge you the extra income for the undoubted extra effort required to put it together, I just want you to know that it does spoil the enjoyment of reading it just a little.
Denise
A Fan
I can turn them off by upgrading etc. Will consider doing that.
love the site. You might find my youtube video on Georg Cantor interesting because it overlaps your posts on Turing, Godel, et al. a little:
the video is on the deeper philosophy of Georg Cantor: http://www.youtube.com/watch?v=_Ds6XtElf3E check it out in HD. I’d love to know what you think, Professor.
I’ve been a reader here for a good while now. Big fan, too. It’s a great place to hang out. I haven’t come across any contact information anywhere though, so I’ll just put this here instead. I apologize that by doing this ahead of time, since it has the unfortunate effect of spamming the about page with an external link. I think you’ll see it’s potential though.
I just stumbled across Stack Exchange’s Theoretical Computer Science forum (in beta). It’s something I feel has the potential to be a very useful place to ask such questions. And by reading your stuff here, I know you and those who help you could help bring it to life. Akin to Jon Skeet’s ability to answer almost any C# question on Stack Overflow. This is the site: http://cstheory.stackexchange.com
If you’ve never heard of Stack Exchange, check out http://www.stackoverflow.com to see one of their sites in action. This example in particular is a wonderful resource for programmers. I’d love to see an equally good place for CS theory. So check it out if you have the time. At the time of writing this, there’s a popular question on where people should go for help on their research and publishing. So these kinds of questions and answers can help out so many students involved in theory in a very practical way.
http://romvf.wordpress.com/2011/01/19/open-letter/
Would love to hear your comment on this. 🙂
Nice blog Prof.Lipton. it will be my pleasure to start following this blog..!!!
–U.
You are cooler than every rapper I know.
Your post on Ed Clarke’s approach was a nice read.
I hated TOC in college. Age has tempered my juvenile perceptions on the most fundamental faculty of computer science.
I saw that chess program in 1972 – it was one of the best things I ever saw on tv. And so simple!
I remember back then in 1999, a dos chess game. The computer was so hard to defeat. Do you think which is better, computer or the game creator? can computer defeat the game creator?
Very good blog. I like reading posts.
Have a look a my blog at http://mathematicsbhilai.blogspot.com/
Dear Prof. Richard J. Lipton,
What will be the effect of deciding complexity of the Problem of Isomorphism of Graphs on problem of deciding P = NP (or, P != NP) ? Where do you expect this problem will go (i.e. in P category or NP Complete category)?
Best Regards,
Dhananjay P. Mehendale
There will be no effect of deciding complexity of problem of “Isomorphism of Graphs” on problem of deciding P = NP (or, P != NP) as this problem doesn’t belong to set of NP complete problems. Thanks.
If you believe in Cantor, what is your answer to the following questions?
Consider a sequence of sets with increasing cardinality:
o
oo
ooo
…
Enumerate the elements of the sets
1
1,2
1,2,3
…
Is there a limit set, omega say?
Enumerate the elements of the sets
1
2,3
4,5,6
…
Is there a limit set, the empty set say?
Enumerate the elements by superscripts like in the first case and by subscripts like in the second case.
Is there a limit set? What kind of set is it?
Regards, WM
Dear Dick Lipton, I would like to thank you for your research and for sharing your views and ideas. I came across your blog just two days ago and have spent the past two days trying to formulate a “cultural project” which presents research as art. I am a student of a MA in Cultural Production program at the University of Salzburg and I also compose electronic music using the computer as my instrument and “field” recordings as many of my sounds. This project I am dreaming up would involve using some of your ideas and research as tools for addressing problems in society. The research I would do based on your post on Erdös and the Quantum Method would be presented as non-text archival audio samples (placed on a online archive for people to download and use for free) along with musical interpretations of the results (This would be sampling research for artistic expression as an experiment). I am deeply interested in collaborating with you in some way. Please let me know what you think! I want to make this project happen. :))
ps. what is the best way to establish communication with you?
oh! i forgot to mention, i failed college algebra 3 times before I finally passed the course on the 4th try. i would have never imagined i would use math and quantum theory methods as metaphors for society and as proposals for creating awareness of a civil society. however, at some point, i began “doing the math”, and recently referring to humans as homogeneous polynomials: finite with variables and constants; operate through addition, subtraction, multiplication (and division as a metaphor for problems in society). i realized we are walking math and therefore walking possibilities, and positive/ progressive possibilities for that matter. seeing potential for an active socially conscious civil society is what drives me to do this project; connecting these ideas to composition methods of electronic music using the computer as an instrument is my intuitive creative expression and need.
both/and statements: this is art with a cause. “causes” create art.
(reflections on the purpose of art)
thanks again for your time.
Regarding the RSS comment feed 10 post cutoff problem which I’ve mentioned above, as well as in another post. (I feel like I’m nagging, but on the other hand no one’s ever responded.) Apparently this is a known problem
The solution for WordPress seems to be to ‘Amend “Syndication feeds show the most recent” in Admin/Settings/Reading.’
Could someone please increase this to something more reasonable for the current comment volume? I checked the feed just before turning off my laptop last night, and when I just got up I was happy to see there were only 8 new comments so I could see them all in the feed…
I cannot resist posting again about this silly feed business: Strangely that message hasn’t showed up in my feed, despite it being relatively quiet in the intervening time. I wonder if it has something to do with being held up in the spam filter (I put a little too many links in it). So I cannot help but hypothesize an explanation: The feed shows the latest comments by posted date instead of by when they actually show up publicly, meaning that if more than 10 other posts are made before it gets out of the spam filter, it will not appear in the feed at all, no matter how often it is checked.
(Now waiting for it to suddenly appear in my feed anyhow, voiding my hypothesis. 😛 )
Maybe you should consider reading this blog on the web… 🙂
Oh, I am reading this blog on the web. I am talking about the comments, not the main posts themselves, which don’t come anywhere near often enough to trigger the cutoff, and which besides are listed sorted in the archive so I could find them even if it happened.
Without the RSS comment feed (or the blog comment list on the right side, which seems to also be just 10 comments, although I am almost sure I saw it increasing briefly during the Deolalikar discussions) I don’t know any reasonable way of knowing whether there are new comments. Even checking recent posts by hand doesn’t work for new comments to really old posts.
Actually I did mean the comments, not the posts. There’s a possible confusion because you can say “to post a comment” and as a francophone I’m not aware of the usage. I think a comment limit of 20 to 25 would do better. It would prevent us from missing sporadic comments on old posts. Comments on new posts are less likely to be missed since we can always use ctrl-F to search the page for the current date. 🙂
Sigh, it has been silent lately, but there it starts overflowing again, like whenever a troll and a crank feeds off each other… sorry for the grumpiness.
Since I have heard no comment from either Prof. Lipton or Regan, not even to say they do not wish to do this, I wonder if I have failed to make it clear – the above suggestion if it is to be done must be applied by the blog authors, it cannot as far as I know be achieved by the readers.
Dick, I don’t know if I ever told you this. But every conversation I’ve ever had with you has been a privilege and a pleasure. Your mental energy and enthusiasm is exhilarating, inspiring and staggering. My brief time with the more theoretical aspects of computing was long ago but I truly enjoy those patterns of thoughts, even though I spend most of my time on practical aspects of how to build better siftware, cheaper. Thanks for this blog. It is like I get to have a conversation with you anytime.
Keep on thinking!
Jeff
It is a very nice website you have here. I will return!
A couple of years ago, I wrote a “paradox”, that you might find interesting. Have a look: http://blogoff.simonjensen.com/#post4
A friend of mine recommended your site, and asked me to ask for your opinion. Hope yo can spare a moment.
Best regards,
Simon Jensen
And there I go again, opening tabs with all recent posts to find all the interesting comments which get lost beyond the cutoff limit I’ve nagged about before above. (It’s beginning to look like all I say here, isn’t it.) Except of course I have no idea how to find the ones in non-recent posts.
(The comment sidebar limit increasing to 15 recently has helped a bit, but now that got overflowed too… the RSS limit seems still to be 10.)
Never mind, I just unsubscribed instead.
This blog is just COOOOOOOLLLLLLLLLLLLLLL. Please, keep it alive!
Dear Pip,
I recently stumbled upon and became curious about the P=NP problem. The stumbling occurred when I took a seminar course in the neighboring arts and technology department along with an advanced algorithms class in my CS department. And the muses were kind enough to give me some ideas for my seminar report titled: “Schrodinger’s Cat in flatland”. Although trembling with fear at the idea of presenting such a first cut work as this to an expert such as you, may I ask for a few minutes of your precious time to read and comment on this document?
It is available here: https://docs.google.com/document/d/1JV0Ey3wY71x2RqFP5wIRcTtyo9QPzZzq_GuB_txax5E/edit
Sincerely,
Arun
great blog!
This is the best idea about integer factorization, written here is to let more people know and participate.
A New Way of the integer factorization
1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known integer.
True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
How do I know "k" and "y"?
"P" is a factor of "N",GCD(k,N)=P.
Two Special Presentation:
N=5287
1+2+3+…k=Ny
Using the dichotomy
1+2+3+…k=Nrm
"r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)
"m" is Square
(K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)
(K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)
(K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)
(K^2+k)/(2*256)=5287*1.75 k=2176(OK)
K=2176,y=448
GCD(2176,5287)=17
5287=17*311
N=13717421
1+2+3+…+k=13717421y
K=4689099,y=801450
GCD(4689099,13717421)=3803
13717421=3803*3607
The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!
True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
More details of the process in my G+ and BLOG.
My G+ :https://plus.google.com/u/0/108286853661218386235/posts
My BLOG:http://hi.baidu.com/s_wanfu/item/00cd4d3c5a2fd089f5e4ad0a
Sir, where might I find a blog or accessible book on discriminants? I want read up a little bit more before I teach my kid how to solve quadratics. I am trying to find material that puts HS school algebra into a little more perspective by taking a tid-bit and running with it a little bit. Best regards on a fine blog. Shane
Hello,
I don’t understand why you’re using https protcol to publish the blog. Thanks for it.
Way cool! Some extremely valid points! I appreciate you
writing this article plus the rest of the website is extremely
good.
Hello Dr. Lipton,
I am currently running a crowd funding campaign for my upcoming educational game Sweet Math. I was wondering what is the process to get a story out on your blog.
Here’s more information about the game itself: http://www.kickstarter.com/projects/89952638/sweet-math
—
For those of you who think education is a key to make the world a better place check out our educational game Sweet Math. We are currently at 69% of our funding goal and the campaign will end on November 14th. We accept donation for as low as $1. http://www.kickstarter.com/projects/89952638/sweet-math
The game let player practice arithmetics with their entire family.
I wanted to make a suggestion on a topic. This was the first synthesized music created by Wendy Carlos in the 70’s. I once built my own moog synthesizer out of amp chips, creating seven adjustable oscillators whose sub tone volume could be adjusted. I was going to use Flip Flops to jump octaves. Instead I started hanging out in a friends band that had the real thing.
http://wintersbutterfly.com/2014/01/02/switched-on-bach/
I have been working on a chess database structure that is useful for solving chess as it can be pruned to only store winning moves but will still allow fast access to positions and can keep track of losing paths of play without storing every losing position. I’d like to get a real credible person’s take on this approach. Would you be willing to discuss it with me?
Somewhat off the topic, but I am at my wit’s end looking for an answer to a problem that has been bugging me for over 6 years. I am a computer scientist with an extensive math background, even having taken a course on computability with Martin Davis at NYU. So it bothered me when I was reading a novel that referred to Chaitin’s constant, and I had never heard of it. Since then, my interest in such things has been rekindled. My problem is, I’ll be d***ed if I can remember the name of the book. It was sort of a techno-thriller, and Chaitin’s constant was sort of a key to get into something. Can you or your readers help me with this. Oh, and BTW – great blog!!
Dear Prof. Lipton, thank you for sustaining this daringly intellectual blog! I have a philosophical math question which I wanted to ask here, if I may. Here goes:
Math is a system of knowledge that is unambiguously stored within an
“accounting” language which underlies all work ever written on the subject,
regardless of its form (symbolic, English, hybrid, etc).
The uniqueness of this underlying formal language is manifested in
the consensus amongst scientists when they go about their daily
communications.
That language is—by choice or necessity or taste, but certainly by agreement—acyclic:
It begins with axioms (of Set Theory) and grows with operations (of Formal Logic).
Acyclic graphs (equivalently formal systems) are not the only ones we know.
Systems of truth can be circular—as if suspended in air without axioms—and
their sophistication can be accomplished by refinement as opposed to growth.
This is what we call CSP problems in Computer Science.
Why is that we study formal systems with no beginning or end (CSP problems
in combinatorial optimization), but we use a language to describe
our findings (Formal Logic) which is an acyclic infinite system?
This question rings familiar when you put it in the context of two painful paradoxes
in math: the search for correlation-cause-effect resolution and the question of existence
of one-way functions.
Could it be that our choice to use an axiomatic language to talk about math
is creating singularities: one at the place when information comes into
math (the act of observation) and at the other end of the math universe
(the term for the “unknown” in math as language—randomness).
Could the resolution of both paradoxes simply be to rethink the
language of mathematical expression so that those two open questions
are collapsed into one and converted into a theorem—thereby going
from two conundrums to one result, or (-1) + (-1) = +1.
Here’s where this problem emerges in practice:
I find it odd that experimental sciences (when they are correct) report:
“The observations show a correlation between … and we are going
to use some side theory to disambiguate between cause-and-effect.”
What side theory?
The very side theory they are appealing to is Math and Math resolves their
meaningless and inane (due to cognitive bias and short historic memory)
question (of “Is correlation cause or effect?”) into another
meaningless one, which is the collection of paradoxes intrinsic in
Math—the provider of the answer—as an axiomatic language.
But if Math wasn’t serving to the asking experimentalist and rather aiming
to build a language that explains everything as seen and observed and testified to
by its users (people), in a consistent impartial and non-arguable manner, it would have
to offer a new tool to record and reason about correlation without breaking it
into cause and effect. No?
Thank you so much,
Petar
I would like to add a further refinement of my question, to make the problem even more visible:
The issue is that when Mathematician think about math they find the notion of “double-checking” everything from axioms to present interests inhumanly difficult: and it is. But this is the wrong place to look.
That path (axioms to modern interests) is the path of history. But the path through which Math is understood by a person (the consumer of it) is not historic, rather it is through their mother tongue (whatever it may be) which as Chomsky tells us is a cyclic infinite formal system. Not acyclic.
That’s all there is to it.
Because Math doesn’t care to check back and “defragment”, it is sticking to this acyclic system of axioms+logic which is simply—ironically in math’s own terms—a local view on a large manifold (the formal system of truth), which is slightly incorrect at the fringes, the way a tangent space is not accurate away from the focus. And these inaccuracies manifest themselves into ever more tightly phrased problems of the Clay Math Institute.
They are Math language closing in on its own contradiction. Beautifully,
the process of abstracting a few very hard open problems is—surprise—Occam’s razor in reverse (for physicists, this is “unification in reverse”).
I think the picture is simple.
To put it yet differently: How come no one ever asks why Turing presumed that a machine has input and output? If the idea is that his machine models the physical universe, then what is the I/O a metaphor for? This is a cognitive slip up, because we all tend to see (and think) of objects as modular and “in front of us”, but the world is all around and a model of it will not have an input and an output. It would be a closed system.
Closed systems are symmetric objects, by definition. Input/output devices are not. They are the epitome of directionality. Isn’t that puzzling?
Math has already tinkered with this insight in the form of Choiceless Polynomial Time. But it doesn’t seem to have been used for the right question.
I thought to share with you the following recent article related to the SAT problem : http://arxiv.org/abs/1602.04955 … Greetings !!
Hi there,
I’ve been reading and thinking a fair bit about Cantor and I came across your post about “counts” and “uncounts”. You very much seem like the kind of person I can ask a question of so… I’m currently a count I’m afraid – I have some justification that I presume must be wrong but I don’t understand why as it seems rather simple – could I tell you so perhaps you can explain where my mistake is and maybe convert me back to the good side?
Thank-you,
Jim
I have published ‘A SHORT PROOF THAT NP IS NOT P’ 2 years ago (a copy can be got from P-versus-NP page. I am confident that my proof (3 pages) does not have a fundamental flaw. So, I am wondering why I have no comments.
Sincerely,
Dr. Viktor Ivanov
I (as many others) was citing R.J.Lipton report 63, 1976 for years having no acces to it. Recently i’ve got it and i am puzzled with it. As a straightforward person i try to compose an explicit Petri net with k blocks that strongly computes 2^{2^k} from 1. I ask R.J.Lipton to invite me as a visiting professor for a couple of months to accomplish this task together.
Hi, Professor Lipto + Professor Regan = Pip:
I have enjoyed and have found most illuminating the several blog posts from Pip that I’ve read. How do I get information about them regularly?? (OK, I see below the button that asks me to fill in my details and asks me to confirm that I want to to be notified about new mails. Am about to do that).
Professor lipton, I’m a math hobbyist. I wonder what a person out of the academic world should do, if he discovered a fast algorithm to factorize or an algorithm that solves a complete NP problem, or any valuable mathematical discovery …
I mean: who should I say? what should I do?
Thank you for your attention and sorry if I take advantage of your kindness
Carlo Ceccarelli
Did-this-guy-solve-P-vs-NP?
https://www.quora.com/unanswered/Did-this-guy-solve-P-vs-NP
A curious idea that NP is simply equivalent to #P. Complete correctness of programs for NP (zero chopped subspaces, zero randomization) implies true equivalence with #P, because, All satisfying solutions are acceptable as answers from the program. Inequality with #P would imply NOT all solutions are answers, contradicting correctness.
,
Can I send a P vs NP paper for review?
good morning, there is actually a more interesting question than the erroneous Cantorian conclusions. The question is if real numbers exist or at least are conceivable conceptually. The answer is no. However, I’m not here to make controversy. I’m looking for Poincare’s observations on the diagonal proof. Wittgenstein mentions them but I can’t find a trace. I was wondering if you can help me.
Thx in any case