May 4, Wednesday
12:00 – 13:00
Holographic Computation of Balanced Succinct Permanent Instances
Graduate seminar
Lecturer : Nova Fandina
Affiliation : CS, BGU
Location : 202/37
Host : Gaduate Seminar
Galperin and Wigderson proposed a succinct representation for graphs,
that uses number of bits that is logarithmic in the number of nodes. They proved
complexity results for various decision problems on graph properties, when the
graph is given in a succinct representation. Later, Papadimitriou and Yannakakis
showed, that under the same succinct encoding method, certain class of decision
problems on graph properties becomes exponentially hard. We consider
the complexity of the Permanent problem when the graph/matrix is given
in a restrict succinct representation. We present an optical architecture that is
based on the holographic concept for solving balanced inputs of the Succinct Permanent problem.
The talk will include both a theoretical results (relating establishing a computational complexity of some problems) and
an optical implementation of the proposed algorithm.