The 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics, LIPIcs 58 2016年8月 [査読有り]
A Boolean function f : {0, 1}n → {0, 1} is weighted symmetric if there exist a function g : ℤ → {0, 1} and integers w0,w1, . . . ,wn such that f(x1, . . . , xn) = g(w0 + ∑n i=1 wixi) holds. In this paper, we present algorithms for the circuit sati...
Alexander Golovnev Alexander S. Kulikov Alexander V. Smal Suguru Tamaki
The 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics, LIPIcs 58 2016年8月 [査読有り]
Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones...
Interdisciplinary Information Sciences 21(4) 289-306 2015年12月 [査読有り]
A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics. The parallel repetition theorem states that for an...
大学本部
社会情報科学部