Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- ArticleJuly 2023
Solving 3SAT and MIS Problems with Analog Quantum Machines
Computational Science and Its Applications – ICCSA 2023 WorkshopsPages 429–439https://doi.org/10.1007/978-3-031-37105-9_29AbstractThis work considers the use of analog quantum machines to solve the boolean satisfiability problem 3SAT by taking Quadratic Unconstrained Binary Optimization models (QUBO) as input. With the aim of using real quantum computers instead of emulators ...
- abstractMarch 2017
Improving SAT-solving with Machine Learning
SIGCSE '17: Proceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science EducationPages 787–788https://doi.org/10.1145/3017680.3022464In this project, we aimed to improve the runtime of Minisat, a Conflict-Driven Clause Learning (CDCL) solver that solves the Propositional Boolean Satisfiability (SAT) problem. We first used a logistic regression model to predict the satisfiability of ...
- articleMarch 2013
Optimal Reconstruction Might be Hard
Discrete & Computational Geometry (DCOG), Volume 49, Issue 2Pages 133–156https://doi.org/10.1007/s00454-012-9475-8Given as input a point set $$\mathcal S $$ that samples a shape $$\mathcal A $$, the condition required for inferring Betti numbers of $$\mathcal A $$ from $$\mathcal S $$ in polynomial time is much weaker than the conditions required by any known ...
- articleJuly 2011
Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems
One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472-476, 2001) proposed the ...
- research-articleJune 2010
Optimal reconstruction might be hard
SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometryPages 334–343https://doi.org/10.1145/1810959.1811014Sampling conditions for recovering the homology of a set using topological persistence are much weaker than sampling conditions required by any known polynomial time algorithm for producing a topologically correct reconstruction. Under the former ...
- ArticleJune 2008
The Power of Unentanglement
CCC '08: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational ComplexityPages 223–236https://doi.org/10.1109/CCC.2008.5The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence ...
- research-articleJune 1990
On the Multiple-Query Optimization Problem
IEEE Transactions on Knowledge and Data Engineering (IEEECS_TKDE), Volume 2, Issue 2Pages 262–266https://doi.org/10.1109/69.54724The complexity of the multiple-query optimization problem in database management systems is examined. It is shown that the problem is NP-hard. Then the authors examine the performance of a heuristic algorithm to solve the multiple-query optimization ...