On codes, matroids, and secure multiparty computation from linear secret-sharing schemes

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries.Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp–Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

On fast-decodable space-time block codes

We focus on full-rate, fast-decodable space–time block codes (STBCs) for 2 x 2 and 4 x 2 multiple-input multiple-output (MIMO) transmission. We first derive conditions and design criteria for reduced-complexity maximum-likelihood (ML) decodable 2 x 2 STBCs, and we apply them to two families of codes that were recently discovered. Next, we derive a novel reduced-complexity 4 x 2 STBC, and show that it outperforms all previously known codes with certain constellations.

On high-rate full-diversity 2x2 space-time codes with low-complexity optimum detection

The 2×2 MIMO profiles included in Mobile WiMAX specifications are Alamouti’s space-time code (STC) fortransmit diversity and spatial multiplexing (SM). The former hasfull diversity and the latter has full rate, but neither of them hasboth of these desired features. An alternative 2×2 STC, which is both full rate and full diversity, is the Golden code. It is the best known 2×2 STC, but it has a high decoding complexity. Recently, the attention was turned to the decoder complexity, this issue wasincluded in the STC design criteria, and different STCs wereproposed. In this paper, we first present a full-rate full-diversity2×2 STC design leading to substantially lower complexity ofthe optimum detector compared to the Golden code with only a slight performance loss. We provide the general optimized form of this STC and show that this scheme achieves the diversitymultiplexing frontier for square QAM signal constellations. Then, we present a variant of the proposed STC, which provides a further decrease in the detection complexity with a rate reduction of 25% and show that this provides an interesting trade-off between the Alamouti scheme and SM.

Low-density parity-check codes for nonergodic block-fading channels

We design powerful low-density parity-check (LDPC) codes with iterative decoding for the block-fading channel. We first study the case of maximum-likelihood decoding, and show that the design criterion is rather straightforward. Since optimal constructions for maximum-likelihood decoding do not performwell under iterative decoding, we introduce a new family of full-diversity LDPC codes that exhibit near-outage-limit performance under iterative decoding for all block-lengths. This family competes favorably with multiplexed parallel turbo codes for nonergodic channels.

Generalized low-density codes with BCH constituents for full-diversity near-outage performance

A new graph-based construction of generalized low density codes (GLD-Tanner) with binary BCH constituents is described. The proposed family of GLD codes is optimal on block erasure channels and quasi-optimal on block fading channels. Optimality is considered in the outage probability sense. Aclassical GLD code for ergodic channels (e.g., the AWGN channel,the i.i.d. Rayleigh fading channel, and the i.i.d. binary erasure channel) is built by connecting bitnodes and subcode nodes via a unique random edge permutation. In the proposed construction of full-diversity GLD codes (referred to as root GLD), bitnodes are divided into 4 classes, subcodes are divided into 2 classes, and finally both sides of the Tanner graph are linked via 4 random edge permutations. The study focuses on non-ergodic channels with two states and can be easily extended to channels with 3 states or more.

Full diversity product codes for block erasure and block fading channels

We show how to build full-diversity product codes under both iterative encoding and decoding over non-ergodic channels, in presence of block erasure and block fading. The concept of a rootcheck or a root subcode is introduced by generalizing the same principle recently invented for low-density parity-check codes. We also describe some channel related graphical properties of the new family of product codes, a familyreferred to as root product codes.

A comparison of full-rate full-diversity 2x2 space-time codes for WiMAX systems

Multiple-input multiple-output (MIMO) techniques have become an essential part of broadband wireless communications systems. For example, the recently developed IEEE 802.16e specifications for broadband wireless access include three MIMOprofiles employing 2×2 space-time codes (STCs), and two of these MIMO schemes are mandatory on the downlink of Mobile WiMAX systems. One of these has full rate, and the other has full diversity, but neither of them has both of the desired features. The third profile, namely, Matrix C, which is not mandatory, is both a full rate and a full diversity code, but it has a high decoder complexity. Recently, the attention was turned to the decodercomplexity issue and including this in the design criteria, several full-rate STCs were proposed as alternatives to Matrix C. In this paper, we review these different alternatives and compare them to Matrix C in terms of performances and the correspondingreceiver complexities.

Outage thresholds of LDPC codes over nonergodic block-fading channels

This paper derives approximations allowing the estimation of outage probability for standard irregular LDPC codes and full-diversity Root-LDPC codes used over nonergodic block-fading channels. Two separate approaches are discussed: a numerical approximation, obtained by curve fitting, for both code ensembles, and an analytical approximation for Root-LDPC codes, obtained under the assumption that the slope of the iterative threshold curve of a given code ensemble matches the slope of the outage capacity curve in the high-SNR regime.

On iterative performance of LDPC and Root-LDPC codes over block-fading channels

This paper presents our investigation on iterativedecoding performances of some sparse-graph codes on block-fading Rayleigh channels. The considered code ensembles are standard LDPC codes and Root-LDPC codes, first proposed in and shown to be able to attain the full transmission diversity. We study the iterative threshold performance of those codes as a function of fading gains of the transmission channel and propose a numerical approximation of the iterative threshold versus fading gains, both both LDPC and Root-LDPC codes.Also, we show analytically that, in the case of 2 fading blocks,the iterative threshold root of Root-LDPC codes is proportional to (α1 α2)1, where α1 and α2 are corresponding fading gains.From this result, the full diversity property of Root-LDPC codes immediately follows.

Transhepatic ipsilateral right portal vein embolization extended to segment IV: improving hypertrophy and resection outcomes with spherical particles and coils.

PURPOSE: To analyze outcomes after right portal vein embolization extended to segment IV (right PVE + IV) before extended right hepatectomy, including liver hypertrophy, resection rates, and complications after embolization and resection, and to assess differences in outcomes with two different particulate embolic agents. MATERIALS AND METHODS: Between 1998 and 2004, transhepatic ipsilateral right PVE + IV with particles and coils was performed in 44 patients with malignant hepatobiliary disease, including metastases (n = 24), biliary cancer (n = 14), and hepatocellular carcinoma (n = 6). Right PVE + IV was considered if the future liver remnant (FLR; segments II/III with or without I) was less than 25% of the total estimated liver volume (TELV). Tris-acryl microspheres (100-700 microm; n = 21) or polyvinyl alcohol (PVA) particles (355-1,000 microm; n = 23) were administered in a stepwise fashion. Smaller particles were used to occlude distal branches, followed by larger particles to occlude proximal branches until near-complete stasis. Coils were then placed in secondary portal branches. Computed tomographic volumetry was performed before and 3-4 weeks after right PVE + IV to assess FLR hypertrophy. Liver volumes and postembolization and postoperative outcomes were measured. RESULTS: After right PVE + IV with PVA particles, FLR volume increased 45.5% +/- 40.9% and FLR/TELV ratio increased 6.9% +/- 5.6%. After right PVE + IV with tris-acryl microspheres, FLR volume increased 69.0% +/- 30.7% and FLR/TELV ratio increased 9.7% +/- 3.3%. Differences in FLR volume (P = .0011), FLR/TELV ratio (P = .027), and resection rates (P = .02) were statistically significant. Seventy-one percent of patients underwent extended right hepatectomy (86% after receiving tris-acryl microspheres, 57% after receiving PVA). Thirteen patients (29%) did not undergo resection (extrahepatic spread [n = 9], inadequate hypertrophy [n = 3], other reasons [n = 1]). No patient developed postembolization syndrome or progressive liver insufficiency after embolization or resection. One death after resection occurred as a result of sepsis and hemorrhage. Median hospital stays were 1 day after right PVE + IV and 7 days after resection. CONCLUSION: Transhepatic ipsilateral right PVE + IV with use of particles and coils is a safe, effective method for inducing contralateral hypertrophy before extended right hepatectomy. Embolization with small spherical particles provides improved hypertrophy and resection rates compared with larger, nonspherical particles.

Spatial distribution of a spherical gall (Hymenoptera, Eulophidae) on Caryocar brasiliense (Caryocaraceae)

We obtained the first data on spatial distribution of a spherical galling insect (Hymenoptera, Eulophidae) at the Caryocar brasiliense Camb. (Caryocaraceae) tree level. This work was developed in two pastures in Montes Claros, Minas Gerais State, Brazil. The areas studied were: pasture 1 (in activity) and pasture 2 (abandoned pasture = savanna in recovery). We evaluated the distribution of spherical galls in: foliage orientation (slope), among leaves (border and interior of the tree crown), among leaflets (right, central, left), distal, median, and proximal as well as border, central area, and adjacent to the mid leaf vein of the leaflet, and difference between areas in 10 infested trees per area. The smaller number of spherical gall/leaflet was observed in pasture 1 than in pasture 2. More spherical galls were found on the northern in pasture 1, but in the pasture 2, the lower spherical galls were observed on the northeast than other slopes. The average number of spherical galls did not differ statistically among the three leaflets of C. brasiliense in pasture 2. However, in pasture 1, we observed highest number of spherical galls in the central leaflet. More spherical galls were found in the border than interior of the tree crown. The average number of spherical galls did not differ statistically among the longitudinal region on leaflet of C. brasiliense. The spherical gall insect preferred to colonize the leaf margin than the central portion or near mid vein on transversal regions on a leaflet.

Density modes in spherical 4He shells

We compute the density-fluctuation spectrum of spherical 4HeN shells adsorbed on the outer surface of Cn fullerenes. The excitation spectrum is obtained within the random-phase approximation, with particle-hole elementary excitations and effective interaction extracted from a density-functional description of the shell structure. The presence of one or two solid helium layers adjacent to the adsorbing fullerene is phenomenologically accounted for. We illustrate our results for a selection of numbers of adsorbed atoms on C20, C60, and C120. The hydrodynamical model that has proven successful to describe helium excitations in the bulk and in restricted geometries permits to perform a rather exhaustive analysis of various fluid spherical systems, namely, spheres, cavities, free bubbles, and bound shells of variable size.

Effective mass and dielectric constant mismatch effects in spherical multishell quantum dots

The role of effective mass and dielectric mismatches on chemical potentials and addition energies of many-electron multishell quantum dots (QDs) is explored within the framework of a recent extension of the spin density functional theory. It is shown that although the gross electronic density is located in the wells of these multishell QDs, taking position-dependent effective mass and dielectric constant into account can lead to the appearance of relevant differences in chemical potential and addition energies as compared to standard calculations in which the effective mass and the dielectric constant of the well is assumed for the whole multishell structure.