Sinziana Munteanu

Ph.D. Candidate in Computer Science, Carnegie Mellon University

B.S.E. in Computer Science, Princeton University








I am interested in theoretical computer science (graph algorithms, approximation algorithms, combinatorics).

Curriculum Vitae

Publications

  • Recurrence in Infinite Partial Words , SIAM Conference on Discrete Mathematics, 2012
    joint work with Francine Blanchet-Sadri and Bob Chen
  • Computing Bounded Path Decompositions in Logspace , submitted
    joint work with Shiva Kintali
  • Deciding Representability of Sets of Words of Equal Length in Polynomial Time , in preparation
    joint work with Francine Blanchet-Sadri
  • Deciding AllRepresentability and h-Representability of Sets of Words of Equal Length , in preparation
    joint work with Francine Blanchet-Sadri
  • Representing Languages by Infinite Partial Words , in preparation
    joint work with F. Blanchet-Sadri, B. Chen, L. Manuelli, J. Schwartz and S. Stich

    • Research Experience

  • Algorithmic Combinatorics on Partial Words , June - July 2012
    Mathematics and Computer Science REU (Research Experience for Undergraduates)
    Research Assistant, Advisor: Francine Blanchet-Sadri
        We investigated the notion of Representability in the context of finite partial words. Let A be a nonempty finite set of symbols. A full word is a sequence of elements of A and a partial word is a sequence of elements of A and diamonds, where the symbol diamond, called a hole, denotes a value that is not known. A subword of a partial word w is a block of consecutive symbols of w, in which all the diamond symbols have been replaced by elements of A. A set S of length n full words is said to be representable if there exists a partial word w such that the set of length n subwords of w is S. Define Rep to be the problem of deciding if a given set S is representable. It was previously shown that Rep is in NP. We gave the first polynomial time algorithm for deciding Rep. This result is included in our paper, "Deciding Representability of Sets of Words of Equal Length in Polynomial Time".
        We then studied the related notions of AllRepresentability and h-Representability. A set S of length n full words is said to be h-representable if there exists a partial word w with h holes such that the set of length n subwords of w is S. Define AllRep to be the problem of determining all integers h for which a given set S is h-representable. We gave the first polynomial time algorithm for deciding AllRep. For any constant h, define h-Rep to be the problem of deciding if a given set S is h-representable. A polynomial time algorithm for deciding h-Rep was previously given. We gave a more tractable algorithm and furthermore, gave the first polynomial time algorithm for deciding h-Rep, when h is an input parameter given in unary representation. These results are included in our paper, "Deciding AllRepresentability and h-Representability of Sets of Words of Equal Length".

  • Efficient Algorithms for Treewidth, Pathwidth and Related Parameters , September 2011 - May 2012
    Senior Thesis, Advisor: Shiva Kintali
        We investigated the treewidth and pathwidth of a graph, which are measures of the extent to which the graph resembles a tree and a path, respectively. It was shown that determining the treewidth or pathwidth of a graph and of finding the associated tree or path decomposition is NP-complete. However, if the graph has bounded treewidth or pathwidth, there exist linear time algorithms for computing them along with their associated decompositions. Moreover, there exists a logspace algorithm for computing the treewidth and tree decomposition of a bounded treewidth graph. We developed a logspace algorithm for computing the path decomposition of bounded pathwidth graphs. Prior to our work, the best known upper bound to compute such decompositions was linear time. Our result can be found in the paper "Computing Bounded Path Decompositions in Logspace".

  • Algorithmic Combinatorics on Partial Words , June - July 2011
    Mathematics and Computer Science REU (Research Experience for Undergraduates)
    Student Participant, Advisor: Francine Blanchet-Sadri
        We investigated recurrence in infinite partial words, a notion related to symbolic dynamics. For full words, it is known that the recurrence quotient is 1, if the word is periodic and is at least 3, otherwise. Nothing else is known about the topological structure of the spectrum of possible values achievable by the recurrence quotients of full words. We gave a complete characterization of the spectrum of possible values achievable by the recurrence quotients of partial words. More specifically, we showed that if a word is ultimately factor periodic, then the recurrence quotient is 1 and otherwise, the spectrum is [2, infinity]. These and other results related to recurrence, periodicity and subword complexity are included in our paper, "Recurrence in Infinite Partial Words".
        We then investigated sets of subwords. We classified formal languages that are the sets of subwords of recurrent/ nonrecurrent full/ partial infinite words and investigated properties of words with the same set of subwords. These and other results are presented in the paper "Representing Languages by Infinite Partial Words".