The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
An infinite sequence F={fn} n=1∞ of one-output Boolean functions with the following three properties is constructed: (1) fn can be computed by a Boolean circuit with O(n) gates. (2) For any positive, nondecreasing, and unbounded function h : N → R, each Boolean circuit having an n/h(n) separator requires nonlinear number of...
The communication complexity is an abstract complexity measure intensively investigated in the last few years. Since it provides lower bounds on the area (A) and area time squared (AT2) complexity measures of VLSI computations, the main interest is in proving lower bounds on communication complexity of specific languages. We present a new combinatorial technique in order to establish a...
Pebble game on dynamic graphs is studied as an abstract model for the incremental computations. We investigate how the time T and/or the space S is changing according to the number m of insert-edge/delete-edge operations on directed acyclic graphs of size n. Time-space trade-off of the form T= Θ (n2/S+m) is given for standard pebble game on permutation graphs. In the case of the minimal...
The complexity of systolic dissemination of information in one-way (telegraph) and two-way (telephone) communication mode is investigated. The following main results are established: (i) tight lower and upper bounds on the complexity of one-way systolic gossip in cycles for any length of the systolic period, (ii) optimal one-way and two-way systolic gossip algorithms in 2-dimensional grids whose...