Mathematiker schließen Quest ab, um „kugelförmige Würfel“ zu bauen

Im vierten Jahrhundert lobte der griechische Mathematiker Pappus von Alexandria Bienen für ihre „geometrische Voraussicht“. Die sechseckige Struktur ihrer Waben schien der optimale Weg zu sein, um den zweidimensionalen Raum in Zellen gleicher Fläche und minimalen Umfangs zu unterteilen – was es den Insekten ermöglichte, weniger Wachs zu produzieren und weniger Zeit und Energie für den Bau ihrer Waben aufzuwenden Bienenstock.

Das haben zumindest Pappus und andere angenommen. Jahrtausendelang konnte niemand beweisen, dass Sechsecke optimal sind – bis schließlich 1999 der Mathematiker Thomas Hales zeigte, dass keine andere Form besser geeignet ist. Mathematiker wissen heute noch nicht, welche Formen drei oder mehr Dimensionen mit der kleinstmöglichen Fläche kacheln können.

Es hat sich herausgestellt, dass dieses „Schaum“-Problem weitreichende Anwendungen hat – für Physiker, die das Verhalten von Seifenblasen (oder Schäumen) untersuchen, und Chemiker, die die Struktur von Kristallen analysieren, für Mathematiker, die Kugelpackungsanordnungen erforschen, und Statistiker, die effektive Datenverarbeitungstechniken entwickeln .

Mitte der 2000er Jahre erregte eine besondere Formulierung des Schaumproblems auch die Aufmerksamkeit theoretischer Informatiker, die zu ihrer Überraschung feststellten, dass es eng mit einem wichtigen offenen Problem auf ihrem Gebiet verbunden war. Sie konnten diese Verbindung nutzen, um eine neue hochdimensionale Form mit minimaler Oberfläche zu finden.

„Ich liebe dieses Hin und Her“, sagte er Assaf Naor der Princeton University. „Einige alte Mathematik wird für die Informatik relevant; die Informatik zahlt sich aus und löst die Frage in der Mathematik. Es ist sehr schön, wenn das passiert.“

Aber dieser Form, obwohl optimal, fehlte etwas Wichtiges: eine geometrische Grundlage. Da seine Existenz mit Techniken der Informatik nachgewiesen wurde, war seine tatsächliche Geometrie schwer zu erfassen. Das ist es, was Naor zusammen mit Oded Regev, ein Informatiker am Courant Institute der New York University, machte sich daran, das zu korrigieren ein Beweis, der letzten Monat online gestellt wurde.

„Das ist ein sehr schönes Ende der Geschichte“, sagte Regev.

Kubische Schäume

Mathematiker haben andere Versionen des Schaumproblems in Betracht gezogen – einschließlich dessen, was passiert, wenn Sie den Raum nur gemäß dem sogenannten ganzzahligen Gitter aufteilen dürfen. In dieser Version des Problems nehmen Sie eine quadratische Anordnung von gleichmäßig verteilten Punkten (jeweils 1 Einheit auseinander) und machen jeden dieser Punkte zum Mittelpunkt einer Form. Das „kubische“ Schaumproblem fragt nach der minimalen Oberfläche, wenn Sie den Raum auf diese Weise kacheln müssen.

Die Forscher waren ursprünglich daran interessiert, diese Einschränkung aufzuerlegen, um die Eigenschaften topologischer Räume, sogenannte Mannigfaltigkeiten, zu verstehen. Aber die Frage nahm ein Eigenleben an und wurde in der Datenanalyse und anderen Anwendungen relevant.

Es ist auch geometrisch interessant, weil es ändert, was „optimal“ bedeuten könnte. In zwei Dimensionen können beispielsweise regelmäßige Sechsecke die Ebene nicht mehr kacheln, wenn sie nur um ganzzahlige Beträge in horizontaler und vertikaler Richtung verschoben werden können. (Sie müssen sie um irrationale Beträge in eine der beiden Richtungen bewegen.)

Quadrate können. Aber ist das das Beste, was getan werden kann? Als Mathematiker Jaigyoung Choe 1989 entdeckt, lautet die Antwort nein. Die optimale Form ist stattdessen ein Sechseck, das in einer Richtung gestaucht und in einer anderen verlängert wurde. (Der Umfang eines solchen Sechsecks beträgt ungefähr 3.86, wenn seine Fläche 1 beträgt – was den Umfang des Quadrats von 4 übertrifft.)

Diese Unterschiede mögen trivial erscheinen, aber sie werden in höheren Dimensionen viel größer.

Unter allen Formen eines gegebenen Volumens ist diejenige, die die Oberfläche minimiert, die Kugel. Als n, die Anzahl der Dimensionen, wächst, nimmt die Oberfläche der Kugel proportional zur Quadratwurzel von zu n.

Aber Kugeln können einen Raum nicht kacheln, ohne Lücken zu hinterlassen. Andererseits ein n-dimensionaler Würfel des Volumens 1 Dose. Der Haken ist, dass seine Oberfläche 2 istn, wächst direkt proportional zu seiner Dimension. Ein 10,000-dimensionaler Würfel des Volumens 1 hat eine Oberfläche von 20,000 – viel größer als 400, die ungefähre Oberfläche einer 10,000-dimensionalen Kugel.

Und so fragten sich die Forscher, ob sie einen „kugelförmigen Würfel“ finden könnten – eine Form, die Fliesen bildet n-dimensionaler Raum, wie ein Würfel, dessen Oberfläche aber langsam wächst, wie die einer Kugel.

Es schien unwahrscheinlich. „Wenn Sie möchten, dass Ihre Blase den Raum genau ausfüllt und auf diesem kubischen Gitter zentriert ist, ist es schwer vorstellbar, was Sie außer einer kubischen Blase verwenden würden“, sagte er Ryan O'Donnell, theoretischer Informatiker an der Carnegie Mellon University. „Es scheint wirklich, dass der Würfel der Beste sein sollte.“

Wir wissen jetzt, dass es nicht so ist.

Die Härte schwieriger Probleme

Jahrzehntelang blieb das Problem des kubischen Schaums in höheren Dimensionen relativ unerforscht. Die ersten Forscher, die damit Fortschritte machten, kamen nicht aus dem Bereich der Geometrie, sondern aus der theoretischen Informatik. Sie stießen zufällig darauf, als sie nach einer Möglichkeit suchten, eine zentrale Aussage in ihrem Fachgebiet, bekannt als die, zu beweisen einzigartige Spiele Vermutung. „Die einzigartige Spielevermutung“, sagte Regev, „ist meiner Meinung nach derzeit die größte offene Frage in der theoretischen Informatik.“

2002 vorgeschlagen von Subhash Khot, damals ein Doktorand, geht die Vermutung davon aus, dass, wenn ein bestimmtes Problem – eines, bei dem es darum geht, den Knoten eines Netzwerks Farben zuzuordnen – nicht exakt gelöst werden kann, es sehr schwierig ist, selbst eine ungefähre Lösung zu finden. Wenn dies zutrifft, würde die Vermutung es den Forschern ermöglichen, die Komplexität einer großen Auswahl anderer Rechenaufgaben auf einen Schlag zu verstehen.

Informatiker klassifizieren Aufgaben oft danach, ob sie mit einem effizienten Algorithmus gelöst werden können oder ob sie stattdessen „NP-schwer“ sind (was bedeutet, dass sie mit zunehmender Größe des Problems nicht effizient gelöst werden können, solange allgemein angenommen wird aber unbewiesene Vermutungen über Rechenkomplexität sind wahr). Beispielsweise ist das Problem des Handlungsreisenden, das nach dem kürzesten Weg fragt, der benötigt wird, um jede Stadt in einem Netzwerk nur einmal zu besuchen, NP-schwer. Das gilt auch für die Feststellung, ob ein Graph – eine Sammlung von Knoten, die durch Kanten verbunden sind – mit höchstens drei Farben beschriftet werden kann, sodass zwei beliebige verbundene Knoten unterschiedliche Farben haben.

Es stellt sich heraus, dass es NP-schwer ist, für viele dieser Aufgaben auch nur eine ungefähre Lösung zu finden. Angenommen, Sie möchten die Scheitelpunkte eines Diagramms mit unterschiedlichen Farben so kennzeichnen, dass eine Reihe von Einschränkungen erfüllt werden. Wenn es NP-schwer ist, all diese Einschränkungen zu erfüllen, wie wäre es dann mit dem Versuch, nur 90 % oder 75 % oder 50 % davon zu erfüllen? Unterhalb einer bestimmten Schwelle könnte es möglich sein, einen effizienten Algorithmus zu entwickeln, aber oberhalb dieser Schwelle wird das Problem NP-schwer.

Seit Jahrzehnten arbeiten Informatiker daran, Schwellenwerte für verschiedene interessante Optimierungsprobleme festzulegen. Aber einige Fragen entziehen sich dieser Art der Beschreibung. Während ein Algorithmus 80 % der besten Lösung garantieren kann, kann es NP-schwer sein, 95 % der besten Lösung zu erreichen, wodurch die Frage ungeklärt bleibt, wo genau zwischen 80 % und 95 % das Problem in NP-hartes Gebiet mündet.

Die Unique Games Conjecture oder UGC bietet eine Möglichkeit, die Antwort sofort zu finden. Es macht eine Aussage, die auf den ersten Blick eingeschränkter erscheint: dass es NP-schwer ist, den Unterschied zwischen einem Diagramm zu erkennen, für das Sie fast alle einer bestimmten Reihe von Farbbeschränkungen (z. B. mehr als 99%) erfüllen können, und einem Diagramm für die Sie kaum befriedigen können (sagen wir, weniger als 1%).

Aber kurz nachdem der UGC im Jahr 2002 vorgeschlagen wurde, zeigten Forscher, dass man, wenn die Vermutung wahr ist, den Härteschwellenwert für jedes Problem der Erfüllung von Einschränkungen leicht berechnen kann. (Das liegt daran, dass der UGC auch impliziert, dass ein bekannter Algorithmus für all diese Probleme die bestmögliche Annäherung erreicht.) „Er war genau der Dreh- und Angelpunkt für all diese Optimierungsprobleme“, sagte O'Donnell.

Und so machten sich theoretische Informatiker daran, den UGC zu beweisen – eine Aufgabe, die einige von ihnen schließlich dazu brachte, kugelförmige Würfel zu entdecken.

Schwierige Probleme schwieriger machen

Im Jahr 2005 arbeitete O'Donnell bei Microsoft Research. Er und zwei Kollegen – Uriel Feige, jetzt am Weizmann Institute of Science, und Guy Kindler, jetzt an der Hebräischen Universität von Jerusalem – zusammengetan, um gegen UGC vorzugehen.

Sie hatten eine vage Vorstellung davon, wie sie vorgehen wollten. Sie würden mit einer Frage zu Diagrammen beginnen – eine, die dem UGC sehr ähnlich ist. Das sogenannte Maximum-Cut-Problem („Max-Cut“) fragt, wie man bei gegebenem Graphen seine Eckpunkte in zwei Mengen (oder Farben) aufteilt, so dass die Anzahl der Kanten, die diese Mengen verbinden, so groß wie möglich ist. (Sie können sich max cut als eine Frage vorstellen, wie man einen Graphen am besten mit zwei Farben einfärbt, sodass möglichst wenige Kanten Knoten derselben Farbe verbinden.)

Wenn der UGC wahr ist, würde dies bedeuten, dass ein effizienter Approximationsalgorithmus bei einem gegebenen zufälligen Diagramm nur innerhalb von etwa 87 % des wahren maximalen Schnitts dieses Diagramms kommen kann. Etwas Besseres wäre NP-schwer.

Feige, Kindler und O'Donnell wollten stattdessen in die entgegengesetzte Richtung gehen: Sie hofften zu zeigen, dass der maximale Schnitt schwer zu approximieren ist, und dies dann zum Beweis des UGC zu verwenden. Ihr Plan stützte sich auf die Stärke einer Technik namens parallele Wiederholung – eine clevere Strategie, die schwierige Probleme schwieriger macht.

Angenommen, Sie wissen, dass es NP-schwer ist, zwischen einem Problem, das Sie lösen können, und einem, das Sie größtenteils lösen können, zu unterscheiden. Durch die parallele Wiederholung können Sie darauf aufbauen, um ein viel stärkeres Härteergebnis zu zeigen: dass es auch NP-schwer ist, zwischen einem Problem, das Sie lösen können, und einem, das Sie kaum lösen können, zu unterscheiden. „Dieses nicht intuitive, tiefe Phänomen … steckt heute in den Eingeweiden vieler Informatiker“, sagte Naor.

Aber da ist ein Fang. Parallele Wiederholung verstärkt die Härte eines Problems nicht immer so sehr, wie Informatiker es sich wünschen. Insbesondere gibt es Aspekte des Max-Cut-Problems, die „große Kopfschmerzen bei paralleler Wiederholung verursachen“, sagte Regev.

Feige, Kindler und O'Donnell konzentrierten sich darauf zu zeigen, dass parallele Wiederholungen trotz der Kopfschmerzen funktionieren könnten. "Das ist eine wirklich komplizierte Sache zu analysieren", sagte er Dana Moschkowitz, theoretischer Informatiker an der University of Texas, Austin. „Aber das schien verlockend nah. Parallele Wiederholungen schienen diese Verbindung von Max Cut zu Unique Games zu [helfen].“

Als Aufwärmphase versuchten die Forscher, die parallele Wiederholung für einen einfachen Fall von Max-Cut zu verstehen, was Moshkovitz „den dümmsten Max-Cut“ nannte. Stellen Sie sich eine ungerade Anzahl von Scheitelpunkten vor, die durch Kanten verbunden sind, um einen Kreis oder einen „ungeraden Zyklus“ zu bilden. Sie möchten jeden Scheitelpunkt mit einer von zwei Farben beschriften, sodass kein Paar benachbarter Scheitelpunkte dieselbe Farbe hat. In diesem Fall ist das unmöglich: Eine Kante verbindet immer gleichfarbige Ecken. Sie müssen diese Kante löschen und den ungeraden Zyklus „durchbrechen“, damit Ihr Graph die Einschränkung des Problems erfüllt. Letztendlich möchten Sie den Gesamtanteil der Kanten minimieren, die Sie löschen müssen, um Ihr Diagramm richtig einzufärben.

Die parallele Wiederholung ermöglicht es Ihnen, eine hochdimensionale Version dieses Problems zu betrachten – eine, bei der Sie alle ungeraden Zyklen, die auftreten, durchbrechen müssen. Feige, Kindler und O'Donnell mussten zeigen, dass man, wenn die Anzahl der Dimensionen sehr groß wird, einen sehr großen Teil der Kanten löschen muss, um alle ungeraden Zyklen zu durchbrechen. Wenn das wahr wäre, würde es bedeuten, dass die parallele Wiederholung die Härte dieses „dummen Max-Cut“-Problems effektiv verstärken könnte.

Dabei entdeckte das Team einen merkwürdigen Zufall: Es gab eine geometrische Methode, um zu interpretieren, ob die parallele Wiederholung so funktionieren würde, wie sie es sich erhofft hatten. Das Geheimnis lag in der Oberfläche kubischer Schäume.

Von Zitrone bis Limonade

Ihr Problem, umgeschrieben in die Sprache der Schäume, lief darauf hinaus, zu zeigen, dass kugelförmige Würfel nicht existieren können – dass es unmöglich ist, den hochdimensionalen Raum entlang des ganzzahligen Gitters in Zellen zu unterteilen, deren Oberfläche viel kleiner ist als die des Würfels. (Eine größere Oberfläche entspricht der Notwendigkeit, mehr „schlechte“ Kanten im Graphen der ungeraden Zyklen zu löschen, wie die Informatiker zu zeigen hofften.)

"Wir dachten, oh, was für ein seltsames Geometrieproblem, aber das ist wahrscheinlich wahr, oder?" sagte O’Donnell. „Wir brauchten das wirklich, um die wahre Antwort zu sein.“ Aber er, Feige und Kindler konnten es nicht beweisen. Also im Jahr 2007, sie veröffentlichte ein Papier skizziert, wie sie dieses Problem nutzen wollten, um den UGC anzugreifen.

Schon bald wurden ihre Hoffnungen zunichte gemacht.

Ran Raz, ein theoretischer Informatiker in Princeton, der bereits mehrere wichtige Ergebnisse zur parallelen Wiederholung bewiesen hatte, war von ihrer Arbeit fasziniert. Er beschloss, die parallele Wiederholung für das Problem der ungeraden Zyklen zu analysieren, teilweise wegen der Verbindung zur Geometrie, die Feige, Kindler und O'Donnell aufgedeckt hatten.

Raz hat nicht mit dem Schaumproblem begonnen, sondern die Informatikversion der Frage direkt angegriffen. Er zeigte, dass man mit dem Löschen von viel weniger Kanten davonkommen kann, um alle ungeraden Zyklen in einem Graphen zu durchbrechen. Mit anderen Worten, die parallele Wiederholung kann die Härte dieses Max-Cut-Problems nicht ausreichend verstärken. „Die Parameter, die man genau durch parallele Wiederholung erhält, reichen genau nicht aus, um dies zu geben“, sagte Moshkovitz.

„Unser Plan, parallele Wiederholungen zu verwenden, um die Härte einzigartiger Spiele zu zeigen, hat nicht einmal im einfachsten Fall funktioniert“, sagte O'Donnell. "Das hat den ganzen Plan kaputt gemacht."

Obwohl enttäuschend, deutete das Ergebnis von Raz auch auf die Existenz kugelförmiger Würfel hin: Formen, die sich kacheln lassen n-dimensionaler Raum mit einer Oberfläche, die proportional zur Quadratwurzel von skaliert ist n. „Wir dachten, nun, machen wir Limonade aus Zitronen und nehmen dieses enttäuschende technische Ergebnis über parallele Wiederholung und diskrete Graphen und verwandeln es in ein ordentliches, interessantes Ergebnis in Geometrie“, sagte O'Donnell.

Er und Kindler in Zusammenarbeit mit den Informatikern Anup Rao und Avi Wigderson, brüteten über Raz' Beweis, bis sie seine Techniken gut genug gelernt hatten, um sie auf das Schaumproblem zu übertragen. 2008 haben sie das gezeigt kugelförmige Würfel sind durchaus möglich.

"Es ist eine nette Art, über das Problem zu argumentieren", sagte er Markus Braverman von Princeton. "Es ist wunderschön."

Und es warf Fragen auf der geometrischen Seite der Geschichte auf. Da sie Raz' Arbeit an parallelen Wiederholungen verwendet hatten, um ihre Kachelform zu konstruieren, hatten Kindler, O'Donnell, Rao und Wigderson am Ende etwas Hässliches und Frankenstein-ähnliches. Die Fliese war unordentlich und voller Vertiefungen. Mathematisch gesehen war es nicht konvex. Während dies für ihre Zwecke funktionierte, fehlten dem kugelförmigen Würfel Eigenschaften, die Mathematiker bevorzugen – Eigenschaften, die eine Form konkreter, leichter zu definieren und zu untersuchen und für potenzielle Anwendungen besser geeignet machen.

„Ihre Konstruktion hat etwas sehr Unbefriedigendes“, sagte Regev. „Es sieht aus wie eine Amöbe. Es sieht nicht so aus, wie man es erwarten würde, ein schöner Kachelkörper.“

Das wollten er und Naor herausfinden.

Ausbruch aus dem Käfig

Naor und Regev war von Anfang an klar, dass sie bei Null anfangen mussten. „Zum Teil, weil konvexe Körper so restriktiv sind, hatte keine der vorherigen Techniken eine Chance zu funktionieren“, sagte er Dor Minzer, ein theoretischer Informatiker am Massachusetts Institute of Technology.

Tatsächlich war es völlig plausibel, dass die Konvexität zu restriktiv wäre – dass es einen konvexen kugelförmigen Würfel einfach nicht gibt.

Aber letzten Monat haben Naor und Regev bewiesen, dass man partitionieren kann n-dimensionaler Raum entlang ganzzahliger Koordinaten mit einer konvexen Form, deren Oberfläche ziemlich nahe an der der Kugel liegt. Und sie taten es vollständig geometrisch – sie führten das Problem zu seinen mathematischen Wurzeln zurück.

Zunächst mussten sie ein großes Hindernis überwinden. Das kubische Schaumproblem erfordert, dass jede Kachel bei ganzzahligen Koordinaten zentriert ist. Aber im ganzzahligen Gitter gibt es sehr kurze Abstände zwischen einigen Punkten – und diese kurzen Abstände verursachen Probleme.

Betrachten Sie einen Punkt im zweidimensionalen Gitter. Es befindet sich 1 Einheit entfernt von seinen nächsten Punkten in horizontaler und vertikaler Richtung. Aber in diagonaler Richtung ist der nächste Punkt $latex sqrt{2}$ Einheiten entfernt – eine Diskrepanz, die in größeren Räumen noch schlimmer wird. Im n-dimensionalen Integer-Gitter, die nächsten Punkte sind immer noch 1 Einheit entfernt, aber diese „diagonalen“ Punkte sind jetzt $latex sqrt{n}$ Einheiten entfernt. In beispielsweise 10,000 Dimensionen bedeutet dies, dass der nächste „diagonale“ Nachbar zu jedem Punkt 100 Einheiten entfernt ist, obwohl es 10,000 andere Punkte (einen in jeder Richtung) gibt, die nur 1 Einheit entfernt sind.

In anderen Gittern wachsen diese beiden Arten von Abständen proportional zueinander. Mathematiker wissen seit Jahrzehnten, wie man solche Gitter mit konvexen Formen von minimaler Oberfläche kachelt.

Aber im ganzzahligen Gitter bleiben die kürzesten Abstände immer bei 1 hängen. Dies steht der Konstruktion einer gut aussehenden Kachel mit optimaler Oberfläche im Weg. „Sie haben dich irgendwie in diesen Käfig gesteckt“, sagte Regev. "Sie machen alles sehr eng um dich herum."

Also betrachteten Naor und Regev stattdessen ein Stück vom Ganzen n-dimensionaler Raum. Sie haben diesen Unterraum sorgfältig ausgewählt, damit er immer noch reich an ganzzahligen Punkten ist, aber keiner dieser Punkte zu nahe beieinander liegt.

Mit anderen Worten, der Teilraum, den sie am Ende hatten, war genau der Typ, von dem Mathematiker bereits wussten, wie man ihn optimal kachelt.

Aber das war nur die halbe Arbeit. Naor und Regev mussten den gesamten Raum aufteilen, nicht nur einen Teil davon. Um ein zu bekommen n-dimensionaler kugelförmiger Würfel, mussten sie ihre effiziente Kachel mit einer Kachel aus dem verbleibenden Raum multiplizieren (ähnlich wie man ein zweidimensionales Quadrat mit einem eindimensionalen Liniensegment multipliziert, um einen dreidimensionalen Würfel zu erhalten). Dies würde ihre Konstruktion wieder in den ursprünglichen Raum heben, aber auch ihre Oberfläche vergrößern.

Das Paar musste zeigen, dass die Kachel aus dem Restraum, die nicht so optimal war, nicht zu viel Fläche hinzufügt. Sobald sie das getan hatten, war ihre Konstruktion abgeschlossen. (Die Oberfläche ihrer endgültigen Form war am Ende etwas größer als die des nicht konvexen kugelförmigen Würfels, aber sie glauben, dass es möglich sein könnte, eine konvexe Kachel zu finden, die genauso effizient ist wie ihr nicht konvexes Gegenstück.)

„Ihr Beweis ist völlig anders“ als frühere Arbeiten an Kugelwürfeln, sagte der Mathematiker Noga Alon. „Und rückblickend ist es vielleicht ein natürlicherer Beweis. Damit hätte vielleicht jemand anfangen sollen.“

„Wenn die Dinge anders gemacht werden“, fügte Raz hinzu, „findet man manchmal interessante zusätzliche Implikationen.“

Hoffnung neu entfacht

Es ist noch nicht klar, was diese Implikationen sein könnten – obwohl die Arbeit die potenzielle Verwendung von ganzzahligen Gittern in der Kryptographie und anderen Anwendungen erschließt. Da dieses Problem mit anderen Feldern verbunden ist, „wird es wahrscheinlich zu anderen Dingen führen“, sagte Alon.

Derzeit sehen Informatiker keinen Weg, das konvexe Ergebnis in der Sprache der parallelen Wiederholung und des UGC zu interpretieren. Aber sie haben den ursprünglichen Plan, das Schaumproblem zu nutzen, um die Vermutung zu beweisen, nicht ganz aufgegeben. „Es gibt verschiedene Möglichkeiten, wie Sie versuchen können, die offensichtlichen Barrieren, auf die wir gestoßen sind, zu untergraben“, sagte Kindler.

Braverman und Minzer versuchten einen solchen Weg, als sie revisited Schäume im Jahr 2020. Anstatt zu verlangen, dass die Kachelform konvex ist, forderten sie, dass sie bestimmten Symmetrien gehorcht, sodass sie gleich aussieht, egal wie Sie ihre Koordinaten umdrehen. (In 2D würde ein Quadrat funktionieren, aber ein Rechteck nicht; die bisher beschriebenen hochdimensionalen kugelförmigen Würfel auch nicht.) Unter dieser neuen Einschränkung war das Paar in der Lage zu zeigen, was Kindler und andere 15 Jahre zuvor gehofft hatten: die man nicht viel besser machen kann als die Oberfläche des Würfels.

Dies entsprach einer anderen Art paralleler Wiederholung – einer, die den einfachsten Fall von Max Cut so schwierig machen würde, wie es sein musste. Während das Ergebnis einige Hoffnung für diese Forschungsrichtung bietet, ist es nicht klar, ob diese Version der parallelen Wiederholung für alle Max-Cut-Probleme funktionieren wird. „Das bedeutet nicht, dass Sie fertig sind“, sagte Braverman. "Es bedeutet nur, dass Sie wieder im Geschäft sind."

„Es gibt viel Potenzial in der Geometrie“, sagte Minzer. "Es ist nur so, dass wir es nicht gut genug verstehen."