'Breakthrough' algorithm exponentially faster than any previous one

#1

Post by optimalsolver » Tue, Jul 03, 2018, 2:05 PM UTC

'Breakthrough' algorithm exponentially faster than any previous one
sciencedaily.com

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#2

Post by HelloNurse » Tue, Jul 03, 2018, 2:24 PM UTC

Any link to a paper?

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#3

Post by FlukE_ » Tue, Jul 03, 2018, 2:31 PM UTC

HelloNurse wrote: post #2

Any link to a paper?

'The researchers will present their novel approach at two upcoming conferences: the ACM Symposium on Theory of Computing (STOC), June 25-29 and International Conference on Machine Learning (ICML), July 10 -15.' I couldn't find anything with some googling so I'm assuming this quote describes the first showing of the paper.

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#4

Post by pmarreck » Tue, Jul 03, 2018, 2:41 PM UTC

So this is basically "early search-tree pruning"? Or, how is it different from that, exactly? (I believe early search-tree pruning has been used in chess algorithms for years.)

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#5

Post by rindalir » Tue, Jul 03, 2018, 2:42 PM UTC

FlukE_ wrote: post #3

HelloNurse wrote: post #2

Any link to a paper?

'The researchers will present their novel approach at two upcoming conferences: the ACM Symposium on Theory of Computing (STOC), June 25-29 and International Conference on Machine Learning (ICML), July 10 -15.' I couldn't find anything with some googling so I'm assuming this quote describes the first showing of the paper.

https://scholar.harvard.edu/files/ericbalkanski/files/the-ad...

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#6

Post by MaxBarraclough » Tue, Jul 03, 2018, 2:42 PM UTC

HelloNurse wrote: post #2

Any link to a paper?

https://arxiv.org/pdf/1804.06355.pdf

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#7

Post by IshKebab » Tue, Jul 03, 2018, 2:47 PM UTC

This is too dumbed down to be understood by anyone. :/

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#8

Post by MaxBarraclough » Tue, Jul 03, 2018, 2:47 PM UTC

rindalir wrote: post #5

FlukE_ wrote: post #3

Earlier quoted context omitted.

'The researchers will present their novel approach at two upcoming conferences: the ACM Symposium on Theory of Computing (STOC), June 25-29 and International Conference on Machine Learning (ICML), July 10 -15.' I couldn't find anything with some googling so I'm assuming this quote describes the first showing of the paper.

https://scholar.harvard.edu/files/ericbalkanski/files/the-ad...

I don't think that's it. That's one of Singer's earlier works.

I'm fairly sure the relevant one is https://arxiv.org/pdf/1804.06355.pdf (listed as 'under submission' at https://people.seas.harvard.edu/~yaron/papers.html , in line with the article's description)

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#9

Post by fhood » Tue, Jul 03, 2018, 2:48 PM UTC

Is this satire? What algorithm is faster than what algorithm?!?! They have names! "State of the art" is not the name of a damn algorithm. Why is the abstract being coy?

Re: 'Breakthrough' algorithm exponentially faster than any previous one

#10

Post by Barjak » Tue, Jul 03, 2018, 2:50 PM UTC

HelloNurse wrote: post #2

Any link to a paper?

I think it's arXiv:1804.06355

"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation"