Open Problems in Computational geometry | Hacker News Reader

Open Problems in Computational geometry

topp.openproblem.net

92 pointsnill012 comments

It's a great idea to collect open problems, to give them a name and unique number, to collect status updates, and to provide related literature references. It would be good to keep this open for submitting new problems also, and I'd like to see similar activities for all sub-areas of mathematics and computer science.

Mathematicians led by Terence Tao are keen to explore new ways for mathematicians to collaborate remotely and online to tackle all open problems together in an open and technology-supported way. I think problem inventories should be part of that, together with proof collections, existing datasets such as the great On-Line Encyclopedia of Integer Sequences (OEIS, at https://oeis.org), and perhaps Jupyter-type notebooks that utilize symbolic algebra systems, theorem provers etc.

Does anyone know if this is still up-to-date?

All three authors are large contributors to the field (the book _discrete and computational geometry_ by O'Rourke & Devadoss is excellent), Demaine has some origami in the collection at MoMA NYC^, Mitchell found a ptas for euclidian tsp (Google it - the paper is readable and there is another good write up of his vs Arora's)

^ https://erikdemaine.org/curved/MoMA/

Last update to mark a problem as solved was in December last year: https://github.com/edemaine/topp/pull/10

You just need to file a simple PR to mark a problem as solved though. I cannot get much simplier

Thanks for the pointer, I just saw the 2nd edition of Discrete and Computational Geometry will be coming out in July: https://www.amazon.com/-/en/Discrete-Computational-Geometry-... (I preordered a copy)

Definitely out of date, e.g. the 3SUM subquadratic conjecture (probably 11) has been solved and improved on [1].

If it's not been already there's immediate application, e.g. problem 41.

[1]:https://link.springer.com/article/10.1007/s00453-015-0079-6

Are there any solutions similar to those found at https://www.cs.ru.nl/~freek/100/ ?

Is any of the new machine learning tech promising here? I recall some new invariants of minimal surfaces were discovered only a few years ago by a DeepMind-made AI - and that's before LLMs. I'm wondering if AI can invent notions as powerful as homology groups: It could go about this by constructing lossy compressors whose outputs can still be used to accurately predict properties of geometric objects. That is what homology groups and the like are for.

This does seem like one math domain where there's some potential for program synthesis approaches like the recent AlphaEvolve and others. I say that because some of these problems you could feasibly write automatic evaluation code and solve them by the LLM spitting out a constructor for solutions and then doing hill climbing. That's not true in many areas of math though. There's also problems here that require a proof and maybe would be approachable eventually using automated theorem proving. But there's also problems that don't obviously fit into either of those categories.

A technicality is that those compressors need to provably predict properties of said geometric objects to be interesting to mathematicans (a statement which itself needs appropriate encoding in mathematical language - what exactly you want probably depends on the problem you hope to solve). Something that superficially looks good but works as a black box wouldn't cut it.

My understanding of ML interpretability research at the moment is that it's very early days - too early, perhaps, to hope for a general purpose compressor algorithm that produces proofs of it's own workings (that seems like the holy grail). But of course I would love to be wrong!

Was hoping for some pretty pictures.... since there are none this article isn't for me I guess.

Indeed. With more pictures such as at https://topp.openproblem.net/p59 I foresee that there will be much more solutions. You don't need to be an expert to solve most, but they hide themselves behind expert language

Reply on news.ycombinator.com