Posted by: holdenlee | September 5, 2015

Media consumption, 8/23-9/5

*denotes something I found particular interesting.

[h] is a highlighted page (I’m in the habit of using scrible to highlight web pages I read – these are for my own convenience and I don’t expect others to find them useful).

Posted by: holdenlee | August 23, 2015

Media consumption, 8/9-22

Posted by: holdenlee | August 8, 2015

Media consumption, 8/2-8

I’m presenting Barron’s Theorem in the Machine Learning reading group today.

Abstract: I will state and prove Barron’s Theorem, which shows that 1-layer neural networks can evade the curse of dimensionality. Barron’s Theorem bounds the error of the best neural net approximation to a function, in terms of the number of hidden nodes and the smoothness of the function, independently of the dimension.

Notes are available here (source).
Update: Thanks to Alex Anderson for pointing out limitations of Barron’s Theorem. In his words:
In the context of deep learning, Barron’s Theorem has been a huge red-herring for the neural network community. Even if a single hidden-layer network can do arbitrary function approximation, that doesn’t mean that it does it efficiently (in terms of number of parameters), and these approaches are never used in practice now. There are some things happening that are much more subtle than can be treated in this fashion.
Here are some recent papers he recommends:
Posted by: holdenlee | August 1, 2015

Media consumption, 7/26-8/1

* = found particularly interesting

  •  Podcasts
    • 99% Invisible
      • Automation paradox*: 2-part series on automation.
        • 170 Children of the magenta – How automation has changed airplane safety (no question it increases safety, but automation can lead to incompetence – pilots being too reliant)
        • 171 Johnnycab: A world with self-driving cars. How would cities change?
      • 172 On location: on the Bradbury building, a film icon in Los Angeles
      • 173 Awareness: Ribbons for causes – it started with AIDS. How to do it: get the ribbons in a lot of high-profile places, and then tell people it’s for AIDS awareness
      • 174 From the sea, freedom: Micronations
      • 169 Freud’s couch
    • Freakonomics:
    • TED radio hour
      • Finite* (innovation comes out of scarcity; rainforests contain a wealth of medical knowledge that we haven’t valued and have turned away from; antibiotics should be viewed as a scarce resource because they create resistance)
      • Transformation
  • Following Slate star codex*. (Things like minimum wage, tenure, and medical school admission create “duality”: a gap between those who get it vs. those who don’t, with similar consequences), (People misuse the word “debunk” to refer to literature that opposes their beliefs, rather than is publicly dismissed; often both sides claim they “debunked” each other). Lots of links. It’s very draining to sift through lots of media to find interesting things, so a curated list of link is gold.
  • Glanced at first 2 chapters of Experimental mathematics (website). Seems to be a lot of interesting math problems to do here, though I mostly just read the notes on doing math:
    • Hardy and Littlewood’s 4 axioms for collaboration:

      The first [axiom] said that when one wrote to the other (they often preferred to exchange thoughts in writing instead of orally), it was completely indifferent whether what they said was right or wrong. As Hardy put it, otherwise they could not write completely as they pleased, but would have to feel a certain responsibility thereby. The second axiom was to the effect that, when one received a letter from the other, he was under no obligation whatsoever to read it, let alone answer it, – because, as they said, it might be that the recipient of the letter would prefer not to work at that particular time, or perhaps that he was just then interested in other problems….The third axiom was to the effect that, although it did not really matter if they both thought about the same detail, still, it was preferable that they should not do so. And, finally, the fourth, and perhaps most important axiom, stated that it was quite indifferent if one of them had not contributed the least bit to the contents of a paper under their common name; otherwise there would constantly arise quarrels and difficulties in that now one, and now the other, would oppose being named co-author.“

    • Observation vs. proof in math (p. 11)

      I have myself always thought of a mathematician as in the first instance an observer, a man who gazes at a distant range of mountains and notes down his observations… proofs are what Littlewood and I call gas, rhetorical flourishes designed to affect psychology, pitcures on the board in the lecture, devices to stimulate the imagination of pupils. – G H. Hardy

    • Site + article on Escher: What an Escher picture has to do with elliptic curves.
  • Curiosity – thought about this after listening to From Curiosity to Discovery (TED radio hour) a while back. Curiosity is an important ingredient to a fulfilling life and yet is not talked about/encouraged in society. Picked up Curious, Ian Leslie and A Curious Mind, Brian Grazer.
    Snippets from the intro:

    No one had thought to let him in on a secret: “I was suddenly seeing that the world is incredibly interesting… The closer you look at anything, the more interesting it gets. But nobody tells you this.”

    For most of Western history, it has been regarded as at best a distraction, at worst a poison, corrosive to the soul and to society… curiosity is deviant.
    [The Renaissance happened was a shift where society realized it was good to ask questions.]

    [the] new challenge is to make people hungry to learn, question, and create…. how to instill a culture of inquiry and critical thinking into their educational systems.

    Curiosity is more state than trait: we can arrange our lives to stoke our curiosity or quash it.

  • An interesting talk by Nisheeth Vishnoi on thinking about evolution using computer science. Papers quite readable.
  • LLL algorithm, notes and slides. (One application is finding algebraic dependenciess, see Experimental mathematics above.
  • Started reading Game of Thrones.
  • Watched up to episode 11 of My Little Pony
Posted by: holdenlee | July 25, 2015

Media consumption, 7/19-25

To keep track of some of the stuff I read/watch/listen to/play. Perhaps I’ll post one of these every week or two.

Posted by: holdenlee | July 21, 2015

Fully Homomorphic Encryption

I’m giving a talk today on fully homomorphic encryption at the student-run “Gems of theoretical computer science” seminar.

Here are the notes (source).

Here are notes (source, original paper) from a talk by Noga Ron-Zewi.


Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are special families of error-correcting codes that admit extremely efficient sub-linear time algorithms for error correction and detection, respectively, while making a few queries to the received word. These codes were originally studied in complexity theory because of their close relationship to program checking and probabilistically-checkable proofs (PCPs), but subsequently they were extensively studied for their own sake.

In this work, we construct the first locally-correctable codes and locally-testable codes with constant rate, constant relative distance, and sub-polynomial query complexity and running time. Specifically, we show that there exist binary LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity and running time $\exp(\sqrt{\log n})$. Previously such codes were known to exist only with query complexity and running time $n^{\beta}$ (for constant $\beta > 0$), and there were several, quite different, constructions known.

Along the way, we also construct LCCs and LTCs over large (but constant) size alphabets, with the same query complexity and running time $\exp(\sqrt{\log n})$, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any sub-linear query complexity.

If time permits I will also discuss a very recent work that substantially improves the query complexity of LTCs to quasi-polylogarithmic function of the form $(\log n)^{O(\log \log n)}$.

Joint work with Swastik Kopparty, Or Meir and Shubhangi Saraf

Posted by: holdenlee | July 18, 2015

Inside Out

I saw Inside Out recently and I loved it!

Some ramblings.

I’m fascinated with the whole “society of mind” idea – the idea that what constitutes our consciousness or our intelligence isn’t just one central entity (oneness is an illusion) – but rather a large collection of agents – feelings, methods of reasoning, etc. – cooperating/competing in our minds. To turn this into a story – portray all these agents in a person’s mind as characters – would be amazing but also very difficult – how could one get this across without being either being overly pedantic or abstract, or too simplistic? Inside Out really strikes a sweet spot here.

Read More…

Posted by: holdenlee | July 12, 2015

Namba.elm: A fast-paced arithmetic game

Play me at

Source code is available at This is the minimal playable version (v0.1) – leave me some comments so I can make the next version better.

Detailed instructions (plus thoughts on making the game, and directions to go from here) follow. But see if you can figure it out by yourself first.

If you get a score >10, let me know in the comments:)

Read More…

« Newer Posts - Older Posts »