Pages that link to "Item:Q862399"
From MaRDI portal
The following pages link to Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas (Q862399):
Displaying 27 items.
- A dichotomy for local small-bias generators (Q315550) (← links)
- Cryptographic hardness of random local functions. Survey (Q332271) (← links)
- Toward a model for backtracking and dynamic programming (Q430838) (← links)
- Special issue in memory of Misha Alekhnovich. Foreword (Q430839) (← links)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs (Q430840) (← links)
- A note on SAT algorithms and proof complexity (Q436581) (← links)
- On linear-size pseudorandom generators and hardcore functions (Q744085) (← links)
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT (Q764375) (← links)
- On exponential time lower bound of Knapsack under backtracking (Q964408) (← links)
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms (Q1678752) (← links)
- Hard satisfiable formulas for splittings by linear combinations (Q1680241) (← links)
- The complexity of inverting explicit Goldreich's function by DPLL algorithms (Q1946844) (← links)
- On the complexity of choosing the branching literal in DPLL (Q1978252) (← links)
- Non-interactive zero-knowledge in pairing-free groups from weaker assumptions (Q2055663) (← links)
- Limitations of restricted branching in clause learning (Q2272157) (← links)
- Resolution over linear equations modulo two (Q2334112) (← links)
- Locally computable UOWHF with linear shrinkage (Q2408584) (← links)
- Hard satisfiable instances for DPLL-type algorithms (Q2577593) (← links)
- Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle (Q2818003) (← links)
- On the one-way function candidate proposed by Goldreich (Q2828220) (← links)
- The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms (Q3007623) (← links)
- Fast Pseudorandom Functions Based on Expander Graphs (Q3179351) (← links)
- Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets (Q3448816) (← links)
- Automata, Languages and Programming (Q5466449) (← links)
- Parameterized Complexity of DPLL Search Procedures (Q5892559) (← links)
- On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator (Q6095188) (← links)
- Advice complexity of adaptive priority algorithms (Q6180750) (← links)
