Title	Hard Satisfiable Formulas for Splittings by Linear Combinations
Creator	Knop, Alexander
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2018-08-31T11:44
Description	Itsykson and Sokolov in 2014 introduced the class of DPLL(xor) algorithms that solve Boolean satisfiability problem using the splitting by linear combinations of variables modulo 2. This class extends the class of DPLL algorithms that split by variables. DPLL(xor) algorithms solve in polynomial time systems of linear equations modulo 2 that are hard for DPLL, PPSZ and CDCL algorithms. Itsykson and Sokolov have proved first exponential lower bounds for DPLL(xor) algorithms on unsatisfiable formulas. In the talk, we discuss several subclasses of DPLL(xor) algorithms and explain lower bounds for one of them.
Extent	26.0
Subject	Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: UC San Diego
Series	BIRS Workshop Lecture Videos (Oaxaca de Juárez (Mexico))
Date Available	2019-04-05
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0377822
URI	http://hdl.handle.net/2429/69476
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Postdoctoral
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos