Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Algo
Time-space tradeoffs for width-parameterized SAT
Periklis A. Papakonstantinou

29 June 2012, 14h30 - 29 June 2012, 15h30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
SAT, short for satisfiability, is probably the most decorated
and
applicable NP-hard problem. Empirical studies show that:
(i) state-of-the-art SAT solvers abort mainly due to lack of memory, and
(ii) real-life SAT instances come with structure.
We systematically study time-space tradeoffs for solving SAT,
parameterized by path-width & tree-width; two popular ways to quantify
how much structured is the input instance.

In particular, we (conditionally) resolve the main open question
of Alekhnovitch and Razborov (2002) which has as follows:

"Is it possible to solve SAT of treewidth w(n) simultaneously in
time-space (poly(n) 2^O(w), poly(n))?"

We show that in the incidence graph there is a simple
algorithm running in time-space (poly(n) 2^O(w*logn), poly(n)).
We furthermore, show that removing this logn factor from the time
exponent incurs an exponential blow up in the space
unless NC subseteq SC (or its scalled analogs).
That is, ignoring constants in the exponent,
if you pay a logn in the exponent then
you can bring the space down to polynomial, but other than this
there is nothing else you can do.

Finally, we devise algorithms showing that it is possible to trade
constants in the exponent between time and space.

If time permits, I'll outline some new connections and directions
of our work to propositional proof complexity (the first step has
already been taken by Beame-Beck-Impagliazzo 2012).

Pour en savoir plus :
Séminaires
Some recent results on the integer linear programm
Théorie des graphes
Friday 12 October 2018 - 14h30
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Maximum Independent Set in H-free graphs
Théorie des graphes
Friday 05 October 2018 - 14h30
Salle : 445 - PCRI-N
Edouard BONNET .............................................

A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 29 June 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................