4 papers
From k-SAT to k-CSP: Two Generalized Algorithms
Liang Li, Xin Li, Tian Liu +1
Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bou…
On Exponential Time Lower Bound of Knapsack under Backtracking
Xin Li, Tian Liu
M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dy…
On Lower Bound of Worst Case Error Probability for Quantum Fingerprinting with Shared Entanglement
Xin Li, Tian Liu, Han Peng +2
This paper discusses properties of quantum fingerprinting with shared entanglement. Under certain restriction of final measurement, a relation is given between unitary operations o…
Improved Exponential Time Lower Bound of Knapsack Problem under BT model
Xin Li, Tian Liu, Han Peng +2
M.Alekhnovich et al. recently have proposed a model of algorithms, called BT model, which covers Greedy, Backtrack and Simple Dynamic Programming methods and can be further divided…