Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Information flows, graphs and their guessing numbers. | Information flows graphs and their guessing numbers S0ren Riis Queen Mary University of London smriis@ Submitted Jan 9 2006 Accepted May 28 2007 Published Jun 7 2007 Mathematics Subject Classification 05C20 68Q17 68R10 Abstract Valiant s shift problem asks whether all n cyclic shifts on n bits can be realized if n 1 e input output pairs e 1 are directly connected and there are additionally m common bits available that can be arbitrary functions of all the inputs. If it could be shown that this is not realizable with m O log 0gn common bits then a significant breakthrough in Boolean circuit complexity would follow. In this paper it is shown that in certain cases all cyclic shifts are realizable with m n ne 2 common bits. Previously no solution with m n o n was known and Valiant had conjectured that m n 2 was not achievable. The construction therefore establishes a novel way of realizing communication in the manner of Network Coding for the shift problem but leaves the viability of the common information approach to proving lower bounds in Circuit Complexity open. The construction uses the graph-theoretic notion of guessing number. As a by-product the paper also establish an interesting link between Circuit Complexity and Network Coding a new direction of research in multiuser information theory. 1 Introduction The problem of proving superlinear lower bounds on the size of circuits for an explicitly defined sequence of Boolean functions is still open after more than 30 years of intensive research in Complexity Theory. The problem is open even if we consider the case where we look for functions with n input bits and n output bits and where the depth of the circuit is in O log n . For a detailed discussion and further survey of this class of problems and their link to communication complexity and matrix rigidity see 7 . In this paper we relate this fundamental problem in Complexity Theory more specifically we focus on Valiant s Shift problem that has been
