Pages that link to "Item:Q4406287"
From MaRDI portal
The following pages link to Short proofs are narrow—resolution made simple (Q4406287):
Displaying 50 items.
- Cryptographic hardness of random local functions. Survey (Q332271) (← links)
- A general model and thresholds for random constraint satisfaction problems (Q359981) (← links)
- Satisfiability, branch-width and Tseitin tautologies (Q430830) (← links)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs (Q430840) (← links)
- On the power of clause-learning SAT solvers as resolution engines (Q543613) (← links)
- The depth of resolution proofs (Q647405) (← links)
- Cutting planes and the parameter cutwidth (Q693047) (← links)
- Mean-payoff games and propositional proofs (Q716324) (← links)
- Short propositional refutations for dense random 3CNF formulas (Q741088) (← links)
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT (Q764375) (← links)
- Spines of random constraint satisfaction problems: definition and connection with computational complexity (Q812393) (← links)
- Proof complexity of modal resolution (Q832717) (← links)
- Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability (Q840834) (← links)
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas (Q862399) (← links)
- Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis (Q894453) (← links)
- A simplified way of proving trade-off results for resolution (Q989569) (← links)
- A combinatorial characterization of treelike resolution space (Q1014444) (← links)
- Finding a tree structure in a resolution proof is NP-complete (Q1019749) (← links)
- Random constraint satisfaction: easy generation of hard (satisfiable) instances (Q1028939) (← links)
- Resolution for Max-SAT (Q1028942) (← links)
- The intractability of resolution (Q1071750) (← links)
- Resolution lower bounds for the weak functional pigeonhole principle. (Q1401365) (← links)
- Proving unsatisfiability of CNFs locally (Q1610678) (← links)
- On space and depth in resolution (Q1616620) (← links)
- A note about \(k\)-DNF resolution (Q1641156) (← links)
- Relating size and width in variants of Q-resolution (Q1653019) (← links)
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms (Q1678752) (← links)
- Cliques enumeration and tree-like resolution proofs (Q1708271) (← links)
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution (Q1854546) (← links)
- On the automatizability of resolution and related propositional proof systems (Q1881219) (← links)
- Resolution lower bounds for perfect matching principles (Q1881260) (← links)
- On the complexity of resolution with bounded conjunctions (Q1885907) (← links)
- A sharp threshold in proof complexity yields lower bounds for satisfiability search (Q1887710) (← links)
- The complexity of inverting explicit Goldreich's function by DPLL algorithms (Q1946844) (← links)
- On the automatizability of polynomial calculus (Q1959382) (← links)
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs (Q1983330) (← links)
- Lower bound techniques for QBF expansion (Q1987510) (← links)
- The satisfiability threshold for random linear equations (Q2003764) (← links)
- The treewidth of proofs (Q2013559) (← links)
- Space proof complexity for random 3-CNFs (Q2013560) (← links)
- Resolution with counting: dag-like lower bounds and different moduli (Q2029775) (← links)
- Reversible pebble games and the relation between tree-like and general resolution space (Q2033469) (← links)
- Nullstellensatz size-degree trade-offs from reversible pebbling (Q2040600) (← links)
- Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search (Q2074664) (← links)
- Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
- Lower bounds for QCDCL via formula gauge (Q2118284) (← links)
- On the hierarchical community structure of practical Boolean formulas (Q2118321) (← links)
- Partially definable forcing and bounded arithmetic (Q2257103) (← links)
- Characterising tree-like Frege proofs for QBF (Q2272983) (← links)
- Random resolution refutations (Q2311546) (← links)
