# 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.

### 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

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

thatmessage 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. :P )

Maybe you should consider reading this blog on the web… :)

Oh, I

amreading 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

knowingwhether 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/