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|
|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
|Date:||11 / 20 / 2013|
|Time:||04:40pm - 05:30pm|