Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k Forall-Quantified First-Order Graph Properties
Speaker:Nick Fischer
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 11 July 2019
Duration:30 Minutes
Building:E1 4
An important class of problems in logics and database theory is given by fixing a first-order property $\psi$ over a relational structure, and considering the model-checking problem for $\psi$. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of fine-grained complexity in P, by showing that the \emph{(Sparse) Orthogonal Vectors} problem is complete for this class under fine-grained reductions. This raises the question whether fine-grained complexity can yield a precise understanding of all first-order model-checking problems. Specifically, can we determine, for any fixed first-order property $\psi$, the exponent of the optimal running time $O(m^{c_\psi})$, where $m$ denotes the number of tuples in the relational structure?

Towards answering this question, in this work we give a dichotomy for the class of $\exists^k \forall$-quantified graph properties. For every such property $\psi$, we either give a polynomial-time improvement over the baseline $O(m^k)$-time algorithm or show that it requires time $m^{k-o(1)}$ under the hypothesis that MAX3SAT has no $O((2-\epsilon)^n)$-time algorithm. More precisely, we define a hardness parameter $h = H(\psi)$ such that $\psi$ can be decided in time $O(m^{k-\epsilon})$ if $h \le 2$ and requires time $m^{k-o(1)}$ for $h \ge 3$ unless the $h$-uniform Hyperclique hypothesis fails. This unveils a natural hardness hierarchy within first-order properties: for any $h \ge 3$, we show that there exists a $\exists^k \forall$-quantified graph property $\psi$ with hardness $H(\psi)= h$ that is solvable in time $\Order(m^{k-\epsilon})$ \emph{if and only if} the $h$-uniform Hyperclique hypothesis fails. Finally, we give more precise upper and lower bounds for an exemplary class of formulas with $k = 3$ and extend our classification to a counting dichotomy.

Name(s):Nick Fischer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Nick Fischer, 07/08/2019 02:39 PM -- Created document.