 |
|
|
|
Please revisit this page frequently, additional projects will be posted through January.
Mentors: Ming Xie, mxie at stat.rutgers.edu, Department of Statistics and E.A. Elsayed, elsayed at rci.rutgers.edu, Department of Electrical Engineering
Project Title: Optimum Strategies of Container Inspection at Port-of-Entry
Containers arriving at ports may contain undesirable contents such as drugs, radioactive material or chemical and biochemical agents.
Inspection of a fraction of these containers (randomly or based on some risk factor) might lead to an improved security system. Clearly, there is a probability that a container with undesirable contents might enter into the system without detection or a "clean" container might be subjected to a thorough inspection.... The objective of this project is determine the optimum inspection strategy that minimizes the occurrence of the above probabilities. Approaches such as the development of adaptive threshold levels of the inspection sensors based on the assigned risk factor might prove to an efficient inspection strategy.
The research investigates new and efficient inspection strategies.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Vinod Ganapathy, vinodg@cs.rutgers.edu , Computer Science Department
Project Title: Mitigating Malware on Emerging Networks
Recent years have seen the emergence of several unconventional networks of computers including networks of cellular phones, social networks and vehicular networks. The emergence of these networks also brings with it the risk of malware, such as viruses, worms, rootkits and botnets. This project will focus on understanding the nature of the threat of malware on these networks and will seek to devise techniques to mitigate this threat.
This topic is fairly broad and the exact project topic will be decided based upon student interest. Depending on the student's interest, the project could either be a "black hat" project or a "white hat" project. For example, one black hat project could involve better understanding the threat of malware on cellular phones by devising novel malware that use features unique to cellular phones. Similarly, another project could devise techniques to mitigate malware on cellular phones in a manner that does not exhaust network bandwidth or increase the phone's power consumption.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Vinod Ganapathy, vinodg@cs.rutgers.edu , Computer Science Department
Project Title: Securing Software with Transactional Memory Introspection
With multi-core machines becoming ubiquitous, it is now well accepted that programs of the future must be parallel in order to exploit the these cores for performance. Transactional memory is a new programming paradigm that promises to ease the otherwise difficult task of writing parallel programs. My group has developed a security architecture, called transactional memory introspection, that uses the mechanisms implemented by transactional memory systems to improve software security.
In this project, you will extend the functionality of transactional memory introspection in several ways. For example, one project could use transactional memory mechanisms to implement an information flow tracking system. Information flow tracking traces the flow of data as a program executes, and has several applications, such as detecting and preventing privacy breaches. Similarly, another project could devise a forensics system based upon transactional memory, that would enable better analysis of memory accesses made by malware.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Danfeng Yao, danfeng@cs.rutgers.edu , Computer Science Department
Project Title: Detecting HTTP Based Botnet Command and Control Traffic
This project is to investigate the similarities and differences in the HTTP periodicity between botnet command & control and legitimate web server traffic. Studies found that HTTP based botnet command and control channels have distinct periodicity. However, using this single parameter for botnet detection may produce a large false positive rate (i.e., falsely classifying legitimate traffic as bot traffic). Legitimate web servers also periodically refresh their web pages automatically. This project is to study how to use and leverage human behavior patterns in differentiating the malicious connections from legitimate ones, and to investigate how difficult it is for botnets to evade our detection mechanism.
This project will require a student with CS or ECE background. Preliminary knowledge in security is *not* required.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: William Pottenger, billp at dimacs.rutgers.edu , DIMACS and Computer Science
Project Title: Higher Order Learning
Traditional machine learning approaches make the assumption that instances are independent and identically distributed (IID). We term models constructed under the IID assumption first-order because in general they only leverage relationships between attributes within instances (e.g., co-occurrence relationships). Thus classification of a single instance (of previously unseen data) is possible because no additional context is needed to infer class membership. Such a context-free approach, however, does not exploit valuable information about relationships between instances in the dataset.
In our research we are developing a novel framework for learning that, unlike approaches that assume instances are IID, leverages implicit co-occurrence relationships between attributes in different instances. We term these implicit co-occurrence relationships higher-order paths. Attributes ( e.g., words in documents in text collections) are richly connected by such higher-order paths, and the model builts by our higher order learners exploit this rich connectivity pattern. In our work to-date we have developed both supervised and unsupervised learning approaches including Higher Order Naive Bayes, Higher Order SVM, Higher Order Classification Based ARM and Distributed Higher Order ARM. We are also have a framework under development that leverages human-computer interaction entitled Distributed Interactive Higher Order Privacy Enhancing Knowledge Discovery (DI HOPE KD).
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: James Abello, abello@dimacs.rutgers.edu , DIMACS
Project Title: DIMACS Graph MiningIn this project we will build a variety of multi-graphs that can be extracted from this data set. We will then use our current set of graph analysis tools to parse, navigate, visualize and synthesize the findings. One central challenge is to devise methods that are privacy preserving.
Requirements: Some Knowledge of SQL, fundamental graph algorithms and C/C++ programming is a plus. However, there are several analysis tasks that can be performed using our plug in graph visualization system and that require only minimal amount of programming.
Reference:
[AvHK06] J. Abello, F. van Ham, and N. Krishnan, "Ask-GraphView-:
A Large Scale Graph Visualization System", IEEE Transactions in
Visualization and Computer Graphics, 12(5): 669-676 (2006).
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: James Abello, abello@dimacs.rutgers.edu , DIMACS
Project Title: Name That ClusterGiven a user query, search engines generally return a very sizeable collection of possible answers. Clustering has been proposed as a tool to partition the possible answer set into more manageable subsets of related results. There is no current agreement on the preferred mode of presentation of these clusters. Currently, most search engines display the set of results on almost a pure textual form. However, relatively recently we have witnessed some timid attempts to use some graphical representations. This study is a first step to elucidate when and why text appears to outperform graphics for certain fundamental clustering related tasks. To this end we designed three interfaces to display flat clusters of user queries. The interfaces are enhanced with mechanisms by which users provide feedback about the relevance of a cluster for a pre-specified input query. Subsequently, users are asked to provide a name for a given cluster that best describes the cluster contents. In this project, we will analyze the results obtained from a web user study that is planned to run from Feb to May 2008.
Requirements:Basic Statistics, reading clustering related papers and preparing summary of findings.
Reference:
[ASGT07] J. Abello, J, Schulz, H, Gaudin, B, and Tominski, C (2007).
Name That Cluster - Text vs. Graphics, IEEE InfoVis Conference, Sacramento, November 2007.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: James Abello, abello@dimacs.rutgers.edu , DIMACS
Project Title: Point Configurations, The Weak Bruhat Order of Sn and The Majority RuleMaximal Chains in the Weak Bruhat Order of the Symmetric Group give rise to a special class of graphs called Persistent Graphs. These graphs are directly related to visibility graphs associated with point configurations on the plane and they encode transitivity of the majority rule. This project will study the combinatorial properties of this new class of graphs and their geometric implications. Requirements: A good discrete math course, basics of graph theory , linear algebra and a strong will to face interesting combinatorial geometry questions.
Reference:
[AEK95] J. Abello, O. Egecioglu and K. Kumar, "Visibility Graphs of
Staircase Polygons and the Weak Bruhat Order", Discrete and
Computational Geometry, Volume 14, 1995.
* You must be a enrolled at a U.S. university to be eligible for this project.
Project Title: Protein-induced DNA Looping
Many genetic processes are mediated by proteins that bind at separate, often widely spaced, sites on the double helix, tethering the intervening DNA into a loop [1, 2]. Examples of these processes include gene expression and its control, DNA replication, genetic rearrangements, multi-site cutting by restriction enzymes, and DNA packaging. A DNA loop stabilized by such long-range protein-protein contacts constitutes a discrete topological unit. As long as the ends of the DNA stay in place and the duplex remains unbroken, the linking number, Lk, or number of times the two strands of the double helix wrap around one another, is conserved. This constraint in Lk underlies the well known supercoiling of DNA: the stress induced by positioning the ends of the polymer in locations other than the natural (relaxed) state perturbs the overall coiling of the chain axis and/or the twisting of successive base-pairs in the intervening parts of the chain [3]. As a first step in understanding the effects of specific proteins and drugs on DNA looping, we propose to study the imposed bending and twisting of neighboring base pairs [4] in known complexes of proteins and drugs with double helical DNA stored in the Nucleic Acid Database [5]. By subjecting a DNA segment of the same chain length as that found in a given complex to the observed orientation, displacement, and superhelical stress and setting the elastic moduli to sufficiently high values, we can use existing programs, e.g., [6], to simulate the presence of a rigidly bound molecule at arbitrary positions on circular DNA molecules or to model specific systems in which DNA looping plays an important role, e.g., the lac repressor-operator assembly in EscherichiaA0coli [7]. One student could devote a summer project to the collection of geometric information. Other students could apply this information to simulations of DNA loops and folds in subsequent years. Prerequisites: Students should have an interest (but not necessarily formal training) in molecular biology, familiarity with linear algebra in order to understand the parameters used to describe DNA structure, and knowledge of basic chemistry and physics to understand the nature of the DNA molecules and the elastic treatment of the double helix.
[1] Halford, S. E., Gowers, D. M., and Sessions, R. B., ``Two are Better than One,'' Nature Struct. Biol., 7, (2000), 705-707.
[2] Schleif, R., ``DNA Looping,'' Annu. Rev. Biochem., 61, (1992), 199-223.
[3] Bauer, W. R. ``Structure and Reactions of Closed Duplex DNA,'' Annu. Rev. Biophys. Bioeng., 7, (1978), 287-313.
[4] Olson, W. K., Gorin, A. A., Lu, X.-J., Hock, L. M., and Zhurkin, V. B., ``DNA Sequence-dependent Deformability Deduced from Protein-DNA Crystal Complexes,'' Proc. Natl. Acad. Sci. USA, 95, (1998), 11163-11168.
[5] Berman, H. M., Olson, W. K., Beveridge, D. L., Westbrook, J., Gelbin, A., Demeny, T., Hsieh, S.-H., Srinivasan, A. R., and Schneider, B., ``The Nucleic Acid Database: A Comprehensive Relational Database of Three-dimensional Structures of Nucleic Acids,'' Biophys. J., 63, (1992), 751-759.
[6] Westcott, T. P., Tobias, I., and Olson, W. K., ``Modeling Self-contact Forces in the Elastic Theory of DNA Supercoiling,'' J. Chem. Phys., 107, (1997), 3967-3980.
[7] Muller-Hill, B., The Lac Operon, Walter
de Gruyter, Berlin, 1996.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentors: Alantha Newman, alantha@dimacs.rutgers.edu, DIMACS
Project Title: Clustering PermutationsGiven an integer k and a set of m permutations on the numbers 1 through n, our goal is to find the "best" partitioning of these permutations into k clusters, each of which represents some set of "similar" permutations. In other words, each of the m input permutations could represent, for example, a preference list. How do we determine which sets of preference lists are most similar?
This project will address this question from a theoretical and experimental perspective.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Nina Fefferman, feffermn at dimacs.rutgers.edu, DIMACS
Project Title: Sensitivity of Entropy Measures in BiosurveillanceEarly work has demonstrated the use of information theoretic entropy can detect outbreaks in streaming disease incidence data earlier than other methods. However, this work has required human-based decisions using prior knowledge about disease-specific processes. This summer project will explore general preprocessing parameters for disease-blind sensitivity. Work will involve basic statistics, experimental computation and a little information theory.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Nina Fefferman, feffermn at dimacs.rutgers.edu, DIMACS
Project Title: Self-organizing Social NetworksPopulations in which individuals choose their friendships have been shown to be able to converge to stable networks. This summer work will explore whether or not certain affiliation preferences can be proved to converge vs. diverge under different network measures of success. Work will begin as computational experimentation and hopefully lead at least to the formulation of rigorous conjectures, if not provable bounds.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Gene Fiorini, gfiorini at dimacs.rutgers.edu, DIMACS
Project Title: Extremal Properties of k-Partite Graphs of Large Girth, k = 2, 3Project description in pdf form
Extremal graph theory is a branch of graph theory that is interested in studying the following scenario: Suppose G is a family of graphs, P a property and an invariant for each . We wish to determine a value m such that whenever for , then G has property P. Those graphs for which and G does not have property P are said to be the extremal graphs with respect to property P and invariant . For example, suppose G is the family of simple graphs on n vertices, n a positive integer. Moreover, suppose P is the property that "G contains a cycle," and the invariant is the number of edges of G, . Then (the number of edges a graph on n vertices can possess and still not contain a cycle) and the extremal graphs are trees on n vertices.
Consider all k-partite simple graphs (k = 2, 3) on a finite set of vertices. The objective of this project is to explore bounds on the number of edges that k-partite graphs can have and still be of large girth. That is, what is the maximum number of edges a bipartite or tripartite graph can have and avoid cycles of length n (n = 3, 4, 5, ?)?
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Gyan Bhanot, gyanbhanot at gmail.com, Rutgers University; Cancer Institute of New Jersey and the Institute for Advanced Study
Project Title: Looking for Hapolotype Selection in HapMaP III data in p53 pathway genesSince Darwin's revolutionary idea about the origin of species, there has been continuing debate about the specific mechanisms driving selection and speciation. In spite of several major discoveries in molecular biology, including the recent understanding of DNA structure and the sequencing of the genomes of many organisms, this question remains a central puzzle in biology. We are not challenging the key Darwinian insight that selection acts on fitness changes due to independent mutations in a slowly changing environment and that speciation is due to an accumulation of sufficient genetic divergence over time because of such selection events in genetically isolated subgroups derived from the same ancestral population. However, the molecular details of how this mechanism operates and how best to look for it in SNP and sequence data remains a mystery and this will be the focus of our analysis. The student selected to work in this project will help Dr. Bhanot and his colleagues at the Sanger Institute look for correlations in genotypes and haplotypes in genes in the p53 pathway to identify signatures of co-evolution network dynamics and adaptation. The student must be able to program in MatLab to work on this project. A basic knowledge of population genetics is also desirable (but not essential).
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Debbie Yuster, yuster@math.rutgers.edu , DIMACS, Mathematics Department
Project Title: Computing Shift EquivalenceTwo square, integer matrices A and B (not necessarily the same size) are shift equivalent if there exist integer matrices R and S, and a whole number m, such that AR=RB, SA=BS, A^m=RS, and B^m=SR. It is an open problem to decide whether or not two given matrices are shift equivalent. Even shift equivalence of 2x2 matrices is not very well understood. Our summer research project will consist of trying to classify and understand different shift equivalence classes of matrices, and possibly shift equivalence classes of group homomorphisms (which are defined analogously). We may also consider the role of the number m in the shift equivalence relation. Prerequisite: a strong background in linear algebra. Computer programming experience would be helpful but is not necessary.
Reference:
[1] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding [Chapter 7], Cambridge University Press.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentors: Debbie Yuster, yuster@math.rutgers.edu , DIMACS, Mathematics Department
Project Title: Using Combinatorics to Gain Insight into GenomicsBiologists may look at an organism's genome (DNA sequence) and ask how it evolved. In this project, we will use generating functions, a powerful mathematical tool, to list alternate DNA sequences that might have arisen for an organism. From this data we will decide how likely the actual DNA sequence is, and draw conclusions about the organism's evolutionary path. Prerequisite: Computer programming experience.
Reference:
[1] D. Zeilberger, "Enumerative and Algebraic Combinatorics", in
Princeton Companion to Mathematics, (Timothy Gowers, ed.), Princeton
University Press, 550-561,
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/enu.html
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: Aaron Jaggard, adj@dimacs.rutgers.edu , DIMACS
Project Title: Pattern Avoidance and Parallels Between Families of Permutations
The broad questions motivating this project involve parallels
between different classes of permutations: Given two different
classes of permutations---e.g., all permutations and the set of
involutions (permutations whose square is the identity
permutation)---which combinatorial questions have (approximately)
the same answer when asked of both classes? (For example, the
probability that a permutation in the symmetric group
Sn contains a
specified subsequence of k distinct integers is exactly
1/k!,
while the probability that an involution in Sn
contains the
subsequence approaches 1/k! as n approaches infinity
[3].)
In this project, we'll focus on questions related to
pattern avoidance by permutations; a permutation
p:{1,2,...,n}--->{1,2,...,3} (which we write as its list
of values
p(1)p(2)...p(n)) avoids the
pattern 231 if there is no triple
(i,j,k) of indices such that
i<j<k and
p(k)<p(i)<p(j)
(i.e., the
order relationships between p(i), p(j), and
p(k) are exactly the same
as those between 2, 3, and 1); avoidance of other patterns is defined
analogously. Depending on the interests of the student, the questions
that we study may range from concrete (as in [1], answering questions about
specific patterns) to more abstract (as in [2], answering questions about
families of patterns or, even more generally, about parallels
between different families of patterns). We'll use Mathematica or Maple
to help suggest/test conjectures, but extensive programming experience
is not required.
1. O. Guibert, E. Pergola, and R. Pinzani, "Vexillary involutions are enumerated by Motzkin numbers," Ann. Comb., 5 (2):153-174, 2001 (link).
2. A.D. Jaggard, "Prefix exchanging and pattern avoidance by involutions," Elec. J. Comb., 9 (2): Research paper #16, 2003 (link).
3. B.D. McKay, J. Morse, and H.S. Wilf, "The Distributions of the Entries
of Young Tableaux," J. Comb. Th. A, 97 (1):117-128, 2002 (link)..
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentors: Endre Boros, boros at rutcor.rutgers.edu, RUTCOR
Project Title: Minimum Cost Optimal Decision Tree
In many situations costly tests lead to a final diagnosis. Based on past data, it is a hard problem to find the best diagnosis based on the attributes. Even harder to find the one which provides the best diagnosis at the smallest expected cost. The project will try out a new method based on dynamic programming. Knowledge of java is a plus, but not a must.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentors: Endre Boros, boros at rutcor.rutgers.edu, RUTCOR and Vladimir Gurvich, gurvich at rutcor.rutgers.edu, RUTCOR
Project Title: Cyclic Games
A large family of two-person games are equivalent with the so called cyclic games: played in a directed graph in which every arc has a cost associated, and where every node is either black or white. Both players -- black and white -- choose a single outgoing arc from the vertices they control, and the game ends in the unique cycle we get from a designated initial node following the chosen arcs. The value of the game is the average of the weights of the arcs in the terminal cycle. White wants to maximize this value, while black wants to minimize it. This simple game is known to have a uniformly optimal choice of arcs (strategy) for both players which provide the optimal value from any initial node. It is however not clear how fast one can find this optimal strategy. This is a challenging problem, belonging to both NP and co-NP, but still not having a polynomial time solution. The project will try several different algorithmic ideas, and develop new ones.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentors: Myong K. Jeong, mjeong at rci.rutgers.edu, RUTCOR and Department of Industrial and Systems Engineering and Kyung S. Shin, kshin at rci.rutgers.edu, RUTCOR
Project Title: Hybrid Evolutionary Algorithms for Feature Selection in Genomics and Proteomics
In most of data sets in genomics and proteomics, the number of attributes is huge. So, the problem of finding some important features for classification (e.g, detection of cancers) is very important.. However, when the dimension of a data set is huge, find the optimal features set that optimizes the certain criteria such as separability measures is computationally intractable due to the resulting exponential search space and, hence, most of the available algorithms mostly lead to suboptimal solutions. This project aims at developing a novel hybrid evolutionary algorithm (e.g., genetic algorithm) for feature selection. We will develop new local search operations that will be embedded in hybrid genetic algorithms to fine-tune the search.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Wanpracha (Art) Chaovalitwongse, wchaoval at rci.rutgers.edu, Department of Industrial Engineering
Project Title: Brain State Identification: Classification of Neurophysiological SignalsUnderstanding the link between mental states and brain neurophysiology has long been an open problem in cognitive science and neuroscience. Not only will this knowledge unlock the complexity of human brain, but it can be used to improve human performance. This problem is very challenging and extremely difficult mainly due to the sophisticated structure of human cognitive system as well as the complexity of brainwave activity such as electroencephalogram (EEG) recordings. In this project, we will explore signal processing, rigorous mathematical modeling and statistical approaches to identify and classify distinctive patterns in EEG recordings from various mental states. These approaches will also be applied to the diagnosis and treatment of epilepsy, the second most common brain disorder. Epilepsy is characterized by recurrent episodes of seizure. We will use our approaches to identify and classify normal and pre-seizure states of epilepsy patients.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Wanpracha (Art) Chaovalitwongse, wchaoval at rci.rutgers.edu, Department of Industrial Engineering
Project Title: Optimizing Cooperative Sensors in BattlespaceWide Area Search Munitions (WASMs) are unmanned aerial vehicles
with an array of onboard sensors, a warhead or other kill mechanism,
and autonomous flight capabilities. WASMs have played many important
roles in the modern battle field including reconnaissance, search,
battle damage assessment, or communications relay. The ATR (automatic
target recognition) system in WASM is used to identify potential targets and broadcast this information to other WASMs. However, target identification is subject to errors. For example, two WASMs might detect the same target, but associate with that target two separate target tracks. Conversely, two WASMs might detect separate targets, but assign the same target ID to both targets. We call this problem as the object misidentification (OMI) problem. To solve the OMI problem for a set of points in 4-dimensional space (time, longitude, latitude and altitude), we will investigate data mining techniques like clustering to identify the individual route of each target (detected point). The overall goal is to reconstruct the battle space using statistical, optimization, and data mining approaches.
* You must be a U.S. Citizen or Permanent Resident to be eligible for this project.
Mentor: Paul Kantor, kantor@scils.rutgers.edu , School of Communication, Information and Library Studies
Project Title: Game Theoretic Aspects of Homeland SecurityThe effort to protect our country form the threat of smuggled weapons is a non-zero sum game, in which the opponent's estimates of the value of a success are different from our own estimates of the cost of failure. The problem is known under the name "Ispector Game". The summer project will examine this problem in the context of an ongoing research program on the problem of optimal detection of nuclear threats at borders, and within the country.
* You must be a enrolled at a U.S. university to be eligible for this
project.
Mentor: Aaron D. Jaggard, adj@dimacs.rutgers.edu , DIMACS
Project Title: Permutation Statistics and Parallels Between Families of Permutations
The broad questions motivating this project involve parallels
between different classes of permutations: Given two different
classes of permutations---e.g., all permutations and the set of
involutions (permutations whose square is the identity
permutation)---which combinatorial questions have (approximately)
the same answer when asked of both classes? (For example, the
probability that a permutation in the symmetric group
Sn contains a
specified subsequence of k distinct integers is exactly
1/k!,
while the probability that an involution in Sn
contains the
subsequence approaches 1/k! as n approaches infinity
[3].)
In this project, we'll focus on questions related to
permutation statistics. These are nonnegative-integer-valued functions on permutations; classical examples of statistics on a permutation p include its descent number des(p) (the number of i such that p(i)>p(i+1)), the number of inversions inv(p) (the number of i < j such that p(i)>p(j)), and the major index maj(p) (the sum of the values i such that p(i)>p(i+1)). One important problem is the determination of the distribution of a statistic (or tuples of statistics)---i.e., the number of permutations for which the statistic takes a certain value---over all permutations of a given length. A number of interesting results have been obtained showing that certain statistics (or tuples of statistics) have the same distribution; see [1] for one recent example of this that also provides a way to decompose classical statistics into sums of other statistics.
1. E. Babson and E. Steingrímsson, "Generalized Permutation Patterns and a Classification of the Mahonian Statistics," Séminaire Lotharingien de Combinatoire, B44b (2000) (link).
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: Aaron D. Jaggard, adj@dimacs.rutgers.edu , DIMACS
Project Title: Protecting Internet Routing
The Border Gateway Protocol (BGP) provides best-effort connectivity between the component subnetworks of the Internet, a task called interdomain routing. However, BGP lacks any security mechanism, so accidental router misconfiguration and intentional attacks can have far-reaching effects on network stability and traffic flow. Simply adding security mechanisms doesn't prevent these problems because BGP also lacks the guarantee that specification-compliant inputs always produce stable routes across the network.
This project addresses these shortcomings through research on various assumptions that guarantee good routing behavior and on methods to verify or enforce these assumptions to prevent deviation from that behavior. The specific focus and the techniques used will account for the background and interests of the student; possibilities include theoretical analysis, game-theoretic modeling of router behavior, modeling and simulation, and analysis of real-world routing-policy data. Some recent relevant work is described here.
Neither programming experience nor familiarity with Internet routing
is required.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: Ji Young Choi, JYChoi@ship.edu, Shippensburg University
Project Title: The boundaries of the minimum Pk-total weights for simple connected graphs
The sum of the weights on every path of length k in a graph with edges of weight 1 or -1 is called the Pk-total weight of the +/- 1-assigned graph. The minimum of the absolute value of the Pk-total weights of a graph considering every possible +/- 1 assignment is called the minimum Pk-total weight. This project is to study the boundaries of the minimum Pk-total weights for simple connected graphs.
* You must be a enrolled at a U.S. university to be eligible for this project.
Mentor: Liviu Iftode and S. Muthukrishnan, iftode@cs.rutgers.edu and muthu@cs.rutgers.edu, Rutgers University
Project Title: Game-theoretic analysis of climbing social ladder in networks
In social networks (say Facebook), there are rules for how people discover each other and become friends. For example, say person A desires to become friends with B. The rules constraint A's ability to become B's friend outright and induces a game-theoretic component. A has to judiciously make other intermediate friends in order to eventually become B's friend. The project will involve modeling this situation, studying the game theory and dynamics of various parties, and understanding the price of anarchy and stability of the game. The situation above is an example of a more general phenomenon in networks where people learn and gain trust of others incrementally for nefarious (in DHS settings) or potentially harmless (in social networks) purposes.
* You must be a enrolled at a U.S. university to be eligible for this project.
Please revisit this page frequently, additional projects will be posted through January.
Index of REU program
DIMACS Home Page
Contacting the Center
Document last modified on February 17, 2009.
