Sub-exponential solutions for NP-hard problems

 A few days ago Open AI and Anthropic announced the disproval of the Exponential Time Hypothesis by their models and published two relevant papers. ETH essentially states that the 3-SAT problem, in the worst case, can only be computed in exponential time.

Their proves are interesting, however they are not really built on novel ideas. In chapter 3 of my PhD thesis, also available here, I show that the state space, or else solution space, of the NP-hard problems is not a flat set of unrelated solutions. It is a complex space of related states and by exploiting these relations we can build algorithms that avoid the exhaustive computation of all the possible solutions. 

I used this framework to build approximate polynomial algorithms by actually partitioning the state space and avoid unnecessary computations. This framework enabled me to build a Distributed Deep Learning method to compute efficiently a really demanding problem concerning resource allocation in datacenters.

The aforementioned proves build sub-exponential algorithms by partitioning the set of possible assignments in groups or tensors by exploiting the solution space properties and relations. The underlying logic has similarities in the three works and highlights fundamental properties of the NP-hard problems.

Peer Review Insufficiency

 It is always fascinating to have an article rejected from a journal without sufficient explanation.

Especially when this article is within the scope of the journal and other similar articles, of equal or inferior quality, are already published in this journal.

On AI solving open math problems

Many people these days are shocked by the OpenAI announcements on results on open (until recently) problems and they ask the company to stop testing frontier models on open math problems. That doesn't sound right. Just because you cannot compete technology you cannot ask it to cease to exist.

Nevertheless, it is reasonable to ask AI companies to make such announcements in a slower pace. Not necessarily to slow down model development, just to make such releases on smaller packages and less frequently, so that the community will have time to digest the results and perhaps even understand the proves.

Bombarding the community with a huge bundle of information can only make the whole task unmanageable. That is if you want to make some serious contribution to scientific progress and not just make good impression to your stockholders.

Schrodinger's cat tired of waiting

 Schrodinger's cat tired of waiting

Algorithmic approach of the unit distance problem

In my latest paper, I present experimental evidence on unit-distance graph density which was introduced by Paul Erdős. My approach is based on a novel algorithmic exploration of the rational plane and the generation of a unit-distance graph that surpasses recent theoretical lower bounds. It achieves a scaling exponent larger than 1.17. 

 

The algorithm essentially utilizes a local-breadth search on a bounded and finite set of elements and generates a graph that potentially encompasses the general properties of a unit-distance graph, not affected by restrictions on its generation. 


Find the paper here and the repository containing code and experimental results here.