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.
We study the proof complexity of Taut, the class of Second-Order Existential (SO∃) logical sentences which fail in all finite models. The Complexity-Gap theorem for Tree-like Resolution says that the shortest Tree-like Resolution refutation of any such sentence Φ is either fully exponential, $2^{\Omega \left(n\right)}$ , or polynomial, $n^{O\left(1\right)}$ , where n is the size of the finite...
Guessing games for directed graphs were introduced by Riis [8] for studying multiple unicast network coding problems. It can be shown that protocols for a multiple unicast network can be directly converted into a strategy for a guessing game. The performance of the optimal strategy for a graph is measured by the guessing number, and this number can be bounded from above using information inequalities...
A symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms, was recently introduced. Many communication problems can be recast as dispersion problems in this setup. The so-called min-cut of a term set represents its number of degrees of freedom. For any assignment of function symbols, its dispersion measures the amount of information...
Traditionally, communication networks are modeled and analyzed in terms of information flows in graphs. In this paper, we introduce a new symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms. To any choice of coding functions we associate a measure of performance, referred to as the dispersion. Many communication problems can...
A symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms, was recently introduced. The so-called min-cut of a term set represents its number of degrees of freedom. For any assignment of function symbols, its dispersion measures the amount of information sent to the destinations and its Renyi entropies measure the amount of information...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.