LaTeX Comment Removal Tool (for arXiv)

Recently, I went through several iterations of perfecting a script I wrote for automatically removing the comments from LaTeX source files. It seems that in most cases, people don’t care about submitting source files to arXiv with comments; however, for those of you who do, this might be a handy tool. You can find the script in this Github repo.

I’ll copy the same disclaimer that is in the repo:

Disclaimer This tool has not been widely tested for many types files. There may be bugs/unintended deletions depending on the file. The author(s) do not hold responsibility for any unintended results that may occur while using this file. We encourage you to help us improve this tool by submitting pull requests.

If you do somehow find this useful, please consider improving the script (especially if you do need to adapt it to suit your files) by submitting a pull request!

Advertisement
Posted in Code, Uncategorized | Tagged | Leave a comment

Paper and Puzzle a Day 9

Hello 2020! It’s been 3 years since my last post (3 years!!). It would’ve been poetic if I posted on Dec. 2, 2019 with a third rendition of “Where has the time gone?” but alas, I missed that opportunity last year. But, regardless, I am back! Perhaps when I am not chugging through paper deadlines, I will make a post of what has kept me from blogging for such a time (if I, myself, even know…).

Now, onwards with our scheduled program…

For my paper of the day, I feel obligated to first report on the now #oldnews of 2019 regarding the resolution of the Sensitivity Conjecture by Hao Huang. As countless other blog posts have stated, this result is truly extraordinary and I encourage all of you to read Huang’s elegant proof. The main proof is only 3 pages (3 pages!!).

Now, the puzzle.

I’ve been reading this book called The Moscow Puzzles by Boris A. Kordemsky (Edited by Martin Gardner) as a method of de-stressing from my deadline chugging. There are many nice puzzles in this book and certainly ones that require quite a bit of ingenuity (and the prose is also hilarious at times). For those who have done contest math, although some of the problems may seem easy, I still encourage you to read the book since there are lots of problems that are different in style from those that appear in contests.

I particularly liked the following puzzle from the book:

A work train, made up of a locomotive and 5 cars, stops at a small station. The station has a small sliding that can hold an engine and 2 cars. 

A passenger train is due. How do they let it through?

Screen Shot 2020-02-04 at 6.52.47 PM.png

Pg. 34 of The Moscow Puzzles

The reason why I liked this puzzle was because the first reaction I had was: The problem is poorly defined. What can the train do, can it go backwards, CAN IT FLY? And then, I realized I’ve worked for too long in TCS, and it is an important life skill to know that trains can, in fact, go backwards… Highlight the below space for the answer:

Copied verbatim from The Moscow Puzzles: The work train backs into the siding, which can hold its rear 3 cars. Uncoupling them in the siding, the rest of the work train goes forward a sufficient distance. The passenger train comes up and couples on the 3 cars left by the work train. It backs up on the main track. The work train backs up into the siding, which will now hold its engine and the remaining 2 cars. The passenger train uncouples the 3 cars it took from the siding and goes through. 

Posted in Paper and Puzzle | Leave a comment

Babai’s Updated Results–Graph Isomophism Still Solved in Quasipolynomial Time

Many days overdue on this post but I felt obligated to post this for posterity’s sake (even at woefully so late a time) because the previous post on my blog no longer holds. Laszlo Babai has (since 9 days ago…) posted a fix to his timing analysis so that his graph isomorphism test now once again runs in quasipolynomial time. You can see the announcement here and the updated paper here.

Here are also a short blog post written by Harald Helfgott and his article on Babai’s algorithm for solving GI in quasipolynomial time. The article is currently written in French but it looks like it might be translated into English soon.

Posted in Algorithms, Math | Tagged , | Leave a comment

Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP

Even after today’s retraction of quasi-polynomial time for graph isomorphism László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time. Today Laci posted a retraction of this claim, conceding that the proof has a […]

via Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP

The original letter explaining the retraction of the quasipolynomial claim can be found here. As explained in the blog post above and in the letter, the modified subexponential result is still very significant.

Posted in Algorithms, Math | Tagged , | Leave a comment

Where has the time gone? (Part 2)

It is once again that time where I bemoan all the months that have passed since my last blog post. True to character, it has again been 8 months! 8 months! I think along these 8 months, I’ve lost some of my original motivation for starting this blog in the first place, which is wanting to share things I find interesting (mostly TCS but I swear I have other interests also). But here’s to bringing it back and here’s to introducing some new topics that are (*gasp*) not math! Here’s the intended changes for the new year, that will be soon upon us.

  1. More math! I just started being a PhD student…finally! With everyday bringing in more exciting topics and things I learn. So expect more rigor and more math. And hopefully still simplicity (or pseudo-simplicity…).
  2. What I’m reading. Here’s to experimenting something different. I’ve never really posted anything about what I’m currently reading. But I like to read. And I have opinions. And this is a blog. So these things seem to complement each other in ways I haven’t considered before. I’ve recently started reading Blind Spot: Hidden Biases of Good People which I’ve heard mixed reviews about (mainly whether it offers more insight than what’s standardly known by people interested in this topic). I guess we’ll see what my opinions are shortly!
  3. Athletics. Music. Art. I have this unfortunate penchant for learning new things much more than mastering old subjects (which I’m also trying to be better at this new upcoming year…) Seems like resources I find helpful in learning said new subjects might be useful to other people. In this aspect, I’ve started learning the ukulele–maybe also guitar–so expect good ukulele tutorials from the web. Also, as I try to hone my very mediocre skills at the drums, piano, and viola–also expect things on these topics. Also, I’m trying out the bootcamp life (or pseudo-one-hour-long-bootcamp) so perhaps I’ll also post some exercise things.
  4. Life. Maybe I’ll talk a bit about life as a PhD student. And maybe thoughts about the process and the institution.
  5. MIT. It’s about time I write a bit (just a tad bit) about the place I’ve now spent close to 6 years at! And still loving every minute of it.

So now that I’m setting a goal to discuss all and everything that is interesting to me at the moment (and hopefully also interesting to you or you wouldn’t be here, would you?), I’ll hopefully be able to keep a more regular posting schedule. Here’s once again to a new year and a new blogging initiative!

 

Posted in Thoughts | Tagged | 2 Comments

Where has the Time Gone?

Hello 2016! As WordPress politely informed me today, it’s been 8 months since my last post! 8 months! Where has the time gone? I would say I’m again making a New Year’s resolution to blog more, but it’s no longer January…no, not even close. It’s already April!

On my end, the past 8 months was full of agonizing over grad school essays, mad rush towards writing results, mad rush to submitting applications, and, finally, a month of waiting and more waiting, which I say is probably worse than all the rushing and stress of the months prior. But it’s April! And I have a host of amazing, amazing schools to choose for grad school. But then, in typical fashion, comes a month of worrying over choices, of comparing every minute detail between the schools. But no more! I will be going to the place that will best fit my research interests, where I will hear about problems and solutions from some of the best researchers in the field. Where the feeling of excitement over solving hard challenges doesn’t fade, where people work and sleep at odd hours, and where nerdiness prevails. I hope that wherever I end up will make me feel with absolute certainty that I made the right decision by turning my back to the allure of Silicon Valley with all its sparkling glory two summers ago, exchanging that lifestyle for a different type of fun and a different type of nerdy.

But enough about me, to ring in my new New Year’s Resolution (hey, it’s snowing outside so we could believe it’s New Year’s if we try reaaaally hard), I’m going to talk about some of my favorite blogs. You might have heard of some of them:

  1. Shtetl-Optimized: This is probably the blog you have heard of/read before. But there’s a reason why it’s so popular and a reason why it’s on the top of my list. Scott Aaronson’s humor, very candid discussions, eloquence, and breadth of scientific discussion on his blog is unparalleled. Here’s a snippet of a post he made in January (regarding his daughter’s third birthday): 

    Lily: Why is the world spinning?
    Me: Because of the conservation of angular momentum.
    Lily: Why is the … consibation of amomomo?
    Me: I suppose because of Noether’s Theorem, and the fact that our laws of physics are symmetric under spatial rotations.
    Lily: Why is…
    Me: That’s enough for today Lily!  Link to post

  2. Gödel’s Lost Letter and P=NP: I think I’ve quoted several articles from this blog already. If there is a major scientific breakthrough in computing, then an article will appear on this blog within the next few hours and it is usually one of the most comprehensible and yet informative articles on the topic. This blog has a combination of news-like topics which discussions of esoteric problems in computing. It has a bit of everything, all discussed in an engaging and readable way. Plus lots of puzzles!
  3. FiveThirtyEight: I guess some would say this is more website than blog but it has that blog feel to me. Nate Silver’s great. His analysis is great. I’ve been reading his analysis for the primaries when I should have been working on my thesis.
  4. Terence Tao’s Blog: I usually don’t like very technical blogs (ironic isn’t it?) But Terence Tao explains concepts wonderfully, especially if you want a summary of a long and intricate paper (like the explanation of Zhang Yitang’s work on the Twin Prime Conjecture and related background). Beware, not for the faint of heart.
  5. Theory, Evolution, and Games: I had an interest in evolutionary game theory at some point in the past. I still do, and this blog has some interesting articles.
Posted in Uncategorized | 1 Comment

Four Weddings And A Puzzle

Interesting post about fair scoring with stakes involved. As it is, given rational players, I don’t think the show should exist at all. At least, I don’t see a rational incentive for players to rate other weddings any score other than 0. But perhaps, there’s a way to amend the voting scheme so that there is an incentive for non-zero voting.

Gödel's Lost Letter and P=NP

“Four Weddings” is a reality based TV show that appears in America on the cable channel TLC. Yes a TV show: not a researcher, not someone who has recently solved a long-standing open problem. Just a TV show.
22258_4W_302_Group_1

Today I want to discuss a curious math puzzle that underlines this show.

The show raises an interesting puzzle about voting schemes:

How can we have a fair mechanism when all the voters have a direct stake in the outcome?

So let’s take a look at the show, since I assume not all of you are familiar with it. I do admit to watching it regularly—it’s fun. Besides the American version there are many others including a Finnish version known as “Neljt Ht” (Four Weddings), a German version called “4 Hochzeiten und eine Traumreise” (4 Weddings and one dream journey), and a French version called “4 Mariages pour 1 Lune de Miel”…

View original post 902 more words

Posted in Uncategorized | Leave a comment

Paper and Puzzle a Day 8

Again, I’ve been slightly lax on posting a puzzle and paper a day. Here I am picking up the slack once again. First, a paper. I’ve been reading up on cache-oblivious algorithms recently. Cache-oblivious algorithms are optimal algorithms that do not depend on hardware parameters such as cache size. The paper that introduced such algorithms was presented at FOCS 1999. The paper presents among other popular cache-oblivious algorithms, funnelsort, which stands out the most in my mind. The paper is somewhat math intensive but is a pretty easy read.

Now, the puzzle:

One hundred prisoners just arrived in prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst themselves. Each cell has a window so the prisoners will be able to count the days. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The light bulb is initially switched off. The prisoner may observe the current state of the light bulb. If he wishes, he may toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a strategy that will guarantee their freedom?

The answer to Day 7’s puzzle is the following (highlight to show the answer):

The prisoner who is determined first to go will declare “Red” if she sees 4 blue hats. Otherwise, she declares “Pass.” If she declares “Pass,” then the rest of the prisoners will know that at least one of them has a red hat. Then, the next prisoner will declare “Red” if the prisoner sees all blue hats among the remaining prisoners. Otherwise, the prisoner will declare “Pass.” In this way, only the first prisoner will declare wrong for the only case when all prisoners have blue hats.

Posted in Paper and Puzzle | Tagged , , , | 1 Comment

Paper and Puzzle a Day 7

I’ve been reading up more about hinged dissections and came across a shorter paper than the one I mentioned in my previous post. This paper proves that hinged dissections are PSPACE-hard using a reduction from NCL with some neat gadgets.

Now, the puzzle. This is a puzzle I heard from Rachael Harding and is another variant of the prisoner’s hats puzzles:

Suppose you have 5 prisoners. Each prisoner gets a hat with equal probability of being either a red or a blue hat. The prisoners must guess the color of their own hat. They may choose to say “Red,” “Blue,” or “Pass.” If at least one of the 5 prisoners guesses correctly and no prisoner guesses incorrectly (i.e. guesses the wrong color: “Pass” does not mean the prisoner guesses correctly and it does not mean she guesses incorrectly), then they go free. The friendly warden again allows them to discuss a strategy beforehand. However, before the warden hands them their hats, they must choose an order to be asked what hat is on their heads. Then, the warden will give them their hats and ask the prisoners according to the specified order. The prisoners may hear the answers of the prisoners who answered before them.

What is their optimal strategy for being released with high probability?

The answer to the previous puzzle is explained below (highlight to see):

 

Some figures may be found at http://www.archimedes-lab.org/workshoptangram4.html. The idea is that although the shapes look similar, if you zoom in, the proportions are slightly different. I guess some of you might not like the puzzle as much because the original puzzle figures may not be to scale.

Posted in Paper and Puzzle | Tagged , , , | Leave a comment

Paper and Puzzle a Day 6

It’s been a while since I posted a paper and puzzle since I last made a blog post on a paper and puzzle. Other things have been occupying my time, but hopefully, I’ll be going back to my usual schedule with the Paper and Puzzle a Day posts.

So, first, a paper. I’ve been looking into some computational geometry problems and one particularly interesting paper that I’ve been reading is that of what are called “hinged dissections.” The paper’s title is appropriately titled, “Hinged Dissections Exist.” A hinged dissection is one where all pieces of a dissected shape are connected with a series of “hinges.” For example, the following figure shows a hinged dissection of a triangle into a square discovered by Dudeney in 1902.

Dudeney’s hinged dissection of triangle into square.

The paper shows that any finite collection of polygons of equal area has a hinged dissection such that it can folded into any polygon that is in the collection. It’s quite an intricate paper, and I’m still reading some of the details but it’s quite interesting so far. I may post more in future Paper and Puzzle a Day posts about this paper.

Now, for the puzzle. Since we are talking about computational geometry, I will use a computational geometry puzzle for today.

A tangram consists of the following pieces that form a square.

Even though all of the following figures are made from the same seven pieces, why does the equivalent black and white pieces seem to differ by a piece?

TangraMagic figures

Puzzle courtesy of http://www.archimedes-lab.org/workshoptangram4.html.

Now, the solution to Day 5’s puzzle:

The trick to this puzzle is not to be bogged down with probability calculations. There is a way to ensure that at least 5 prisoners are released regardless of what the distribution of hats is (in which case, the fact that the hats are distributed randomly is irrelevant). Each prisoner decides beforehand what her partner is. Then, one partner decides to say the color hat that is opposite the color of her partner’s hat and the other says the same color as that on the partner’s head. When the hats are distributed, the partners find each other and carry out the strategy. If the hats on both partners’ heads are the same color, then the partner who says the same color will answer correctly. If the hats are different colors, then the partner who says the different color answers correctly. Therefore, one partner in each pair will always answer correctly.

Posted in Uncategorized | Leave a comment