Mathematics Commons^™

The Complexity Of Linear Algebra, Leann Kay Christensen

Theses Digitization Project

This study examines the complexity of linear algebra. Complexity means how much work, or the number of calculations or time it takes to perform a task. As linear algebra is used more and more in different fields, it becomes useful to study ways of reducing the amount of work required to complete basic procedures.

Optimization In Non-Parametric Survival Analysis And Climate Change Modeling, Iuliana Teodorescu

USF Tampa Graduate Theses and Dissertations

Many of the open problems of current interest in probability and statistics involve complicated data

sets that do not satisfy the strong assumptions of being independent and identically distributed. Often,

the samples are known only empirically, and making assumptions about underlying parametric

distributions is not warranted by the insufficient information available. Under such circumstances,

the usual Fisher or parametric Bayes approaches cannot be used to model the data or make predictions.

However, this situation is quite often encountered in some of the main challenges facing statistical,

data-driven studies of climate change, clinical studies, or financial markets, to name a few. …

Measures Of Centrality Based On The Spectrum Of The Laplacian, Scott D. Pauls, Daniel Remondini

Dartmouth Scholarship

We introduce a family of new centralities, the k-spectral centralities. k-Spectral centrality is a measurement of importance with respect to the deformation of the graph Laplacian associated with the graph. Due to this connection, k-spectral centralities have various interpretations in terms of spectrally determined information.

We explore this centrality in the context of several examples. While for sparse unweighted net- works 1-spectral centrality behaves similarly to other standard centralities, for dense weighted net- works they show different properties. In summary, the k-spectral centralities provide a novel and useful measurement of relevance (for single network elements as well as whole subnetworks) …

Enhancing Effective Depth-Of-Field By Multi-Focus Image Fusion Using Morphological Techniques., Ishita De Ghosh Dr.

Doctoral Theses

A scene to be photographed, usually includes objects at varying distances from the camera. Depth-of-field of a digital camera is the range of distance, all objects within which appear to be sharp in the image. Due to the low depth-of-field of the camera, images acquired by them often suffer from degradation called out-of-foc us blur. One way to enhance the effective depth-of-field is to acquire se veral images of a scene with focus on different parts of it and then combine these images into a single image in such a way that all regions of the scene are in focus. …

Blackbox Reduction Of Some Cryptographic Constructions., Rishiraj Bhattacharyya Dr.

Doctoral Theses

No abstract provided.

Some Results On Cryptanalysis Of Rsa And Factorization., Santanu Sarkar Dr.

Doctoral Theses

In this thesis, we propose some new results in Cryptanalysis of RSA and related Factorization problems. Till date, the best known algorithm to solve the Integer Factorization problem is the Number Field Sieve, which has a runtime greater than exp(log1/3 N) for factoring an integer N. However, if one obtains certain information about the RSA parameters, there are algorithms which can factor the RSA modulus N = pq quite efficiently. The intention of this thesis is to identify such weaknesses of the RSA cryptosystem and its variants. Further we study results related to factorization.In Africacrypt 2008, Nitaj presented a class …

Convergence Analysis Of A Multigrid Algorithm For The Acoustic Single Layer Equation, Simon Gemmrich, Jay Gopalakrishnan, Nilima Nigam

Mathematics and Statistics Faculty Publications and Presentations

We present and analyze a multigrid algorithm for the acoustic single layer equation in two dimensions. The boundary element formulation of the equation is based on piecewise constant test functions and we make use of a weak inner product in the multigrid scheme as proposed in Bramble et al. (1994) . A full error analysis of the algorithm is presented. We also conduct a numerical study of the effect of the weak inner product on the oscillatory behavior of the eigenfunctions for the Laplace single layer operator.

On The Hardness Of Counting And Sampling Center Strings, Christina Boucher, Mohamed Omar

All HMC Faculty Publications and Research

Given a set S of n strings, each of length ℓ, and a nonnegative value d, we define a center string as a string of length ` that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of center strings for a given set of strings S and input parameters n, ℓ, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, ℓ, or d is fixed leads to …

Distributed Algorithms For Initialization And Topology Control In Wireless Ad Hoc Networks., Subhasis Bhattacharjee Dr.

Doctoral Theses

Wireless ad hoc networking is an upcoming communication technology that makes exchange of information possible without any pre-existing infrastructure. Over the last decade it has grabbed tremendous interest in the research community due to its easy deployability and high flexibility, with numerous applications to social, industrial and personal uses. In this thesis, we designed effcient light weight distributed algorithms based on minimal local information to resolve the problems related to the initialization and topology configuration of wireless ad hoc networks with special emphasis on optimal utilization of limited resources. Once the ad hoc nodes with in-built radio transceivers are deployed …

Studies On Public Key And Identity-Based Cryptographic Primitives., Mahabir Prasad Jhanwar Dr.

Doctoral Theses

No abstract provided.

Analysis Of The “Travelling Salesman Problem” And An Application Of Heuristic Techniques For Finding A New Solution, Mateusz Pacha-Sucharzewski

Undergraduate Review

In 1832, a German travelling salesman published a handbook describing his profession. Sadly, his name is unknown; he only stated that the book was written by “one old travelling salesman.” However, he has come down in history thanks to a rather simple and quite obvious observation. He pointed out that when one goes on a business trip, one should plan it carefully; by doing so, one can “win” a great deal of time and increase the trip’s “economy.” Two centuries later, mathematicians and scientists are still struggling with what is now known as the “Travelling Salesman Problem” (TSP).

Commuting Smoothed Projectors In Weighted Norms With An Application To Axisymmetric Maxwell Equations, Jay Gopalakrishnan, Minah Oh

Mathematics and Statistics Faculty Publications and Presentations

We construct finite element projectors that can be applied to functions with low regularity. These projectors are continuous in a weighted norm arising naturally when modeling devices with axial symmetry. They have important commuting diagram properties needed for finite element analysis. As an application, we use the projectors to prove quasioptimal convergence for the edge finite element approximation of the axisymmetric time-harmonic Maxwell equations on nonsmooth domains. Supplementary numerical investigations on convergence deterioration at high wavenumbers and near Maxwell eigenvalues and are also reported.

Convergence Of The Mean Shift Algorithm And Its Generalizations, Ting Hu

Electronic Theses and Dissertations

Mean shift is an effective iterative algorithm widely used in image analysis tasks like tracking, image segmentation, smoothing, filtering, edge detection and etc. It iteratively estimates the modes of the probability function of a set of sample data points based in a region. Mean shift was invented in 1975, but it was not widely used until the work by Cheng in 1995. After that, it becomes popular in computer vision. However the convergence, a key character of any iterative algorithm, has been rigorously proved only very recently, but with strong assumptions. In this thesis, the method of mean shift is …

Information-Preserving Structures: A General Framework For Quantum Zero-Error Information, Robin Blume-Kohout, Hui Khoon Ng, David Poulin, Lorenza Viola

Dartmouth Scholarship

Quantum systems carry information. Quantum theory supports at least two distinct kinds of information (classical and quantum), and a variety of different ways to encode and preserve information in physical systems. A system’s ability to carry information is constrained and defined by the noise in its dynamics. This paper introduces an operational framework, using information-preserving structures, to classify all the kinds of information that can be perfectly (i.e., with zero error) preserved by quantum dynamics. We prove that every perfectly preserved code has the same structure as a matrix algebra, and that preserved information can always be corrected. We …

Fast Placement And Floorplanning Methods In Modern Reconfigurable Fpgas., Pritha Baneerjee Dr.

Doctoral Theses

FPGA Field-programmable gate-arrays (FPGA) are programmable hardware platforms with pre-fabricated logic and interconnects, which are electrically programmed by the user to realize a variety of circuits frequently required in a wide range of applications. Unlike application-specific integrated-circuits (ASICs), where realization of a circuit design takes several man-hours and enormous effort, the pre-fabricated logic and interconnects can be quickly programmed according to the design specification and made functional. Thus, in contrast to the ASICs, FPGAs can be customized and reconfigured depending on the need of the user. A basic FPGA chip consists of a set of configurable logic blocks (CLB) and …

Application Of Combinatorial Structures To Key Predistribution In Sensor Networks And Traitor Tracing., Sushmita Ruj Dr.

Doctoral Theses

From time immemorial people have used cryptography for secure communication. Cryptography has decided the fate of many kings and queens as well as the outcome of various wars. It has become all the more important nowadays, with the growing need of electronic communication. We now live in a society where electronic networks pervade all aspects of our professional and private lives. We all use cryptography when we do bank transfers by ATM, or SWIFT, while using the mobile phones and i-phones, SSL protocols or using password protected machines. Though electronic communication is fast and easy, it is vulnerable to security …

Snort: A Combinatorial Game, Keiko Kakihara

Theses Digitization Project

This paper focuses on the game Snort, which is a combinatorial game on graphs. This paper will explore the characteristics of opposability through examples. More fully, we obtain some neccessary conditions for a graph to be opposable. Since an opposable graph guarantees a second player win, we examine graphs that result in a first player win.

Geometric Characterization Of Digital Objects: Algorithms And Applications To Image Analysis., Arindam Biswas Dr.

Doctoral Theses

Several problems of characterizing a digital object, and particularly, those related to boundary description, have been studied in this thesis. New algorithms and their applications to various aspects of image analysis and retrieval have been reported. A combinatorial technique for constructing the outer and inner isothetic covers of a digital object has been developed. The resolution of the background 2D grid can be changed by varying the grid spacing, and this procedure can be used to extract shape and topological information about the object. Next, an algorithm has been designed for constructing the orthogonal (convex) hull of a digital object …

Normal Surfaces And Heegaard Splittings Of 3-Manifolds., Tejas Kalelkar Dr.

Doctoral Theses

This thesis deals with various questions regarding normal surfaces and Heegaard splittings of 3-manifolds.Chapter 1The first chapter is divided into two parts. In the first, we give an outline of normal surface theory and mention some of its important applications. The second part gives an overview of the theory of Heegaard splitting surfaces and a few of its applications. None of the material covered in this chapter is original and it is meant solely as an exposition of known results.Chapter 2In this chapter, we give a lower bound on the Euler characteristic of a normal surface, a topological invariant, in …

Studies On Construction And List Decoding Of Codes On Some Towers Of Function Fields., M. Prem Laxman Das Dr.

Doctoral Theses

In everyday life, there arise many situations where two parties, sender and receiver, need to communicate. The channel through which they communicate is assumed to be binary symmetric, that is, it changes 0 to 1 and vice versa with equal probability. At the receiver’s end, the sent message has to be recovered from the corrupted received word using some reasonable mechanism. This real life problem has attracted a lot of research in the past few decades. A solution to this problem is obtained by adding redundancy in a systematic manner to the message to construct a codeword. The collection of …

Image And Video Compression Using Block Truncation Coding And Pattern Fitting For Fast Decoding., Bibhas Chandra Dhara Dr.

Doctoral Theses

In the present era of multimedia, the requirement of image/video storage and transmission for video conferencing, image and video retrieval, video playback, etc. are increasing exponentially. As a result, the need for better compression technology is always in demand. The limited bandwidth of internet also asks for transmission of desired objects only. Progressive image transmission provides such facilities, where transmission is done in steps and the transmission of undesired image can be stopped at an early stage. Modern applications, in addition to high compression ratio, also demand for efficient encoding and decoding processes, so that computational constraint of many real-time …

Web Surfer Models: Preprocessing, Page Ranking, And Quantitative Evaluation., Narayan L. Bhamidipati Dr.

Doctoral Theses

The World Wide Web [12] (usually referred to as the Web, WWW or W3) is an enormous collection of data available over the Internet, which is a vast network of computers. It was created in the year 1990 by Tim Berners-Lee, while he worked at CERN, Switzerland, and was made available over the Internet in 1991. The World Wide Web Consortium [136] authoritatively defines the Web as the universe of network-accessible information, the embodiment of human knowledge. The Web consists of objects, also called documents or pages in a generic sense, that are identified using a Uniform Resource Identifier (URI), …

Placement And Range Assignment In Power-Aware Radio Networks., Gautam Kumar Das Dr.

Doctoral Theses

Due to the extraordinary growth of demand in mobile communication facility, design of efficient systems for providing specialized services has become an important issue in wireless mobility research. Broadly speaking, there are two major models for wireless networking: single-hop and multi-hop. The single-hop model [110] is based on the cellular network, and it provides one-hop wireless connectivity between the host and the static nodes known as base stations. single-hop networks rely on a fixed backbone infrastructure that interconnects all the base stations by high speed wired links. On the other hand, the multi-hop model requires neither fixed wired infrastructure nor …

Algorithms For Some Geometric Facility Location And Path Planning Problems., Sasanka Roy Dr.

Doctoral Theses

The facility location problem is a resource allocation problem that mainly deals with adequate placement of various types of facilities to serve a distributed set of demands satisfying the nature of interactions between the demands and facilities and optimizing the cost of placing/maintaining the facilities and the quality of services.The facility location problem is well-studied in the Operations Research literature and recently has received a lot of attention in the Computer Science community. For a company, the facility location problem provides more strategic decisions than just giving importance to locate the lowest cost space for storing its products. While identifying …

Geometric Primitives In Digital Images: Analyses And Applications Using Digital Geometry., Partha Bhowmick Dr.

Doctoral Theses

No abstract provided.

Construction Of (Hierarchical) Identity-Based Encryption Protocols Using Bilinear Pairing., Sanjit Chatterjee Dr.

Doctoral Theses

Science, it is argued [65], advances through paradigm shifts. Concepts emerge that open-up new vistas of research, fundamentally changing the way we are used to looking at things. Between these paradigm shifts remain the periods of consolidation. Periods when human mind explores the newly found territory, shedding light on hitherto unknown dimensions. If radical changes are the hallmarks of paradigm shifts, the period within witnesses small but continuous developments, occasionally marked by its own milestones. It is in these periods that human faculty tries to grasp the full significance of the new concepts, consolidates its gains and thereby pushes the …

Some Necessary Conditions Of Boolean Functions To Resist Algebraic Attacks., Deepak Dalai Dr.

Doctoral Theses

No abstract provided.

A Study On Time/Memory Trade-Off Cryptanalysis., Sourav Mukhopadhyay Dr.

Doctoral Theses

At the beginning of 2003, I was searching for a suitable area to do my PhD. My respected guide Prof. Palash Sarkar assigned me to do a survey work on block cipher cryptanalysis. I found myself very interested in this area. I am very lucky that I joined into a golden group – Cryptology Research Group of India formed by our beloved teacher Prof. Bimal Roy and had the opportunity to work with Prof. Palash Sarkar, Dr. Subhomoy Maitra, Prof. Rana Barua and many others. I have been inspired by many persons during my PhD work.I would like to begin …

Concatenative Text-To-Speech Synthesis: A Study On Standard Colloquial Bengali., Soumen Chowdhury Dr.

Doctoral Theses

The primary communication process between human beings is Speech. Speech synthesis is the automatic and artificial generation of the speech signal by a machine. A TTS (Text-To-Speech) synthesis system is one which can generate speech signal from a string of text in a given language. The development in the speech synthesis systems in various languages has been going on for several decades. With the unprecedented expansion of IT (Information Technology) invading the life of the common man it is highly desirable that at least the information dissemination be made via the speech mode which is the most natural mode of …

Some Geometrical Aspects Of The Cone Linear Complementarity Problem., Madhur Malik Dr.

Doctoral Theses

Cone Linear Complementarity ProblemLet V be a finite dimensional real inner product space and K be a closed convex cone in V. Given a linear transformation L : V → V and a vector q ∈ V the cone linear complementarity problem or linear complementarity problem over K, denoted as LCP(K, L, q), is to find a vector x ∈ K such thatL(x) + q ∈ K+ and hx, L(x) + qi = 0,where h., .i denotes an inner product on V and K is the dual cone of K defined as:K∗ := {y ∈ V : hx, yi ≥ …