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

Ask HN: Which recent research paper blew your mind?

news.ycombinator.com

Post reply on HN
Print view View original

121–130 of 174 posts

Re: Ask HN: Which recent research paper blew your mind?

#121

Post by nukeman »

NoMoreNicksLeft wrote: post #87
philipkglass wrote: post #78

"Liquid solution centrifugation for safe, scalable, and efficient isotope separation" https://www.science.org/doi/10.1126/sciadv.adg8993 The authors show that a biological type laboratory ultracentrifuge can efficiently function as a near-universal isotope separator. Any element that can be dissolved as a salt in water -- the entire periodic table, excepting the noble gases -- can be enriched according to its relativ…

Surely something about the technique would make it impractical for enriching uranium though... you're not going to be able to produce kilograms of 20% U235 with this are you?

Hypothetically, if the technique can enrich U, Pu, or other fissile isotopes in decent quantities, you run into other issues. Stirring an aqueous enriched uranium solution is a great way to have a criticality accident (cf. https://en.wikipedia.org/wiki/Criticality_accident). That’s not to say it’s impossible to manage, just difficult. UF6, the current compound of choice for enrichment, is in the gas phase during the process.

Re: Ask HN: Which recent research paper blew your mind?

#122

Post by YeGoblynQueenne »

varranvar wrote: post #90
YeGoblynQueenne wrote: post #83

Earlier quoted context omitted.

That's cool and all, but the one thing that really made it possible to train deep neural nets was the use of backpropagation, and its polynomial time complexity. By contrast, there are no known polynomial time algorithms for program synthesis and the standard approach is to search some large combinatorial space [1]. That's the case for all the classical approaches: SMT, SAT, planning and scheduling, etc. At the same…

I'm working on an inductive logic programming algorithm, and from my understanding the search space for logic programs is just as vast as other types of program synthesis. Do you have any information you can share about the polynomial time algorithm?

Of course. It's published as an open-access paper here:

https://link.springer.com/article/10.1007/s10994-020-05945-w

But I recommend the arxiv version where Springer couldn't mess up my LaTex formatting:

https://arxiv.org/abs/2101.05050

(Not that my LaTex formatting is anything to write home about!).

To clarify, the algorithm described in our paper doesn't reduce the size of the search space for logic programs- it sidesteps it.

Note I'm the corresponding author in the paper and my email is in the Springer version (top of the page). I'm always happy to answer questions about my work.

Re: Ask HN: Which recent research paper blew your mind?

#123

Post by lmeyerov »

naillo wrote: post #14
GregarianChild wrote: post #10

Someone managed to GPU-accelerate program synthesis, a form of symbolic ML. First time for ML that is not deep learning: https://dl.acm.org/doi/10.1145/3591274 Deep learning took off precisely when the ImageNet paper dropped around 2010. Before nobody believed that backprop can be GPU-accelerated.

How is program synthesis the same as regular expression search? Honest question

This seems like an early paper and agreed with the consternation.

The paper, in a modern context and based solely on the abstract and having been in the community, is chipping at the "uninteresting" part of the problem. Around that time, program synthesis started switching to SMT (satisfiability modulo theory) methods, meaning basically a super powerful & general SAT solver for the broad search ("write a wild python program") and then, for specialized subdomains, have a good way to call out to optimized domain solvers ("write a tiny bit of floating point math here"). The paper would solve what the regex callout looks like.. which is specialized. We can argue regex is one of the most minimal viable steps towards moving to general programming on GPUs. Except as a person who does SIMD & GPU computing, optimizing compute over finite automata is not general nor representative and I don't expect to change my thinking much about the broader computational classes. To be fair to the authors... back then, synthesizing regex & sql were hard in practice even for boring cases.

Separately, nowadays synthesis has shifted to neural (copilot, gpt), and more interesting to me, neurosymbolic in R&D land. We're doing a lot of (simple) neurosymbolic in louie.ai, and I'm excited if/when we can get the SMT solver side in. Making GPT call Z3 & Coq were some of the first programs I tried with it :) Till then, there's a lot more interesting low-hanging fruit from the AI/ML side vs solvers, but feels like just a matter of time.

Re: Ask HN: Which recent research paper blew your mind?

#124

Post by saltcured »

claytonjy wrote: post #61
GregarianChild wrote: post #31

Earlier quoted context omitted.

Can you point me to papers with reproducible benchmarking that achieves big speedups on those? Modern GPUs are GP -GPUs: where GP means "general purpose" : you can run any code on GPGPUs. But if you want to gain real speed-ups you will have to program in an awkward style ("data parallel"). I am not aware of GPU acceleration of the work-horses of symbolic AI, such as Prolog, or SMT solving. There has been a lot of wor…

I think we're conflating two things: shallow/classic ML is not symbolic AI. I'm not sure "ML" even encompasses anything "symbolic"; I see symbolic AI and ML as subfields with little overlap. I'm not saying symbolic AI has been GPU accelerated in the past, but that non-deep ML has been.

Back when I took AI courses in the early 90s, ML was anything that was trained by data. It did not refer exclusively to dense numerical or statistical methods. It included decision trees, which I think of as being closer to the symbolic camp...

Re: Ask HN: Which recent research paper blew your mind?

#125

Post by nocoiner »

edent wrote: post #17

"Overview of SHARD: A System for Highly Available Replicated Data" it's the first paper to introduce the concept of database sharding. It was published in 1988 by the Computer Corporation of America. It is referenced hundreds of times in many classic papers. But, here's the thing. It doesn't exist . Everyone cites Sarin, DeWitt & Rosenb[e|u]rg's paper but none have ever seen it. I've emailed dozens of academics, libr…

This is really interesting, thanks for posting it here!

On a semi-related topic, I love mysteries like these - mystery songs, those Japanese kanji in Unicode that nobody knows what they mean or where they came from, paper towns on maps.

If anyone else has anything else to read along similar lines, please post it!

Re: Ask HN: Which recent research paper blew your mind?

#126

Post by [deleted] »

CamperBob2 wrote: post #67
edent wrote: post #17

"Overview of SHARD: A System for Highly Available Replicated Data" it's the first paper to introduce the concept of database sharding. It was published in 1988 by the Computer Corporation of America. It is referenced hundreds of times in many classic papers. But, here's the thing. It doesn't exist . Everyone cites Sarin, DeWitt & Rosenb[e|u]rg's paper but none have ever seen it. I've emailed dozens of academics, libr…

1988? As far as anyone can tell, the use of the term "shard" in the context of database replication originated with Ultima Online, which was released in 1997, and which used the term in connection with its underlying mythos (the idea of representing world instances as shards of Mondain's shattered gem). So a documented reference to sharding that's earlier than that would be interesting to see. (Disagree? Instead of d…

[deleted]

Re: Ask HN: Which recent research paper blew your mind?

#127

Post by andyjohnson0 »

CamperBob2 wrote: post #67
edent wrote: post #17

"Overview of SHARD: A System for Highly Available Replicated Data" it's the first paper to introduce the concept of database sharding. It was published in 1988 by the Computer Corporation of America. It is referenced hundreds of times in many classic papers. But, here's the thing. It doesn't exist . Everyone cites Sarin, DeWitt & Rosenb[e|u]rg's paper but none have ever seen it. I've emailed dozens of academics, libr…

1988? As far as anyone can tell, the use of the term "shard" in the context of database replication originated with Ultima Online, which was released in 1997, and which used the term in connection with its underlying mythos (the idea of representing world instances as shards of Mondain's shattered gem). So a documented reference to sharding that's earlier than that would be interesting to see. (Disagree? Instead of d…

(I didn't downvote your comment)

"SHARD" is the name of the software - it was common back then to name systems using acronyms. It's not clear whether the paper/report actually uses the term "shard" in the sense that it is now used in distributed systems, or even whether it uses it at all.

Re: Ask HN: Which recent research paper blew your mind?

#128

Post by InitialLastName »

pjs_ wrote: post #56
edent wrote: post #17

"Overview of SHARD: A System for Highly Available Replicated Data" it's the first paper to introduce the concept of database sharding. It was published in 1988 by the Computer Corporation of America. It is referenced hundreds of times in many classic papers. But, here's the thing. It doesn't exist . Everyone cites Sarin, DeWitt & Rosenb[e|u]rg's paper but none have ever seen it. I've emailed dozens of academics, libr…

Going through the bibliography of other people's papers and theses, looking for papers that you better cite "for good luck", or because "you gotta cite that one" is a classic PhD student behavior (I've done it) and it's not terribly surprising that something like this can happen. In fact I'd expect it to be much more widespread...

One of the only notes I got from my MS thesis defense was one of the professors being annoyed that I had cited a result from someone else's paper that he had reported (effectively the same but derived differently and less conclusively) in one of his own papers. I added a note referring to his result and a citation to his paper and everybody went home happy.

Re: Ask HN: Which recent research paper blew your mind?

#129

Post by GregarianChild »

YeGoblynQueenne wrote: post #83
GregarianChild wrote: post #10

Someone managed to GPU-accelerate program synthesis, a form of symbolic ML. First time for ML that is not deep learning: https://dl.acm.org/doi/10.1145/3591274 Deep learning took off precisely when the ImageNet paper dropped around 2010. Before nobody believed that backprop can be GPU-accelerated.

That's cool and all, but the one thing that really made it possible to train deep neural nets was the use of backpropagation, and its polynomial time complexity. By contrast, there are no known polynomial time algorithms for program synthesis and the standard approach is to search some large combinatorial space [1]. That's the case for all the classical approaches: SMT, SAT, planning and scheduling, etc. At the same…

> backpropagation, and its polynomial time complexity

How do you reconcile the NP-completeness result in [1] about training neural networks with your claim?

[1] A. L. Blum, R. L. Rivest, Training a 3-Node Neural Network is NP-Complete. https://proceedings.neurips.cc/paper/1988/file/3def184ad8f47...

Re: Ask HN: Which recent research paper blew your mind?

#130

Post by mindcrime »

radlad wrote: post #106
radlad wrote: post #50

Earlier quoted context omitted.

I found LinkedIn profiles for Sunil Sarin, Mark Dewitt, and Ronni Rosenberg who all worked at CCA during this time period. I've gone ahead and sent them each a message asking if they might be able to make the paper available. If you'd like to get in contact with them yourself and are having trouble finding their LinkedIn, shoot me an email and I'll be happy to provide you links.

I received a response from Dr. Rosenberg: > Yes, I was involved, 35 years ago! I believe it was an internal CCA paper. I don't have a copy and I have no idea how to get it. Sorry about that. It does seem to be the earliest reference to "shard" in the DB context. (The other early reference pointed to in Wikipedia is from much later, 1997.) > Fortunately, you need not go back 35 years to read about sharding; it's easy…

I've now sent a message to Andy Youniss, CEO of Rocket Software to see if he can help.

I suspect that if that memo lives on anywhere, it's somewhere in the bowels of Xerox. I say that based on observing that:

1. In the paper by Ronni L. Roseniberg at https://apps.dtic.mil/sti/pdfs/ADA209126.pdf the citation to the SHARD paper changed to

Sunil Sarin, Mark DeWitt, and Ronni Rosenberg, "Overview of SHARD: A System for Highly Available Replicated Data," Technical Report 162, Xerox Advanced Information Technology (May 1988).

2. Per Wikipedia[1] Crowntek sold Computer Corporation of America's Advanced Information Technology division to Xerox Corporation in 1988.

To me this suggests that it was the "Advanced Information Technology division" specifically which would have had the paper in question, and that bit of CCA wound up with Xerox.

That said, it can't hurt to reach out anybody connected to this in any way. You never know who will wind up "knowing a guy who knows a gal, who knows a ..." or whatever.

[1]: https://en.wikipedia.org/wiki/Computer_Corporation_of_Americ...

Post reply on HN