Alumni Dissertations

 

Alumni Dissertations

Filter Dissertations By:

 
 
  • Conflict-free coloring

    Author:
    Panagiotis Cheilaris
    Year of Dissertation:
    2009
    Program:
    Computer Science
    Advisor:
    Stathis Zachos
    Abstract:

    Graph and hypergraph colorings constitute an important subject in combinatorics and algorithm theory. In this work, we study conflict-free coloring for hypergraphs. Conflict-free coloring is one possible generalization of traditional graph coloring. Conflict-free coloring hypergraphs induced by geometric shapes, like intervals on the line, or disks on the plane, has applications in frequency assignment in cellular networks. Colors model frequencies and since the frequency spectrum is limited and expensive, the goal of an algorithm is to minimize the number of assigned frequencies, that is, reuse frequencies as much as possible. We concentrate on an online variation of the problem, especially in the case where the hypergraph is induced by intervals. For deterministic algorithms, we introduce a hierarchy of models ranging from static to online and we compute lower and upper bounds on the numbers of colors used. In the randomized oblivious adversary model, we introduce a framework for conflict-free coloring a specific class of hypergraphs with a logarithmic number of colors. This specific class includes many hypergraphs arising in geometry and gives online randomized algorithm that use fewer colors and fewer random bits than other algorithms in the literature. Based on the same framework, we initiate the study of online deterministic algorithms that recolor few points. For the problem of conflict-free coloring points with respect to a given set of intervals, we describe an efficient algorithm that computes a coloring with at most twice the number of colors of an optimal coloring. We also show that there is a family of inputs that force our algorithm to use two times the number of colors of an optimal solution. Then, we study conflict-free coloring problems in graphs. We compare conflict-free coloring with respect to paths of graphs to a closely related problem, called vertex ranking, or ordered coloring. For conflict-free coloring with respect to neighborhoods of vertices of graphs, we prove that number of colors in the order of the square root of the number of vertices is sufficient and sometimes necessary. Finally, we initiate the study of Ramsey-type problems for conflict-free colorings and compute a van der Waerden-like number.

  • Efficient controls for finitely convergent sequential algorithms and their applications

    Author:
    Wei Chen
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Gabor Herman
    Abstract:

    Finding a feasible point that satisfies a set of constraints or a point that optimizes a function subject to a set of constraints is a common task in scientific computing: examples are the linear/convex feasibility/optimization problems. Projection methods have been used widely in solving many such problems of large size much more efficiently than other alternatives. Finitely convergent sequential algorithms are projection methods that sequentially iterate on individual constraints, one at a time, but overall find a feasible point in a finite number of iterations. ART3 is an example using cyclic control in the sense that it repeatedly cycles through the given constraints. The skipping unnecessary checks on constraints that are likely to be satisfied, lead to the new algorithm ART3+, a variant of ART3 whose control is no longer cyclic, but which is still finitely convergent. Experiments in fitting pixel images by blob images show that ART3+ is statistically significantly faster than ART3. Furthermore, a general methodology is proposed for automatic transformation of any finitely convergent sequential algorithm in such a way that (1) finite convergence is retained and (2) the speed of finite convergence is improved. The first property is proved by mathematical theorems, the second is illustrated by applying the algorithms to practical problems. This transformation is applicable, for example, to the finitely convergent modified cyclic subgradient projection algorithm for solving convex feasibility problems. One application is to intensity modulated radiation therapy (IMRT), whose goal is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. The superior performance of the ART3+ for IMRT is demonstrated. An optimization algorithm based on ART3+ is proposed to handle linear constraints with either linear objectives or certain convex objectives. It is on average more than two orders of magnitude faster than the state of art industry-standard commercial algorithms (MOSEK's interior point optimizer and primal/dual simplex optimizer) and has almost no memory overhead. This allows for fast creation of multi-criteria treatment plan databases that span the global planning options available to the treatment planner.

  • COLLABORATIVE RANKING AND COLLABORATIVE CLUSTERING

    Author:
    Zheng Chen
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Heng Ji
    Abstract:

    Ranking and clustering are two important problems in machine learning and have wide applications in Natural Language Processing (NLP). A ranking problem is typically formulated as ranking a collection of candidate "objects" with respect to a "query" while a clustering problem is formulated as organizing a set of instances into groups such that members in each group share some similarity while members across groups are dissimilar. In this thesis, we introduce collaborative schemes into ranking and clustering problems, and name them as "collaborative ranking" and "collaborative clustering" respectively. Contrast to the tradition non-collaborative schemes, collaborative ranking leverages strengths from multiple query collaborators and ranker collaborators while collaborative clustering leverages strengths from multiple instance collaborators and clusterer collaborators. We select several typical NLP problems as our case studies including entity linking, document clustering and name entity clustering.

  • Efficient controls for finitely convergent sequential algorithms and their applications

    Author:
    Wei Chen
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Gabor Herman
    Abstract:

    Finding a feasible point that satisfies a set of constraints or a point that optimizes a function subject to a set of constraints is a common task in scientific computing: examples are the linear/convex feasibility/optimization problems. Projection methods have been used widely in solving many such problems of large size much more efficiently than other alternatives. Finitely convergent sequential algorithms are projection methods that sequentially iterate on individual constraints, one at a time, but overall find a feasible point in a finite number of iterations. ART3 is an example using cyclic control in the sense that it repeatedly cycles through the given constraints. The skipping unnecessary checks on constraints that are likely to be satisfied, lead to the new algorithm ART3+, a variant of ART3 whose control is no longer cyclic, but which is still finitely convergent. Experiments in fitting pixel images by blob images show that ART3+ is statistically significantly faster than ART3. Furthermore, a general methodology is proposed for automatic transformation of any finitely convergent sequential algorithm in such a way that (1) finite convergence is retained and (2) the speed of finite convergence is improved. The first property is proved by mathematical theorems, the second is illustrated by applying the algorithms to practical problems. This transformation is applicable, for example, to the finitely convergent modified cyclic subgradient projection algorithm for solving convex feasibility problems. One application is to intensity modulated radiation therapy (IMRT), whose goal is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. The superior performance of the ART3+ for IMRT is demonstrated. An optimization algorithm based on ART3+ is proposed to handle linear constraints with either linear objectives or certain convex objectives. It is on average more than two orders of magnitude faster than the state of art industry-standard commercial algorithms (MOSEK's interior point optimizer and primal/dual simplex optimizer) and has almost no memory overhead. This allows for fast creation of multi-criteria treatment plan databases that span the global planning options available to the treatment planner.

  • The Bilinear Brain, Bilinear Methods For EEG Analysis And Brain Computer Interfaces.

    Author:
    Christoforos Christoforou
    Year of Dissertation:
    2009
    Program:
    Computer Science
    Advisor:
    Robert Haralick
    Abstract:

    Analysis of electro-encephalographic (EEG) signals has been proven an extremely useful research tool for studying the neural correlates of behavior. Single-trial analysis of these signals is essential for the development of non-invasive Brain Computer Interfaces. Analysis of these signals is often expressed as a single-trial classi¯cation problem. The goal is to infer the underling cognitive state of an individual using purely EEG signals. The high dimensional space of EEG observations and the low signal-to-noise ratio (SNR) -often -20db or less - as well as the inter-subject variability and limited observations available for training, make the single-trial classi¯cation of EEG an extremely challenging computational task. To address these challenges we introduce concepts from Multi-linear Algebra and incorporate EEG domain knowledge. More precisely, we formulate the problem in a matrix space and introduce a bilinear combination of a matrix to reduce the space dimensions. Thus the title of this dissertation: "The Bilinear Brain". We also address the issue of inter-subject variability by de¯ning a model that is partially subject-invariant. We develop two classi¯cation algorithms based on the Bilinear model. We term the ¯rst algorithm Second Order Bilinear Discriminant Analysis (SOBDA). It combines ¯rst order and second order statistics of the observation space. The second algorithm we term Bilinear Feature Based Discriminant (BFBD) and addresses the issue of inter-subject variability. We evaluate our methods on both simulated and real human EEG data-sets and show that our method outperforms state-of-the-art methods on di®erent experimental paradigms.

  • Hash Functions, Latin Squares and Secret Sharing Schemes

    Author:
    Chi Chum
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Xiaowen Zhang
    Abstract:

    A secret sharing scheme creates an effective method to safeguard a secret by dividing it among several participants. Since the original idea introduced by Shamir and Blakley in 1979, a variety of threshold secret sharing schemes and other types have been suggested by researchers. The first part of this thesis shows how to apply hash functions in secret sharing scheme designs. By using hash functions and the herding hashes technique, we first set up a (t + 1, n) threshold scheme which is perfect and ideal, and then extend it to schemes for any general access structure. The schemes can be further set up as verifiable if necessary. The secret can be quickly recovered due to the fast calculation of the hash function. In particular, secret sharing schemes based on Latin squares will be discussed. The practical hash functions used today, such as SHA-1 and SHA-2 families, are iterative hash functions. Although there are many suggestions to improve the security of an iterative hash function, the general idea of processing the message block by block still enables many attacks, which make use of the intermediate hash values, possible. The second part of this thesis proposes a new hash function construction scheme that applies the randomize-then-combine technique, which was used in the incremental hash functions, to the iterative hash construction to prevent those attacks.

  • Algorithms for Superiorization and their Applications to Image Reconstruction

    Author:
    Ran Davidi
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Gabor Herman
    Abstract:

    Computational tractability with limited computing resources is a major barrier for the ever increasing problem sizes of constrained optimization models that seek a minimum of an objective function satisfying a set of constraints. On the other hand, there exist efficient and computationally much less demanding iterative methods for finding a feasible solution that only fulfills the constraints. These methods can handle problem sizes beyond which existing optimization algorithms cannot function. To bridge this gap we present a new concept called superiorization, envisioned methodologically as lying between optimization and feasibility seeking. It enables us to use efficient iterative methods to steer the iterates toward a point that is feasible and superior, but not necessarily optimal, with respect to the given objective/merit function. Using efficient iterative methods to do `superiorization' instead of `full constrained optimization' or only `feasibility' is a new tool for handling mathematical models that include constraints and a merit function. The target improvement of the superiorization methodology is to affect the computational treatment of the mathematical models so that we can reach solutions that are desirable from the point of view of the application at hand at a relatively small computational cost. The key to superiorization is our discovery that two principal prototypical algorithmic schemes, string-averaging projections and block-iterative projections, which include many projection methods, are bounded perturbation resilient. While stability of algorithms under perturbations is usually made to cope with all kinds of imperfections in the data, here we have taken a proactive approach designed to extract specific benefits from the kind of stability that we term perturbation-resilience. Superiorization uses perturbations proactively to reach feasible points that are superior, according to some criterion, to the ones to which we would get without employing perturbations. In this work, we set forth the fundamental principle of the superiorization methodology, give some mathematical formulations, theorems and results, and show potential benefits in the field of image reconstruction from projections.

  • Epistemic paradox and explicit modal logic

    Author:
    Walter Dean
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Sergei Artemov
    Abstract:

    The dissertation presents a unified treatment of what I refer to as the epistemic paradoxes (i.e. the Knower Paradox of Montague and Kaplan and Fitch's Paradox of Knowability) in the context of a quantified extension of Artemov's Logic of Proofs [LP]. The system adopted is a modified form of Fitting's Quantified Logic of Proofs [QLP] and contains not only so-called explicit modalities (i.e. statements of the form t:F with intended interpretation of "t denotes a proof of F") but also first-order quantifiers intended to range over proofs or informal justifications. This allows for a formalization of a justification-based notion of knowledge via statements of the form (exists x) x:F. The first chapter seeks to motivate the use of explicit modalities for reasoning about knowledge and informal provability relative to the tradition of epsitemic logic. The second chapter contains a consolidated treatment of the syntax and arithmetic and semantics of LP and QLP. A relational semantics for QLP is developed and several new results are presented. The third chapter focuses on the reconstruction of the Knower Paradox in QLP. The central observation is that by analyzing the K(x) predicate employed by Montague and Kaplan in terms of proof quantification by replacing K("F") with (exists x) x:F, we realize that an additional logic principle is required for the derivation of the Knower. This principle -- which is similar to a form of Universal Generalization for proofs anticipated by G\"odel [1938a] -- is examined both proof theoretically and through the use of an arithmetic semantics for QLP. The fourth chapter focuses on the reconstruction of the Knowability Paradox in QLP. The central observation is the so-called Knowability Principle on which the paradox is based -- i.e. the claim that if F is true, then it is possible to know F -- is most appropriately formulated via the use of proof quantifiers as (exists x) x:F as opposed to the use of propositional possibility and knowledge operators.

  • Epistemic paradox and explicit modal logic

    Author:
    Walter Dean
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Sergei Artemov
    Abstract:

    The dissertation presents a unified treatment of what I refer to as the epistemic paradoxes (i.e. the Knower Paradox of Montague and Kaplan and Fitch's Paradox of Knowability) in the context of a quantified extension of Artemov's Logic of Proofs [LP]. The system adopted is a modified form of Fitting's Quantified Logic of Proofs [QLP] and contains not only so-called explicit modalities (i.e. statements of the form t:F with intended interpretation of "t denotes a proof of F") but also first-order quantifiers intended to range over proofs or informal justifications. This allows for a formalization of a justification-based notion of knowledge via statements of the form (exists x) x:F. The first chapter seeks to motivate the use of explicit modalities for reasoning about knowledge and informal provability relative to the tradition of epsitemic logic. The second chapter contains a consolidated treatment of the syntax and arithmetic and semantics of LP and QLP. A relational semantics for QLP is developed and several new results are presented. The third chapter focuses on the reconstruction of the Knower Paradox in QLP. The central observation is that by analyzing the K(x) predicate employed by Montague and Kaplan in terms of proof quantification by replacing K("F") with (exists x) x:F, we realize that an additional logic principle is required for the derivation of the Knower. This principle -- which is similar to a form of Universal Generalization for proofs anticipated by G\"odel [1938a] -- is examined both proof theoretically and through the use of an arithmetic semantics for QLP. The fourth chapter focuses on the reconstruction of the Knowability Paradox in QLP. The central observation is the so-called Knowability Principle on which the paradox is based -- i.e. the claim that if F is true, then it is possible to know F -- is most appropriately formulated via the use of proof quantifiers as (exists x) x:F as opposed to the use of propositional possibility and knowledge operators.

  • A SCALABLE AGENT-BASED SYSTEM FOR NETWORK FLOW RECONSTRUCTION WITH APPLICATIONS TO DETERMINING THE STRUCTURE AND DYNAMICS OF DISTRIBUTED DENIAL OF SERVICE ATTACKS

    Author:
    Omer DEMIR
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Bilal Khan
    Abstract:

    In this thesis we describe a novel agent-based architecture for flow reconstruction, and demonstrate how it can be applied to obtain a description of the structure and dynamics of distributed denial of service (DDoS) attacks. We show that the system can operate in a decentralized manner, effectively providing a description of the structure and dynamics of traffic flows even with very modest levels of agent deployment. By providing structural information, the system facilitates the execution of DDoS mitigation strategies close to the actual sources of attack traffic. Through simulations, we validate the efficacy with which the system is able to discover traffic source locations and the structure of traffic flows. Through packet-level simulations, we show favorable convergence properties for the system. We describe several schemes for selecting the precise links on which agents should be placed, and show that these placement schemes yield marked improvements in system performance and scalability. Finally, we introduce a prototype attacker localization scheme called SLANT, which combines information from a sequence of attacks on different victims, in order to further isolate traffic source locations. SLANT shows promise for using multiple attack data to determine the exact locations of the attackers, even at moderate agent deployment levels.