Hacker News Reader

Comment by floatingatoll | Hacker News Reader

On boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea...

The closing quote:

> [Huang] was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least √n of the other points — and the sensitivity conjecture instantly followed from this result

The actual paper: https://arxiv.org/abs/1907.00847

Another blog post: https://www.scottaaronson.com/blog/?p=4229

An older HN post: https://news.ycombinator.com/item?id=20338281

View on HN

This is pure intuition, but from reading this I get the sense that this conjecture is some generalization of a fixed point theorem?

Well - the eigenvalues (of the adjacency matrix), which are used in the proof, correspond to eigenvectors. Which are fixpoints (or at least fixed linear subspaces) of the corresponding linear function. So there is some "lexical" connection. But apart from that I'm not sure that I share your sense that this is "some generalization of a fixed point theorem". Can you give us more insight?

Can you explain your intuition for how this relates to fixed points?

A Boolean array is isomorphic to a fixed point number.

The article discusses non-fixed equivalents, though, both a contextual variable length and a quantum super position length bit array.

I don't understand what you said, but I and (I assume) GP were talking about https://en.wikipedia.org/wiki/Fixed_point_(mathematics)

From the article:

> Other measures involve looking for the simplest way to write the Boolean function as a mathematical expression, or calculating how many answers the banker would have to show a boss to prove they had made the right loan decision. There’s even a quantum physics version of query complexity in which the banker can ask a “superposition” of several questions at the same time. Figuring out how this measure relates to other complexity measures has helped researchers understand the limitations of quantum algorithms.

I assumed you were discussing https://en.wikipedia.org/wiki/Fixed-point_arithmetic which is a potential application domain for this research.

I'm not seeing the connection between this research and fixed-point arithmetic.

I don’t exactly follow the above either, but I believe fixed point is meant in a different sense here, as in a function f(x) such there a point x0 exists where x0=f(x0).

https://en.m.wikipedia.org/wiki/Fixed-point_theorem

Reply on news.ycombinator.com