%0 Journal Article
%J IEEE Transactions on Circuits and Systems for Video Technology
%D 2011
%T Special Issue on Video Analysis on Resource-Limited Systems
%A Chellapa, Rama
%A Cavallaro, A.
%A Wu,Y.
%A Shan, C.
%A Fu, Y.
%A Pulli, K.
%K computational complexity
%K Image Enhancement
%K Special issues and sections
%K Video compression
%X The 17 papers in this special issue focus on resource-limited systems.
%B IEEE Transactions on Circuits and Systems for Video Technology
%V 21
%P 1349 - 1352
%8 2011/10//
%@ 1051-8215
%G eng
%N 10
%R 10.1109/TCSVT.2011.2165795
%0 Conference Paper
%B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)
%D 2010
%T New Constructive Aspects of the Lovasz Local Lemma
%A Haeupler,B.
%A Saha,B.
%A Srinivasan, Aravind
%K acyclic edge coloring
%K Algorithm design and analysis
%K Approximation algorithms
%K Approximation methods
%K computational complexity
%K Computer science
%K constant factor approximation algorithm
%K graph colouring
%K Linearity
%K Lovasz Local Lemma
%K MAX k-SAT
%K Monte Carlo Algorithm
%K Monte Carlo methods
%K Moser-Tardos algorithm
%K nonrepetitive graph coloring
%K output distribution
%K polynomial sized core subset
%K Polynomials
%K Probabilistc Method
%K probabilistic analysis
%K probabilistic logic
%K probability
%K Ramsey type graph
%K Sampling methods
%K Santa Claus Problem
%X The Lov'{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of ``bad'' events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} – the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized ``core'' subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this.
%B 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)
%I IEEE
%P 397 - 406
%8 2010/10/23/26
%@ 978-1-4244-8525-3
%G eng
%R 10.1109/FOCS.2010.45
%0 Conference Paper
%B Software Testing, Verification and Validation Workshops, 2009. ICSTW '09. International Conference on
%D 2009
%T Towards Dynamic Adaptive Automated Test Generation for Graphical User Interfaces
%A Xun Yuan
%A Cohen,M. B
%A Memon, Atif M.
%K adaptive automated test generation
%K computational complexity
%K event sequence length
%K evolutionary algorithm
%K evolutionary computation
%K graphical user interface
%K Graphical user interfaces
%K GUI test case
%K program testing
%X Graphical user interfaces (GUIs) present an enormous number of potential event sequences to users. During testing it is necessary to cover this space, however the complexity of modern GUIs has made this an increasingly difficult task. Our past work has demonstrated that it is important to incorporate "context” into GUI test cases, in terms of event combinations, event sequence length, and by considering all possible starting and ending positions for each event. Despite the use of our most refined modeling techniques, many of the generated test cases remain unexecutable. In this paper, we posit that due to the dynamic state-based nature of GUIs, it is important to incorporate feedback from the execution of tests into test case generation algorithms. We propose the use of an evolutionary algorithm to generate test suites with fewer unexecutable test cases and higher event interaction coverage.
%B Software Testing, Verification and Validation Workshops, 2009. ICSTW '09. International Conference on
%P 263 - 266
%8 2009/04//
%G eng
%R 10.1109/ICSTW.2009.26
%0 Conference Paper
%B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008
%D 2008
%T Flow Algorithms for Parallel Query Optimization
%A Deshpande, Amol
%A Hellerstein,L.
%K Casting
%K computational complexity
%K Cost function
%K Databases
%K Delay
%K distributed environment
%K Educational institutions
%K flow maximization algorithm
%K Interleaved codes
%K interoperator parallelism
%K minimisation
%K multiway join query response time minimization problem
%K parallel database
%K Parallel databases
%K parallel query optimization
%K Partitioning algorithms
%K pipeline processing
%K pipelined parallelism
%K polynomial-time algorithm
%K query planning problem
%K Query processing
%K Web service
%K Web services
%X We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.
%B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008
%I IEEE
%P 754 - 763
%8 2008/04/07/12
%@ 978-1-4244-1836-7
%G eng
%R 10.1109/ICDE.2008.4497484
%0 Conference Paper
%B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
%D 2005
%T Algorithmic graph minor theory: Decomposition, approximation, and coloring
%A Demaine,E. D
%A Hajiaghayi, Mohammad T.
%A Kawarabayashi,K.
%K algorithmic graph minor theory
%K approximation algorithm
%K combinatorial polylogarithmic approximation
%K computational complexity
%K constant-factor approximation
%K graph algorithm
%K graph coloring
%K graph colouring
%K half-integral multicommodity flow
%K largest grid minor
%K maximization problem
%K minimization problem
%K polynomial-time algorithm
%K subexponential fixed-parameter algorithm
%K topological graph theory
%K treewidth
%X At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.
%B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
%P 637 - 646
%8 2005///
%G eng
%R 10.1109/SFCS.2005.14
%0 Conference Paper
%B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on
%D 2005
%T CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems
%A Kianzad,V.
%A Bhattacharyya, Shuvra S.
%A Gang Qu
%K CASPER
%K combined-assignment-scheduling-and-power-management
%K computational complexity
%K distributed system
%K dynamic voltage scaling
%K embedded systems
%K energy reduction
%K genetic algorithm
%K Genetic algorithms
%K graph theory
%K homogeneous multiprocessor system
%K maximal energy saving
%K Multiprocessing systems
%K multiprocessor embedded system
%K optimization loop
%K power management
%K power variation
%K Processor scheduling
%K slack distribution algorithm
%K task assignment
%K task graph scheduling
%X For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (combined assignment, scheduling, and power-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) by S. Hua and G. Qu (2005): applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm by Schmitz et al. (2004), CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA by Schmitz et al. (2002), the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.
%B Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on
%P 191 - 197
%8 2005/07//
%G eng
%R 10.1109/ASAP.2005.23
%0 Conference Paper
%B IEEE Symposium on Information Visualization, 2004. INFOVIS 2004
%D 2004
%T A Rank-by-Feature Framework for Unsupervised Multidimensional Data Exploration Using Low Dimensional Projections
%A Seo,J.
%A Shneiderman, Ben
%K axis-parallel projections
%K boxplot
%K color-coded lower-triangular matrix
%K computational complexity
%K computational geometry
%K Computer displays
%K Computer science
%K Computer vision
%K Data analysis
%K data mining
%K data visualisation
%K Data visualization
%K Displays
%K dynamic query
%K Educational institutions
%K exploratory data analysis
%K feature detection
%K feature detection/selection
%K Feature extraction
%K feature selection
%K graph theory
%K graphical displays
%K histogram
%K Information Visualization
%K interactive systems
%K Laboratories
%K Multidimensional systems
%K Principal component analysis
%K rank-by-feature prism
%K scatterplot
%K statistical analysis
%K statistical graphics
%K statistical graphs
%K unsupervised multidimensional data exploration
%K very large databases
%X Exploratory analysis of multidimensional data sets is challenging because of the difficulty in comprehending more than three dimensions. Two fundamental statistical principles for the exploratory analysis are (1) to examine each dimension first and then find relationships among dimensions, and (2) to try graphical displays first and then find numerical summaries (D.S. Moore, (1999). We implement these principles in a novel conceptual framework called the rank-by-feature framework. In the framework, users can choose a ranking criterion interesting to them and sort 1D or 2D axis-parallel projections according to the criterion. We introduce the rank-by-feature prism that is a color-coded lower-triangular matrix that guides users to desired features. Statistical graphs (histogram, boxplot, and scatterplot) and information visualization techniques (overview, coordination, and dynamic query) are combined to help users effectively traverse 1D and 2D axis-parallel projections, and finally to help them interactively find interesting features
%B IEEE Symposium on Information Visualization, 2004. INFOVIS 2004
%I IEEE
%P 65 - 72
%8 2004///
%@ 0-7803-8779-3
%G eng
%R 10.1109/INFVIS.2004.3
%0 Conference Paper
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%D 2002
%T Dependent rounding in bipartite graphs
%A Gandhi,R.
%A Khuller, Samir
%A Parthasarathy,S.
%A Srinivasan, Aravind
%K Application software
%K Approximation algorithms
%K bipartite graph
%K bipartite graphs
%K broadcast channels
%K broadcast scheduling
%K Broadcasting
%K capacitated vertex cover
%K Character generation
%K computational complexity
%K Computer science
%K Delay
%K edge-sets
%K Educational institutions
%K fair scheduling
%K fractional vectors
%K graph theory
%K per-user fairness properties
%K pipage rounding technique
%K Processor scheduling
%K Random variables
%K random-graph models
%K randomized rounding approach
%K rounding method
%K scheduling
%K Scheduling algorithm
%K telecommunication computing
%K unrelated parallel machines
%X We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%I IEEE
%P 323 - 332
%8 2002///
%@ 0-7695-1822-2
%G eng
%R 10.1109/SFCS.2002.1181955
%0 Conference Paper
%D 1999
%T Building dependable distributed applications using AQUA
%A Ren,J.
%A Cukier, Michel
%A Rubel,P.
%A Sanders,W. H.
%A Bakken,D. E.
%A Karr,D. A.
%K ad hoc methods
%K application programmer
%K AQuA
%K complexities
%K computational complexity
%K dependable distributed applications
%K distributed CORBA application
%K distributed object management
%K Fault tolerance
%K fault tolerant computing
%K proteus
%X Building dependable distributed systems using ad hoc methods is a challenging task. Without proper support, an application programmer must face the daunting requirement of having to provide fault tolerance at the application level, in addition to dealing with the complexities of the distributed application itself. This approach requires a deep knowledge of fault tolerance on the part of the application designer, and has a high implementation cost. What is needed is a systematic approach to providing dependability to distributed applications. Proteus, part of the AQuA architecture, fills this need and provides facilities to make a standard distributed CORBA application dependable, with minimal changes to an application. Furthermore, it permits applications to specify, either directly or via the Quality Objects (QuO) infrastructure, the level of dependability they expect of a remote object, and will attempt to configure the system to achieve the requested dependability level. Our previous papers have focused on the architecture and implementation of Proteus. This paper describes how to construct dependable applications using the AQuA architecture, by describing the interface that a programmer is presented with and the graphical monitoring facilities that it provides
%P 189 - 196
%8 1999///
%G eng
%R 10.1109/HASE.1999.809494
%0 Conference Paper
%B Compression and Complexity of Sequences 1997. Proceedings
%D 1997
%T Hardness of flip-cut problems from optical mapping [DNA molecules application]
%A Dancik,V.
%A Hannenhalli, Sridhar
%A Muthukrishnan,S.
%K binary shift cut
%K Biochemistry
%K Bioinformatics
%K biological techniques
%K Biology
%K biomedical optical imaging
%K combinatorial mathematics
%K combinatorial problem
%K computational complexity
%K computational problems
%K DNA
%K DNA molecule
%K exclusive binary flip cut
%K flip-cut problem hardness
%K Genetic engineering
%K Genomics
%K MATHEMATICS
%K molecular biology
%K molecular biophysics
%K molecule orientation
%K multiple partial restriction maps
%K NP-complete problem
%K optical mapping
%K polynomial time solutions
%K Polynomials
%K sequences
%X Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single “consensus” restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP
%B Compression and Complexity of Sequences 1997. Proceedings
%I IEEE
%P 275 - 284
%8 1997/06/11/13
%@ 0-8186-8132-2
%G eng
%R 10.1109/SEQUEN.1997.666922
%0 Conference Paper
%B , 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings
%D 1997
%T Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
%A Srinivasan, Aravind
%K Approximation algorithms
%K Bandwidth
%K Channel allocation
%K computational complexity
%K Computer science
%K edge-disjoint paths
%K graph theory
%K High speed integrated circuits
%K IEL
%K Image motion analysis
%K Information systems
%K multi-commodity flow relaxation
%K Multiprocessor interconnection networks
%K network routing
%K Optical fiber networks
%K Routing
%K routing problems
%K unsplittable flow
%X We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation
%B , 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings
%I IEEE
%P 416 - 425
%8 1997/10/20/22
%@ 0-8186-8197-7
%G eng
%R 10.1109/SFCS.1997.646130
%0 Conference Paper
%B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings
%D 1996
%T Efficient model checking via the equational μ-calculus
%A Bhat,G.
%A Cleaveland, Rance
%K Automata
%K BDD-based algorithms
%K Boolean functions
%K Calculus
%K compositional model-checking approaches
%K computational complexity
%K Computer science
%K CTL*
%K Data structures
%K Encoding
%K equational variant
%K equational μ-calculus
%K Equations
%K expressive temporal logic
%K Logic
%K Maintenance
%K modal μ-calculus
%K Model checking
%K on-the-fly procedures
%K Surges
%K temporal logic
%K temporal logic model checking
%K unified framework
%X This paper studies the use of an equational variant of the modal μ-calculus as a unified framework for efficient temporal logic model checking. In particular we show how an expressive temporal logic, CTL*, may be efficiently translated into the μ-calculus. Using this translation, one may then employ μ-calculus model-checking techniques, including on-the-fly procedures, BDD-based algorithms and compositional model-checking approaches, to determine if systems satisfy formulas in CTL*
%B , Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings
%I IEEE
%P 304 - 312
%8 1996/07/27/30
%@ 0-8186-7463-6
%G eng
%R 10.1109/LICS.1996.561358
%0 Conference Paper
%B , Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. LICS '95. Proceedings
%D 1995
%T Efficient on-the-fly model checking for CTL
%A Bhat,G.
%A Cleaveland, Rance
%A Grumberg,O.
%K Algorithm design and analysis
%K Automata
%K computational complexity
%K Computer science
%K CTL
%K Encoding
%K finite automata
%K finite-state system
%K global algorithm
%K Logic
%K LTL
%K on-the-fly model checking
%K Performance analysis
%K Safety
%K State-space methods
%K sublogic
%K temporal logic
%K time complexity
%X This paper gives an on-the-fly algorithm for determining whether a finite-state system satisfies a formula in the temporal logic CTL. The time complexity of our algorithm matches that of the best existing “global algorithm” for model checking in this logic, and it performs as well as the best known global algorithms for the sublogics CTL and LTL. In contrast with these approaches, however, our routine constructs the state space of the system under consideration in a need-driven fashion and will therefore perform better in practice
%B , Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. LICS '95. Proceedings
%I IEEE
%P 388 - 397
%8 1995/06/26/29
%@ 0-8186-7050-9
%G eng
%R 10.1109/LICS.1995.523273
%0 Conference Paper
%B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
%D 1995
%T Splitters and near-optimal derandomization
%A Naor,M.
%A Schulman,L. J
%A Srinivasan, Aravind
%K Boosting
%K Circuit testing
%K computational complexity
%K computational linguistics
%K Computer science
%K Contracts
%K derandomization
%K deterministic constructions
%K Educational institutions
%K Engineering profession
%K exhaustive testing
%K fairly general method
%K fixed-subgraph finding algorithms
%K hardness of approximation
%K Information systems
%K k-restrictions
%K learning
%K local-coloring protocol
%K MATHEMATICS
%K near-optimal constructions
%K near-optimal derandomization
%K Parallel algorithms
%K probabilistic bound
%K probability
%K Protocols
%K randomised algorithms
%K Set cover
%K splitters
%X We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits
%B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
%I IEEE
%P 182 - 191
%8 1995/10/23/25
%@ 0-8186-7183-1
%G eng
%R 10.1109/SFCS.1995.492475
%0 Conference Paper
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%D 1994
%T Computing with very weak random sources
%A Srinivasan, Aravind
%A Zuckerman,D.
%K Application software
%K BPP simulations
%K Chor-Goldreich sources
%K computational complexity
%K Computational modeling
%K Computer science
%K Computer simulation
%K cryptography
%K distributed algorithms
%K expander constructions
%K hardness
%K MATHEMATICS
%K min-entropy
%K Physics computing
%K Polynomials
%K probability
%K R-bit string
%K randomness-efficient Leftover Hash Lemma
%K RP algorithms simulation
%K Testing
%K time-space tradeoffs
%K very weak random sources
%X For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson
%B , 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings
%I IEEE
%P 264 - 275
%8 1994/11/20/22
%@ 0-8186-6580-7
%G eng
%R 10.1109/SFCS.1994.365688
%0 Conference Paper
%B International Conference on Application Specific Array Processors, 1994. Proceedings
%D 1994
%T A SIMD solution to the sequence comparison problem on the MGAP
%A Borah,M.
%A Bajwa,R. S
%A Hannenhalli, Sridhar
%A Irwin,M. J
%K AT-optimal algorithm
%K Biological information theory
%K biology computing
%K biosequence comparison problem
%K computational complexity
%K Computer science
%K Costs
%K database size
%K Databases
%K DNA computing
%K dynamic programming
%K dynamic programming algorithms
%K fine-grained massively parallel processor array
%K Genetics
%K Heuristic algorithms
%K maximally similar sequence
%K MGAP parallel computer
%K Micro-Grain Array Processor
%K Military computing
%K molecular biology
%K molecular biophysics
%K Nearest neighbor searches
%K nearest-neighbor connections
%K Parallel algorithms
%K pipeline processing
%K pipelined SIMD solution
%K sequence alignment problem
%K sequences
%X Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128
%B International Conference on Application Specific Array Processors, 1994. Proceedings
%I IEEE
%P 336 - 345
%8 1994/08/22/24
%@ 0-8186-6517-3
%G eng
%R 10.1109/ASAP.1994.331791
%0 Conference Paper
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%D 1993
%T A distributed algorithm for ear decomposition
%A Hannenhalli, Sridhar
%A Perumalla,K.
%A Chandrasekharan,N.
%A Sridhar,R.
%K Asynchronous communication
%K asynchronous communication network
%K Automata
%K Communication networks
%K computational complexity
%K Computer networks
%K Computer science
%K decomposition graph
%K distributed algorithm
%K distributed algorithms
%K Distributed computing
%K Ear
%K ear decomposition
%K graph theory
%K message-optimal
%K network decomposition
%K sorting
%K Testing
%K time-optimal
%X A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%I IEEE
%P 180 - 184
%8 1993/05/27/29
%@ 0-8186-4212-2
%G eng
%R 10.1109/ICCI.1993.315382
%0 Journal Article
%J Information Processing Letters
%D 1992
%T On the difficulty of Manhattan channel routing
%A Greenberg,Ronald
%A JaJa, Joseph F.
%A Krishnamurthy,Sridhar
%K combinatorial problems
%K computational complexity
%K lower bounds
%K VLSI channel routing
%X We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Ω(n) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
%B Information Processing Letters
%V 44
%P 281 - 284
%8 1992/12/21/
%@ 0020-0190
%G eng
%U http://www.sciencedirect.com/science/article/pii/002001909290214G
%N 5
%R 10.1016/0020-0190(92)90214-G
%0 Conference Paper
%B , Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
%D 1992
%T Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs
%A Chandrasekharan,N.
%A Hannenhalli, Sridhar
%K chromatic polynomials
%K computational complexity
%K Computer science
%K graph colouring
%K graph theory
%K matching polynomial
%K Polynomials
%K series-parallel graphs
%K Terminology
%K Tree data structures
%K Tree graphs
%X The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time
%B , Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
%I IEEE
%P 42 - 45
%8 1992/05/28/30
%@ 0-8186-2812-X
%G eng
%R 10.1109/ICCI.1992.227709
%0 Conference Paper
%B Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
%D 1991
%T Towards a theory of nearly constant time parallel algorithms
%A Gil,J.
%A Matias,Y.
%A Vishkin, Uzi
%K computational complexity
%K Estimation
%K nearly constant time parallel algorithms
%K Parallel algorithms
%K positive numbers
%K randomization
%K running time
%K superfast optimal algorithms
%X It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of O(lg* n) (nearly-constant), with high probability, is achieved using n/lg* n (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using n processors, approximates the sum of n positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones
%B Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
%P 698 - 710
%8 1991/10//
%G eng
%R 10.1109/SFCS.1991.185438