The Experts below are selected from a list of 6618 Experts worldwide ranked by ideXlab platform
Alfredo Viola - One of the best experts on this subject based on the ideXlab platform.
-
equivalence classes of boolean functions for first order correlation
IEEE Transactions on Information Theory, 2010Co-Authors: J Le M Bars, Alfredo ViolaAbstract:This paper presents a complete characterization of the first order correlation immune Boolean functions that includes the functions that are 1-resilient. The approach consists in defining an equivalence relation on the full set of Boolean functions with a fixed number of variables. An equivalence class in this relation, called a first-order correlation class, provides a measure of the distance between the Boolean functions it contains and the correlation-immune Boolean functions. The key idea consists on manipulating only the equivalence classes instead of the set of Boolean functions. To achieve this goal, a class operator is introduced to construct a class with n variables from two classes of n - 1 variables. In particular, the class of 1-resilient functions on n variables is considered. An original and efficient method to enumerate all the Boolean functions in this class is proposed by performing a Recursive Decomposition of classes with less variables. A bottom up algorithm provides the exact number of 1-resilient Boolean functions with seven variables which is 23478015754788854439497622689296. A tight estimation of the number of 1-resilient functions with eight variables is obtained by performing a partial enumeration. It is conjectured that the exact complete enumeration for general n is intractable.
-
equivalence classes of boolean functions for first order correlation
International Symposium on Information Theory, 2007Co-Authors: J Le M Bars, Alfredo ViolaAbstract:Boolean functions are very important cryptographic primitives in stream or block ciphers. In this context, these functions need to satisfy good properties like high algebraic degree, nonlinearity and correlation immunity. We present here an original and efficient method to enumerate all the correlation-immune functions of a fixed Hamming weight, in particular the class of 1-resilient functions. The key idea consists in defining equivalent classes to split boolean functions along their distance from correlation-immune boolean functions. These classes, called first-order correlation classes, are built using a Recursive Decomposition of smaller classes. We derive from this method several algorithms to enumerate their elements and to count their cardinality. We first show that the exact number of 1-resilient boolean functions with 7 variables is 23478015754788854439497622689296 and we obtain a tight estimation of their number with 8 variables, between 4 1067 and 5.6 1068. We then present a general lower bound for the number of 1-resilient boolean functions and improve Schneider's upper bound. We also propose a general lower bound for the number of k-resilient functions. Most of the bounds presented in this paper, substantially improve the best known bounds in the literature. We finally establish that the probability of a Boolean function being 1-resilient is asymptotically between (npi)n/2/2n2-3/2n-1en-1/2.
J Le M Bars - One of the best experts on this subject based on the ideXlab platform.
-
equivalence classes of boolean functions for first order correlation
IEEE Transactions on Information Theory, 2010Co-Authors: J Le M Bars, Alfredo ViolaAbstract:This paper presents a complete characterization of the first order correlation immune Boolean functions that includes the functions that are 1-resilient. The approach consists in defining an equivalence relation on the full set of Boolean functions with a fixed number of variables. An equivalence class in this relation, called a first-order correlation class, provides a measure of the distance between the Boolean functions it contains and the correlation-immune Boolean functions. The key idea consists on manipulating only the equivalence classes instead of the set of Boolean functions. To achieve this goal, a class operator is introduced to construct a class with n variables from two classes of n - 1 variables. In particular, the class of 1-resilient functions on n variables is considered. An original and efficient method to enumerate all the Boolean functions in this class is proposed by performing a Recursive Decomposition of classes with less variables. A bottom up algorithm provides the exact number of 1-resilient Boolean functions with seven variables which is 23478015754788854439497622689296. A tight estimation of the number of 1-resilient functions with eight variables is obtained by performing a partial enumeration. It is conjectured that the exact complete enumeration for general n is intractable.
-
equivalence classes of boolean functions for first order correlation
International Symposium on Information Theory, 2007Co-Authors: J Le M Bars, Alfredo ViolaAbstract:Boolean functions are very important cryptographic primitives in stream or block ciphers. In this context, these functions need to satisfy good properties like high algebraic degree, nonlinearity and correlation immunity. We present here an original and efficient method to enumerate all the correlation-immune functions of a fixed Hamming weight, in particular the class of 1-resilient functions. The key idea consists in defining equivalent classes to split boolean functions along their distance from correlation-immune boolean functions. These classes, called first-order correlation classes, are built using a Recursive Decomposition of smaller classes. We derive from this method several algorithms to enumerate their elements and to count their cardinality. We first show that the exact number of 1-resilient boolean functions with 7 variables is 23478015754788854439497622689296 and we obtain a tight estimation of their number with 8 variables, between 4 1067 and 5.6 1068. We then present a general lower bound for the number of 1-resilient boolean functions and improve Schneider's upper bound. We also propose a general lower bound for the number of k-resilient functions. Most of the bounds presented in this paper, substantially improve the best known bounds in the literature. We finally establish that the probability of a Boolean function being 1-resilient is asymptotically between (npi)n/2/2n2-3/2n-1en-1/2.
M. Venkatramam - One of the best experts on this subject based on the ideXlab platform.
-
Very low bit-rate video coding using variable block-size entropy-constrained residual vector quantizers
IEEE Journal on Selected Areas in Communications, 1997Co-Authors: Heesung Kwon, M. VenkatramamAbstract:We present a practical video coding algorithm for use at very low bit rates. For efficient coding at very low bit rates, it is important to intelligently allocate bits within a frame, and so a powerful variable-rate algorithm is required. We use vector quantization to encode the motion-compensated residue signal in an H.263-like framework. For a given complexity, it is well understood that structured vector quantizers perform better than unstructured and unconstrained vector quantizers. A combination of structured vector quantizers is used in our work to encode the video sequences. The proposed codec is a multistage residual vector quantizer, with transform vector quantizers in the initial stages. The transform-VQ captures the low-frequency information, using only a small portion of the bit budget, while the later stage residual VQ captures the high-frequency information, using the remaining bits. We used a strategy to adaptively refine only areas of high activity, using Recursive Decomposition and selective refinement in the later stages. An entropy constraint was used to modify the codebooks to allow better entropy coding of the indexes. We evaluate the performance of the proposed codec, and compare this data with the performance of the H.263-based codec. Experimental results show that the proposed codec delivered significantly better perceptual quality along with better quantitative performance.
Zhi Liu - One of the best experts on this subject based on the ideXlab platform.
-
3D shape Recursive Decomposition by Poisson equation
Pattern Recognition Letters, 2009Co-Authors: Xiang Pan, Qi Hua Chen, Zhi LiuAbstract:This paper proposes a novel algorithm that decomposes the 3D shape into meaningful parts based on Poisson equation. The whole algorithm is divided into three steps. Firstly, shape signature is defined with Poisson equation. Secondly, the binary Decomposition based on shape signature is Recursively performed to get a coarse Decomposition result. Finally, the graph-based minimum cut is used to refine the jaggy boundaries in the initial result. The proposed algorithm not only obtains a set of meaningful parts, but also is robust in the case of deformation, rotation and other transformations. Furthermore, it can process large 3D shapes in an efficient way.
Wahlström Magnus - One of the best experts on this subject based on the ideXlab platform.
-
Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
2021Co-Authors: Wahlström MagnusAbstract:We show the existence of an exact mimicking network of $k^{O(\log k)}$ edges for minimum multicuts over a set of terminals in an undirected graph, where $k$ is the total capacity of the terminals, as well as a method for computing a mimicking network of quasipolynomial size in polynomial time. As a consequence of the latter, several problems are shown to have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution and the number of cut requests. The result combines the matroid-based irrelevant edge approach used in the kernel for $s$-Multiway Cut with a Recursive Decomposition and sparsification of the graph along sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for $s$-Multiway Cut for constant value of $s$ (Kratsch and Wahlstr\"om, FOCS 2012).Comment: Updated version with simplified proof and new constructive resul
-
On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
2020Co-Authors: Wahlström MagnusAbstract:We show the existence of an exact mimicking network of $k^{O(\log k)}$ edges for minimum multicuts over a set of terminals in an undirected graph, where $k$ is the total capacity of the terminals. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than $\Theta(\log n)$, then a mimicking network of quasipolynomial size can be computed in polynomial time. As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, 0-Extension for integer-weighted metrics, and Edge Multicut parameterized by the solution and the number of cut requests. The result works via a combination of the matroid-based irrelevant edge approach used in the kernel for $s$-Multiway Cut with a Recursive Decomposition and sparsification of the graph along sparse cuts. The main technical contribution is a matroid-based marking procedure that we can show will mark all non-irrelevant edges, assuming that the graph is sufficiently densely connected. The only part of the result that is not currently constructive and polynomial-time computable is the detection of such sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for $s$-Multiway Cut for constant value of $s$ (Kratsch and Wahlstr\"om, FOCS 2012)