Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google researcher, long out of math, cracks devilish problem about sets

quantamagazine.org

Post reply on HN
Print view View original

21–30 of 120 posts

Re: Google researcher, long out of math, cracks devilish problem about sets

#21

Post by bobkazamakis »

tester457 wrote: post #14
jobs_throwaway wrote: post #7

Earlier quoted context omitted.

"The value of a … education is not the learning of many facts but the training of the mind to think." While anyone with a (good) STEM education knows this to be obviously true, its frightening how many people go through 16+ years of formal schooling where they mostly do rote memorization and regurgitation.

We can thank the academic system and Goodhart's Law for that. We measure students with tests, but all we get are people good at taking tests and rote memorization. Maybe if we had a better way to access actual learning but are teachers even paid enough to truly care?

>Maybe if we had a better way to access actual learning but are teachers even paid enough to truly care?

There's no incentive to pay teachers more; system is working as designed. Those students aren't giving short-term quarterly gains.

Re: Google researcher, long out of math, cracks devilish problem about sets

#22

Post by tills13 »

thethirdone wrote: post #13

> “Mike said, ‘Justin, you’re going to get me thinking about this problem again and I don’t want to do that,’” said Gilmer. This is a very relatable feeling. I often find myself getting trapped into thinking about problems I am unlikely to solve.

I find it's a cruel trick people, usually inadvertently, play on me at work: "when you've got a sec can you look at x?"

There's a portion of my brain that's immediately hijacked and starts thinking about the problem whether I'm actively working on it or not.

Happens to me for work problems outside of work, too. I'll just be chilling in the shower or something and suddenly I'm thinking about a work problem.

Maybe one day I'll retire from programming and do something less theoretical e.g. driving a semi.

Re: Google researcher, long out of math, cracks devilish problem about sets

#23

Post by thomasahle »

Paper link: https://arxiv.org/abs/2211.09055

Abstract:

We show that for any union-closed family F\subseeq 2^[n],F≠{∅}, there exists an i∈[n] which is contained in a 0.01 fraction of the sets in F. This is the first known constant lower bound, and improves upon the Ω(log_2(|F|)^{−1}) bounds of Knill and Wójick. Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if A,B are independent samples from a distribution over subsets of [n] such that Pr[i∈A]0, then H(A∪B)>H(A).

Re: Google researcher, long out of math, cracks devilish problem about sets

#24

Post by adamisom »

jobs_throwaway wrote: post #7
acctant wrote: post #2

> He also worked with a textbook by his side so he could look up formulas he’d forgotten. “You’d think someone who comes up with a great result shouldn’t have to consult Chapter 2 of Elements of Information Theory, but I did,” Gilmer said. Always enjoy seeing this sentiment reaffirmed. Funny that Gilmer states it in a somewhat self surprised tone. Rings of the Einstein quote: “[I do not] carry such information in my…

"The value of a … education is not the learning of many facts but the training of the mind to think." While anyone with a (good) STEM education knows this to be obviously true, its frightening how many people go through 16+ years of formal schooling where they mostly do rote memorization and regurgitation.

I think it’s mainly that STEM majors are smarter, and thinking is hard slash unmotivating.

Of course any non-STEM field has geniuses, but our impressions—like the parent’s—are formed from averages, and STEM majors are smarter on avg.

Re: Google researcher, long out of math, cracks devilish problem about sets

#26

Post by SideQuark »

rkp8000 wrote: post #9

Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts. A related toy example that comes to mind is the puzzle where you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maxim…

I once made a cool solution to this problem using information theory, in particular coding theory.

The usual solution uses the fact there are 3 places to put items: left scale, off scale, and right scale. Then those solutions do if/then cases to juggle items around to find the mis-weighted ball.

My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 result: left, balance, right. This formed the digits of the mis-weighted ball.

The idea is to make an error correcting code in base 3, and use the "weighings" as the correction matrix to isolate the bad "bit".

This idea generalizes to solve a massive range of find the odd item(s) problems.

Re: Google researcher, long out of math, cracks devilish problem about sets

#27

Post by warrenmiller »

agar wrote: post #12

The article title has been revised to more accurately reflect the researcher's position (and removes the AI ambiguity): "Google Researcher, Long Out of Math, Cracks Devilish Problem About Sets" Should the title of this HN entry be updated accordingly?

"long out of math"? he did his Ph.D. in 2015. - surely 7 years is not that long! :)

Re: Google researcher, long out of math, cracks devilish problem about sets

#28

Post by [deleted] »

tills13 wrote: post #22
thethirdone wrote: post #13

> “Mike said, ‘Justin, you’re going to get me thinking about this problem again and I don’t want to do that,’” said Gilmer. This is a very relatable feeling. I often find myself getting trapped into thinking about problems I am unlikely to solve.

I find it's a cruel trick people, usually inadvertently, play on me at work: "when you've got a sec can you look at x?" There's a portion of my brain that's immediately hijacked and starts thinking about the problem whether I'm actively working on it or not. Happens to me for work problems outside of work, too. I'll just be chilling in the shower or something and suddenly I'm thinking about a work problem. Maybe one…

[deleted]

Re: Google researcher, long out of math, cracks devilish problem about sets

#29

Post by chris_overseas »

tills13 wrote: post #22
thethirdone wrote: post #13

> “Mike said, ‘Justin, you’re going to get me thinking about this problem again and I don’t want to do that,’” said Gilmer. This is a very relatable feeling. I often find myself getting trapped into thinking about problems I am unlikely to solve.

I find it's a cruel trick people, usually inadvertently, play on me at work: "when you've got a sec can you look at x?" There's a portion of my brain that's immediately hijacked and starts thinking about the problem whether I'm actively working on it or not. Happens to me for work problems outside of work, too. I'll just be chilling in the shower or something and suddenly I'm thinking about a work problem. Maybe one…

The obligatory XKCD https://xkcd.com/356/

Re: Google researcher, long out of math, cracks devilish problem about sets

#30

Post by jihadjihad »

thethirdone wrote: post #13

> “Mike said, ‘Justin, you’re going to get me thinking about this problem again and I don’t want to do that,’” said Gilmer. This is a very relatable feeling. I often find myself getting trapped into thinking about problems I am unlikely to solve.

Reminds me of the multi-armed bandit problem, where Allied scientists considered it to be so intractable that they proposed dropping it over Germany so their scientists would waste their time on it.
Post reply on HN