G. Schnitger
Min-Rank Conjecture for Log-Depth Circuits.
Fri, 05/07/2010 - 15:02 — SomNambulAuthors: S. Jukna, G. Schnitger
Subjects: Computational Complexity
AbstractA completion of an m-by-n matrix A with entries in {0,1,*} is obtained by
setting all *-entries to constants 0 or 1. A system of semi-linear equations
over GF(2) has the form Mx=f(x), where M is a completion of A and f:{0,1}^n -->
{0,1}^m is an operator, the i-th coordinate of which can only depend on
variables corresponding to *-entries in the i-th row of A. We conjecture that
no such system can have more than 2^{n-c\cdot mr(A)} solutions, where c>0 is an
absolute constant and mr(A) is the smallest rank over GF(2) of a completion of
A.Circuits with arbitrary gates for random operators.
Fri, 04/30/2010 - 15:01 — SomNambulAuthors: S. Jukna, G. Schnitger
Subjects: Computational Complexity
AbstractWe consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As
gates we allow arbitrary boolean functions; neither fanin nor fanout of gates
is restricted. An operator is linear if it computes n linear forms, that is,
computes a matrix-vector product y=Ax over GF(2). We prove the existence of
n-operators requiring about n^2 wires in any circuit, and linear n-operators
requiring about n^2/\log n wires in depth-2 circuits, if either all output
gates or all gates on the middle layer are linear.
User login
