Kürzlich gab es einige neue Ergebnisse zur computergestützten experimentellen Untersuchung des Erdos-Diskrepanzproblems (EDP) (über SAT-Löser, siehe unten). Dieses Problem wurde von mehreren (T) CS-Forschern angeführt und untersucht. Die (möglicherweise tiefen?) Links zu (T) CS sind jedoch nicht so offensichtlich.
Was sind die Links der EDV zu (T) CS?
Hier sind einige Referenzen, die das Interesse der (T) CS-Community an EDV zeigen:
SAT-Angriff von Konev und Lisitsa auf EDV und Reaktion von Gowers ; auch andere Verbindungen zu empirischen / experimentellen TCS (z. B. automatisierte SAT-Theorembeweise)
Einführung in EDV und Techniken auf Liptons Blog
EDV und differenzieller Datenschutz im Windows on Theory-Blog von Talwar
EDV-Polymath-Projekt mit einigen Beiträgen von Informatikern
Antworten:
Es gibt viele Verbindungen zwischen Diskrepanztheorie und Informatik, und Bernard Chazelle hat einige davon in seinem Buch wunderschön untersucht . In jüngerer Zeit wurde auch eine Reihe von Links gefunden, beispielsweise in Kunals Blogbeitrag über die Verbindung von [MN] und [NTZ] zu differenzierter Privatsphäre . Ein weiteres Beispiel ist Larsens Idee , Diskrepanzen zu verwenden, um die unteren Grenzen der Aktualisierungs- / Abfragezeit für dynamische Datenstrukturen zu beweisen. Viele dieser Verknüpfungen können mit homogenen arithmetischen Fortschritten (HAPs) instanziiert werden. Dies würde geben:
Es gibt jedoch zwei Dinge, die Sie in Bezug auf diese Links beachten müssen. Zum einen ist nicht klar, dass Bereichsbereiche von HAPs sehr natürlich sind. Wann erwarten Sie eine Eingabe, die aus mehreren Ganzzahlen besteht, und möchten antworten, wie viele Elemente eines HAP in der Eingabe enthalten sind? Ich kann mir keine Situation vorstellen, in der dies auftritt, aber vielleicht fehlt mir etwas.
Eine andere Sache, die Sie erkennen müssen, ist, dass alle diese Anwendungen auf dem Begriff der erblichen Diskrepanz beruhen . Dieser Begriff ist robuster als Diskrepanzen, was ihn leichter handhabbar macht: Es stehen stärkere Untergrenzen für ihn zur Verfügung, er ist annähernd innerhalb polylogarithmischer Faktoren und entspricht ungefähr dem Wert eines konvexen Optimierungsproblems. Das Ergebnis, über das Kunal im Blog-Beitrag spricht (Papier ist hier ) und die Konstruktion von Alon und Kalai, über die Kalai in diesem Blog-Beitrag geschrieben hatgemeinsam im Wesentlichen die erbliche Diskrepanz von HAPs regeln. Wie Kunal erklärt, beruhte die Intuition für die Untergrenze der erblichen Diskrepanz von HAPs auf der engen Verbindung zwischen erblicher Diskrepanz und differenzieller Privatsphäre, zusammen mit früheren Ergebnissen bei differenzierter Privatsphäre.
Bei EDV geht es jedoch um die Diskrepanz von HAPs. Die Diskrepanz ist viel spröder als die erbliche Diskrepanz, und das erschwert die Untergrenze. Dies macht es auch in Anwendungen weniger nützlich als erbliche Diskrepanz. Und deshalb ist die EDV noch weit offen, während die Frage der erblichen Diskrepanz ziemlich gut verstanden ist.
Lassen Sie mich mit einem Ansatz zum Angriff auf EDV abschließen, der von Ideen der Informatik inspiriert ist. Es gibt eine Möglichkeit, die Diskrepanz zu einem semidefiniten Programm zu verringern. Weitere Informationen finden Sie in der Umfrage von Bansal. Der optimale Wert des semidefiniten Programms ist durch den Wert jeder möglichen Lösung seines dualen Programms begrenzt. Man kann also versuchen, EDV zu beweisen, indem man eine Familie von Doppellösungen für diese semidefinite Relaxation der Diskrepanz zeigt und zeigt, dass der Wert der Doppellösungen bis ins Unendliche geht. Ich sehe keinen Grund, warum ein solcher Angriff nicht funktionieren kann, insbesondere wissen wir nicht, wie wir Lösungen für die semidefinite Relaxation konstruieren können, die für beliebig große Instanzen einen konstanten Wert haben. Tatsächlich konzentrierte sich ein Großteil der Bemühungen in polymath5 darauf, doppelte Lösungen mit einer bestimmten Struktur zu finden oder auszuschließen.
quelle