PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Jason Morton.

Title:Tensor Contractions for #SAT
Seminar:Applied Algebra and Network Theory Seminar
Speaker:Jacob Biamonte, ISI Foundation
Abstract Link:http://qubit.org/jacob-biamonte.html
Abstract:
Boolean formula satisfiability and solution counting are foundational topics faced in theoretical computer science with numerous practical applications. Recently, the simulation of quantum systems has experienced advancements due to the development of tensor network algorithms and associated quantum physics based techniques. Taking inspiration from these physics based algorithms, we propose a tensor contraction algorithm for \#SAT instances which we show has $O(t2^c)$ complexity, (where $t$ is the polynomial bounding the computation of contracting a tree tensor network and $c$ is the number of COPY tensors in the network. The broader implications of this line of work involve the use of tensor network methods as a language uniting parts of quantum theory and computer science.

Room Reservation Information

Room Number:MB106
Date:11 / 20 / 2013
Time:04:40pm - 05:30pm