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 f-vectors of polytopes and matroids

Thesis (Ph.D.)--University of Washington, 2016-08

Homological and Hodge-theoretic aspects of matroids and polymatroids

In the first part of this thesis, we study the action of the automorphism group of a matroid on the homology space of the co-independent complex. This representation turns out to be isomorphic, up to tensoring with the sign representation, with that on the homology space associated with the lattice of flats. In the case of the cographic matroid of the complete graph, this result has application in algebraic geometry: indeed De Cataldo, Heinloth and Migliorini use this outcome to study the Hitchin fibration. In the second part, on the other hand, we use ideas from algebraic geometry to prove a purely combinatorial result. We construct a Leray model for a discrete polymatroid with arbitrary building set and we prove a generalized Goresky-MacPherson formula. The first row of the model is the Chow ring of the polymatroid; we prove Poincaré duality, Hard-Lefschetz theorem and Hodge-Riemann relations for the Chow ring.

The combinatorics of Hilbert-Poincaré series of matroids

In this thesis we explore the combinatorial properties of several polynomials arising in matroid theory. Our main motivation comes from the problem of computing them in an efficient way and from a collection of conjectures, mainly the real-rootedness and the monotonicity of their coefficients with respect to weak maps. Most of these polynomials can be interpreted as Hilbert--Poincaré series of graded vector spaces associated to a matroid and thus some combinatorial properties can be inferred via combinatorial algebraic geometry (non-negativity, palindromicity, unimodality); one of our goals is also to provide purely combinatorial interpretations of these properties, for example by redefining these polynomials as poset invariants (via the incidence algebra of the lattice of flats); moreover, by exploiting the bases polytopes and the valuativity of these invariants with respect to matroid decompositions, we are able to produce efficient closed formulas for every paving matroid, a class that is conjectured to be predominant among all matroids. One last goal is to extend part of our results to a higher categorical level, by proving analogous results on the original graded vector spaces via abelian categorification or on equivariant versions of these polynomials.

Studies on Fuzzy Matroitls and Related Topics

The doctoral thesis focuses on the Studies on fuzzy Matroids and related topics.Since the publication of the classical paper on fuzzy sets by L. A. Zadeh in 1965.the theory of fuzzy mathematics has gained more and more recognition from many researchers in a wide range of scientific fields. Among various branches of pure and applied mathematics, convexity was one of the areas where the notion of fuzzy set was applied. Many researchers have been involved in extending the notion of abstract convexity to the broader framework of fuzzy setting. As a result, a number of concepts have been formulated and explored. However. many concepts are yet to be fuzzified. The main objective of this thesis was to extend some basic concepts and results in convexity theory to the fuzzy setting. The concept like matroids, independent structures. classical convex invariants like Helly number, Caratheodoty number, Radon number and Exchange number form an important area of study in crisp convexity theory. In this thesis, we try to generalize some of these concepts to the fuzzy setting. Finally, we have defined different types of fuzzy matroids derived from vector spaces and discussed some of their properties.