Exponential Time Paradigms in Computational Algorithms

Exponential Time Paradigms Through the Polynomial Time Lens Joint work with Andy Drucker and Rahul Santhanam Jesper Nederlof Technical University Eindhoven

General Pattern of Scalability Given more resources, solutions become more complex Poor man s solution Rich man s solution (Exponential time) (Polynomial time) Known exponential time algorithms mostly use algorithmic paradigms from P-time algorithms Program: Formalize such paradigms and study their power and limitations

Paradigms in exp. time / FPT algorithms Preprocessing Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, no models studied Dynamic Programming Often applied; several models studied New consequences New LB s New model New model + reductions

Paradigms in exp. time / FPT algorithms Preprocessing Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, no models studied Dynamic Programming Often applied; several models studied

Paradigms in exp. time / FPT algorithms Preprocessing Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Strengths: Contains poly time algorithms (poly time `for free ) Lower bounds under hypothesis concerning PTIME General template to give LB s (OR/AND-composition)

Paradigms in exp. time / FPT algorithms Preprocessing Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, no models studied Dynamic Programming Often applied; several models studied

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) Poly time algo s without false positives but if given YES- instance, return YES with exponentially small success prob Example: Given graph and int ?, finding ? vertices incident to all edges by picking random endpoints of uncovered edges: success prob. ? ? for Vertex Cover (VC) success prob. ? ?(?)equivalent* with f(k)-bit witnesses E.g. VC has verifiers accepting certificates of length k Backwards trivial, forwards requires hashing ideas *modulo randomness

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Strengths: Contains poly time algorithms (poly time `for free ) Generalizes* kernelization Lower bounds under hypothesis concerning PTIME Many algorithms captured by this model Not well studied yet: we further explore this here All our lower bounds build on D 13

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Example theorem Suppose there is a poly algo that, given planar graph on ? vertices, outputs a maximum independent set with probability exp( ?1 ?) for some ? > 0. Then ?? ????/????. We also observe one can get probability exp( ?/ log?) Note that in contrast exp( ?) time algorithms exist

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13)

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions.

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions.

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions. all known AND-compositions are constructive indicates problems admitting AND-compositions* do not admit polynomial OR-kernelizations* Cor: Suppose there is a poly time algorithm that, given tree decomposition of ? of width ? outputs a max. IS with probability 2 ????(?), then ?? ????/????

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions. all known AND-compositions are constructive indicates problems admitting AND-compositions* do not admit polynomial OR-kernelizations* We currently exclude poly kernels via OR/AND compositions Observation: the known FPT algorithm for DFVS gives a poly algorithm finding a DFVS of size ? with succ prob 2 ?(? ?? ?) Cor: Directed FVS has no AND-composition* unless ?? ????/????

Paradigms in exp. time / FPT algorithms Preprocessing Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, no models studied Dynamic Programming Often applied; several models studied

Parity Compression We saw strong limitations of large classes of exponential time algorithms under hypotheses on polynomial time Inspired by this, we model other paradigms similarly OPP algo s are Monte Carlo reductions to Circuit Sat with few input gates (the circuit simulates the verifier) Parity compression is a Monte Carlo reduction to Circuit Sat Circuit Sat: count #satisfying assignments modulo 2 Many algorithms can be rewritten as parity compressions BHKK 10: ?-path in ? (23?/4)-> polynomial time reduction from ?-path to Circuit Sat on 3?/4 inputs

Summary Paradigms are modeled as polynomial time reductions to wisely chosen problems Our contributions (highlights): Lower bounds on success probability of poly time algo s Consequences for kernelization theory Constructive AND-compositions* exclude ????(?) witnesses* (and thus OR-kernels*) DFVS does not admit AND-compositions* Proposed `parity compression and `disjunctive DP to model other paradigms

Further Research Is there a poly algo that given ?1, ,??,? returns ? {1, ,?} with ? X ??= ? with prob 1/????(?), if such ? exists? Currently only known ????(??) time, poly space algo uses DFT (LN 10) Can we rule out such an algo with an AND-composition? Can OPP algo s refute SETH? Is there are problem with poly compressions but not poly witnesses (?-cycle)? Quite a new direction with many things to explore, so please join! Full version available at www.win.tue.nl/~jnederlo Thanks for listening!! www.win.tue.nl/~jnederlo