Spelling suggestions: "subject:"combinatorics anda aptimization"" "subject:"combinatorics anda anoptimization""
41 |
Exponentially Dense MatroidsNelson, Peter January 2011 (has links)
This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class.
Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n).
The Growth Rate Theorem, due to Geelen, Kabell, Kung, and Whittle, shows that the growth rate function is either linear, quadratic, or exponential in n. In the case of exponentially dense classes, we conjecture that, for sufficiently large n,
h_M(n) = (q^(n+k) − 1)/(q-1) − c, where q is a prime power, and k and c are non-negative integers depending only on M. We show that this holds for several interesting classes, including the class of all matroids with no U_{2,t}-minor.
We also consider more general minor-closed classes that exclude an arbitrary uniform matroid. Here the growth rate, as defined above, can be infinite. We define a more suitable notion of density, and prove a growth rate theorem for this more general notion, dividing minor-closed classes into those that are at most polynomially dense, and those that are exponentially dense.
|
42 |
On the Security of Leakage Resilient Public Key CryptographyBrydon, Dale January 2012 (has links)
Side channel attacks, where an attacker learns some physical information about the state of a device, are one of the ways in which cryptographic schemes are broken in practice. "Provably secure" schemes are subject to these attacks since the traditional models of security do not account for them. The theoretical community has recently proposed leakage resilient cryptography in an effort to account for side channel attacks in the security model. This thesis provides an in-depth look into what security guarantees public key leakage resilient schemes provide in practice.
|
43 |
Exponentially Dense MatroidsNelson, Peter January 2011 (has links)
This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class.
Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n).
The Growth Rate Theorem, due to Geelen, Kabell, Kung, and Whittle, shows that the growth rate function is either linear, quadratic, or exponential in n. In the case of exponentially dense classes, we conjecture that, for sufficiently large n,
h_M(n) = (q^(n+k) − 1)/(q-1) − c, where q is a prime power, and k and c are non-negative integers depending only on M. We show that this holds for several interesting classes, including the class of all matroids with no U_{2,t}-minor.
We also consider more general minor-closed classes that exclude an arbitrary uniform matroid. Here the growth rate, as defined above, can be infinite. We define a more suitable notion of density, and prove a growth rate theorem for this more general notion, dividing minor-closed classes into those that are at most polynomially dense, and those that are exponentially dense.
|
44 |
On the Security of Leakage Resilient Public Key CryptographyBrydon, Dale January 2012 (has links)
Side channel attacks, where an attacker learns some physical information about the state of a device, are one of the ways in which cryptographic schemes are broken in practice. "Provably secure" schemes are subject to these attacks since the traditional models of security do not account for them. The theoretical community has recently proposed leakage resilient cryptography in an effort to account for side channel attacks in the security model. This thesis provides an in-depth look into what security guarantees public key leakage resilient schemes provide in practice.
|
45 |
Path Tableaux and the Combinatorics of the Immanant FunctionTessier, Rebecca January 2013 (has links)
Immanants are a generalization of the well-studied determinant and permanent. Although the combinatorial interpretations for the determinant and permanent have been studied in excess, there remain few combinatorial interpretations for the immanant.
The main objective of this thesis is to consider the immanant, and its possible combinatorial interpretations, in terms of recursive structures on the character. This thesis presents a comprehensive view of previous interpretations of immanants. Furthermore, it discusses algebraic techniques that may be used to investigate further into the combinatorial aspects of the immanant.
We consider the Temperley-Lieb algebra and the class of immanants over the elements of this algebra. Combinatorial tools including the Temperley-Lieb algebra and Kauffman diagrams will be used in a number of interpretations. In particular, we extend some results for the permanent and determinant based on the $R$-weighted planar network construction, where $R$ is a convenient ring, by Clearman, Shelton, and Skandera. This thesis also presents some cases in which this construction cannot be extended. Finally, we present some extensions to combinatorial interpretations on certain classes of tableaux, as well as certain classes of matrices.
|
46 |
MAC Constructions: Security Bounds and Distinguishing AttacksMandal, Avradip 17 May 2007 (has links)
We provide a simple and improved security analysis of PMAC, a
Parallelizable MAC (Message Authentication Code) defined over
arbitrary messages. A similar kind of result was shown by Bellare,
Pietrzak and Rogaway at Crypto 2005, where they have provided an
improved bound for CBC (Cipher Block Chaining) MAC, which was
introduced by Bellare, Killan and Rogaway at Crypto 1994. Our
analysis idea is much more simpler to understand and is borrowed
from the work by Nandi for proving Indistinguishability at
Indocrypt 2005 and work by Bernstein. It shows that the advantage
for any distinguishing attack for n-bit PMAC based on a random
function is bounded by O(σq / 2^n), where
σ is the total number of blocks in all q queries made by
the attacker. In the original paper by Black and Rogaway at
Eurocrypt 2002 where PMAC was introduced, the bound is
O(σ^2 / 2^n).
We also compute the collision probability of CBC MAC for suitably
chosen messages. We show that the probability is Ω( lq^2 / N) where l is the number of message blocks, N is the
size of the domain and q is the total number of queries. For
random oracles the probability is O(q^2 / N). This improved
collision probability will help us to have an efficient
distinguishing attack and MAC-forgery attack. We also show that the
collision probability for PMAC is Ω(q^2 / N) (strictly greater
than the birthday bound). We have used a purely combinatorial
approach to obtain this bound. Similar analysis can be made for
other CBC MAC extensions like XCBC, TMAC and OMAC.
|
47 |
Geometric Ramifications of the Lovász Theta Function and Their Interplay with Dualityde Carli Silva, Marcel Kenji January 2013 (has links)
The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and
semidefinite optimization. They are accompanied by a rich duality theory and
deep connections to the geometric concept of orthonormal representations of graphs. In this thesis, we investigate several ramifications of the theory underlying these objects, including those arising from the illuminating viewpoint of duality. We study some optimization problems over unit-distance representations of graphs, which are intimately related to the Lovasz theta function and orthonormal representations. We also strengthen some known results about dual descriptions of theta bodies and their variants. Our main goal throughout the thesis is to lay some of the foundations for using semidefinite optimization and convex analysis in a way analogous to how polyhedral combinatorics has been using linear optimization to prove min-max theorems.
A unit-distance representation of a graph $G$ maps its nodes to some Euclidean space so that adjacent nodes are sent to pairs of points at distance one. The hypersphere number of $G$, denoted by $t(G)$, is the (square of the) minimum radius of a hypersphere that contains a unit-distance representation of $G$. Lovasz proved a min-max relation describing $t(G)$ as a function of $\vartheta(\overline{G})$, the theta number of the complement of $G$. This relation provides a dictionary between unit-distance representations in hyperspheres and orthonormal representations, which we exploit in a number of ways: we develop a weighted generalization of $t(G)$, parallel to the weighted version of $\vartheta$; we prove that $t(G)$ is equal to the (square of the) minimum radius of an Euclidean ball that contains a unit-distance representation of $G$; we abstract some properties of $\vartheta$ that yield the famous Sandwich Theorem and use them to define another weighted generalization of $t(G)$, called ellipsoidal number of $G$, where the unit-distance representation of $G$ is required to be in an ellipsoid of a given shape with minimum volume. We determine an analytic formula for the ellipsoidal number of the complete graph on $n$ nodes whenever there exists a Hadamard matrix of order $n$.
We then study several duality aspects of the description of the theta body $\operatorname{TH}(G)$. For a graph $G$, the convex corner $\operatorname{TH}(G)$ is known to be the projection of a certain convex set, denoted by $\widehat{\operatorname{TH}}(G)$, which lies in a much higher-dimensional matrix space. We prove that the vertices of $\widehat{\operatorname{TH}}(G)$ are precisely the symmetric tensors of incidence vectors of stable sets in $G$, thus broadly generalizing previous results about vertices of the elliptope due to Laurent and Poljak from 1995. Along the way, we also identify all the vertices of several variants of $\widehat{\operatorname{TH}}(G)$ and of the elliptope. Next we introduce an axiomatic framework for studying generalized theta bodies, based on the concept of diagonally scaling invariant cones, which allows us to prove in a unified way several characterizations of $\vartheta$ and the variants $\vartheta'$ and $\vartheta^+$, introduced independently by Schrijver, and by McEliece, Rodemich, and Rumsey in the late 1970's, and by Szegedy in 1994. The beautiful duality equation which states that the antiblocker of $\operatorname{TH}(G)$ is $\operatorname{TH}(\overline{G})$ is extended to this setting. The framework allows us to treat the stable set polytope and its classical polyhedral relaxations as generalized theta bodies, using the completely positive cone and its dual, and it allows us to derive a (weighted generalization of a) copositive formulation for the fractional chromatic number due to Dukanovic and Rendl in 2010 from a completely positive formulation for the stability number due to de Klerk and Pasechnik in 2002. Finally, we study a non-convex constraint for semidefinite programs (SDPs) that may be regarded as analogous to the usual integrality constraint for linear programs. When applied to certain classical SDPs, it specializes to the standard rank-one constraint. More importantly, the non-convex constraint also applies to the dual SDP, and for a certain SDP formulation of $\vartheta$, the modified dual yields precisely the clique covering number. This opens the way to study some exactness properties of SDP relaxations for combinatorial optimization problems akin to the corresponding classical notions from polyhedral combinatorics, as well as approximation algorithms based on SDP relaxations.
|
48 |
Dominating sets in Kneser graphsGorodezky, Igor January 2007 (has links)
This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures.
We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.
|
49 |
Mathematical Programming Formulations of the Planar Facility Location ProblemZvereva, Margarita January 2007 (has links)
The facility location problem is the task of optimally placing a
given number of facilities in a certain subset of the plane. In
this thesis, we present various mathematical programming
formulations of the planar facility location problem, where
potential facility locations are not specified. We first consider
mixed-integer programming formulations of the planar facility
locations problems with squared Euclidean and rectangular distance
metrics to solve this problem to provable optimality. We also
investigate a heuristic approach to solving the problem by extending
the $K$-means clustering algorithm and formulating the facility
location problem as a variant of a semidefinite programming problem,
leading to a relaxation algorithm. We present computational results
for the mixed-integer formulations, as well as compare the objective
values resulting from the relaxation algorithm and the modified
$K$-means heuristic. In addition, we briefly discuss some of the
practical issues related to the facility location model under the
continuous customer distribution.
|
50 |
On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set PolytopeAu, Yu Hin Jay January 2008 (has links)
In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then present algebraic characterizations of these valid inequalities. Tightly based on our algebraic characterizations, we give an alternate proof of a result of Lovasz and Schrijver, establishing the equivalence of N and N_0 operators on the fractional stable set polytope. Since the above mentioned conjectures involve also the recursive applications of N and N_0 operators, we also study the valid inequalities obtained by these lift-and-project operators after two applications. We show that the N-N_0 Conjecture is false, while the Rank Conjecture is true for all graphs with no more than 8 nodes.
|
Page generated in 0.579 seconds