Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Mathematics (21)
- Statistics and Probability (19)
- Engineering (13)
- Electrical and Computer Engineering (6)
- Medicine and Health Sciences (3)
-
- Operations Research, Systems Engineering and Industrial Engineering (3)
- Health Information Technology (2)
- Information Security (2)
- Aerospace Engineering (1)
- Cybersecurity (1)
- Economics (1)
- Education (1)
- Higher Education (1)
- Medical Pathology (1)
- Medical Sciences (1)
- Social and Behavioral Sciences (1)
- Institution
- Keyword
-
- Automated Induction, Machine Learning, Knowledge Representation (4)
- Algorithms (3)
- Algorithm Design (2)
- Application-Oriented Fault Tolerance, Multicomputers. (2)
- Chromatic Number (2)
-
- Embedding, Fault Tolerance, Reconfiguration, Ring, Hypercube. (2)
- Embeddings (2)
- Graph-Coloring (2)
- Heuristic Algorithms (2)
- Optimization, Probabilistic Methods, Stock Cutting, Bin Packing (2)
- Reasoning (2)
- Scheduling (2)
- Speedup (2)
- Academic/Educational Applications (1)
- Approximation (1)
- Artificial Intelligence, Database Rule Systems, Rule Indexing, Rule Clustering, Search Strategies, Rule-base. (1)
- Artificial intelligence (1)
- Bibliography (1)
- Branch-And-Bound (1)
- Church-Rosser Property (1)
- Class NC (1)
- Class NG (1)
- Compilers, Formal Languages, Language Processors, LR(l) Grammars, LR(l) Parsing (1)
- Complete Sets of Reductions (1)
- Complexity Of Algorithms (1)
- Computer assisted instruction (1)
- Conant gasket (1)
- Concurrent Systems (1)
- Conditional Reductions (1)
- Cyber resilience (1)
- Publication Year
- File Type
Articles 241 - 270 of 772
Full-Text Articles in Computer Sciences
Master’S Thesis Proposal: Computation Reuse In Stacking And Unstacking, Anne Loomis
Master’S Thesis Proposal: Computation Reuse In Stacking And Unstacking, Anne Loomis
Computer Science Technical Reports
Algorithms for dynamic simulation and control are fundamental to many applications, including computer games and movies, medical simulation, and mechanical design. I propose to explore efficient algorithms for finding a stable unstacking sequence -- an order in which we can remove every object from a structure without causing the structure to collapse under gravity at any step. We begin with a basic unstacking sequence algorithm: consider the set of all objects in a structure. Collect all possible subsets into a disassembly graph. Search the graph, testing the stability of each node as it is visited. Any path of stable nodes …
Detection Of Covert Channel Encoding In Network Packet Delays, Vincent Berk, Annarita Giani, George Cybenko
Detection Of Covert Channel Encoding In Network Packet Delays, Vincent Berk, Annarita Giani, George Cybenko
Computer Science Technical Reports
Covert channels are mechanisms for communicating information in ways that are difficult to detect. Data exfiltration can be an indication that a computer has been compromised by an attacker even when other intrusion detection schemes have failed to detect a successful attack. Covert timing channels use packet inter-arrival times, not header or payload embedded information, to encode covert messages. This paper investigates the channel capacity of Internet-based timing channels and proposes a methodology for detecting covert timing channels based on how close a source comes to achieving that channel capacity. A statistical approach is then used for the special case …
Combinatorial Theorems About Embedding Trees On The Real Line, Amit Chakrabarti, Subhash Khot
Combinatorial Theorems About Embedding Trees On The Real Line, Amit Chakrabarti, Subhash Khot
Computer Science Technical Reports
We consider the combinatorial problem of embedding a tree metric into the real line with low distortion. For two special families of trees --- the family of complete binary trees and the family of subdivided stars --- we provide embeddings whose distortion is provably optimal, up to a constant factor. We also prove that the optimal distortion of a linear embedding of a tree can be arbitrarily low or high even when it has bounded degree.
A Quasi-Ptas For Unsplittable Flow On Line Graphs, Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
A Quasi-Ptas For Unsplittable Flow On Line Graphs, Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
Computer Science Technical Reports
We study the Unsplittable Flow Problem (UFP) on a line graph, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP is contained in DTIME(2^polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. Earlier results on this problem included a polynomial time (2+epsilon)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most …
The Theory Of Trackability With Applications To Sensor Networks, Valentino Crespi, George Cybenko, Guofei Jiang
The Theory Of Trackability With Applications To Sensor Networks, Valentino Crespi, George Cybenko, Guofei Jiang
Computer Science Technical Reports
In this paper, we formalize the concept of tracking in a sensor network and develop a rigorous theory of {\em trackability} that investigates the rate of growth of the number of consistent tracks given a sequence of observations made by the sensor network. The phenomenon being tracked is modelled by a nondeterministic finite automaton and the sensor network is modelled by an observer capable of detecting events related, typically ambiguously, to the states of the underlying automaton. More formally, an input string, $Z^t$, of $t+1$ symbols (the sensor network observations) that is presented to a nondeterministic finite automaton, $M$, (the …
Efficiently Implementing A Large Number Of Ll/Sc Objects, Prasad Jayanti, Srdjan Petrovic
Efficiently Implementing A Large Number Of Ll/Sc Objects, Prasad Jayanti, Srdjan Petrovic
Computer Science Technical Reports
Over the past decade, a pair of instructions called load-linked (LL) and store-conditional (SC) have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS (e.g., UltraSPARC, Itanium) or restricted versions of LL/SC (e.g., POWER4, MIPS, Alpha). Thus, there is a gap between what algorithm designers want (namely, LL/SC) and what multiprocessors actually support (namely, CAS or RLL/RSC). To bridge this gap, a flurry of algorithms that implement LL/SC from CAS have appeared in the literature. The two most recent algorithms are due to …
Mining Frequent And Periodic Association Patterns, Guanling Chen, Heng Huang, Minkyong Kim
Mining Frequent And Periodic Association Patterns, Guanling Chen, Heng Huang, Minkyong Kim
Computer Science Technical Reports
Profiling the clients' movement behaviors is useful for mobility modeling, anomaly detection, and location prediction. In this paper, we study clients' frequent and periodic movement patterns in a campus wireless network. We use offline data-mining algorithms to discover patterns from clients' association history, and analyze the reported patterns using statistical methods. Many of our results reflect the common characteristics of a typical academic campus, though we also observed some unusual association patterns. There are two challenges: one is to remove noise from data for efficient pattern discovery, and the other is to interpret discovered patterns. We address the first challenge …
Towards Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Towards Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Computer Science Technical Reports
Many security protocols hypothesize the existence of a {\em trusted third party (TTP)} to ease handling of computation and data too sensitive for the other parties involved. Subsequent discussion usually dismisses these protocols as hypothetical or impractical, under the assumption that trusted third parties cannot exist. However, the last decade has seen the emergence of hardware-based devices that, to high assurance, can carry out computation unmolested; emerging research promises more. In theory, such devices can perform the role of a trusted third party in real-world problems. In practice, we have found problems. The devices aspire to be general-purpose processors but …
More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Computer Science Technical Reports
Secure Function Evaluation (SFE) problems. We assume that a really trustworthy TTP device will have very limited protected memory and computation environment---a \emph{tiny TTP}. This precludes trivial solutions like "just run the function in the TTP". Traditional scrambled circuit evaluation approaches to SFE have a very high overhead in using indirectly-addressed arrays---every array access's cost is linear in the array size. The main gain in our approach is that array access can be provided with much smaller overhead---$O(\sqrt{N}\log N)$. This expands the horizon of problems which can be efficiently solved using SFE. Additionally, our technique provides a simple way to …
Structural Analysis Of Social Networks With Wireless Users, Guanling Chen, David Kotz
Structural Analysis Of Social Networks With Wireless Users, Guanling Chen, David Kotz
Computer Science Technical Reports
Online interactions between computer users form Internet-based social networks. In this paper we present a structural analysis of two such networks with wireless users. In one network the wireless users participate in a global file-sharing system, and in the other they interact with each other through a local music-streaming application.
Preventing Theft Of Quality Of Service On Open Platforms, Kwang-Hyun Baek, Sean W. Smith
Preventing Theft Of Quality Of Service On Open Platforms, Kwang-Hyun Baek, Sean W. Smith
Computer Science Technical Reports
As multiple types of traffic converge onto one network (frequently wireless), enterprises face a tradeoff between effectiveness and security. Some types of traffic, such as voice-over-IP (VoIP), require certain quality of service (QoS) guarantees to be effective. The end client platform is in the best position to know which packets deserve this special handling. In many environments (such as universities), end users relish having control over their own machines. However, if end users administer their own machines, nothing stops dishonest ones from marking undeserving traffic for high QoS. How can an enterprise ensure that only appropriate traffic receives high QoS, …
Aggregated Path Authentication For Efficient Bgp Security, Meiyuan Zhao, Sean W. Smith, David M. Nicol
Aggregated Path Authentication For Efficient Bgp Security, Meiyuan Zhao, Sean W. Smith, David M. Nicol
Computer Science Technical Reports
The border gateway protocol (BGP) controls inter-domain routing in the Internet. BGP is vulnerable to many attacks, since routers rely on hearsay information from neighbors. Secure BGP (S-BGP) uses DSA to provide route authentication and mitigate many of these risks. However, many performance and deployment issues prevent S-BGP's real-world deployment. Previous work has explored improving S-BGP processing latencies, but space problems, such as increased message size and memory cost, remain the major obstacles. In this paper, we combine two efficient cryptographic techniques---signature amortization and aggregate signatures---to design new aggregated path authentication schemes. We propose six constructions for aggregated path authentication …
An O(N^{5/2} Log N) Algorithm For The Rectilinear Minimum Link-Distance Problem In Three Dimensions (Extended Abstract), Robert Scot Drysdale, Clifford Stein, David P. Wagner
An O(N^{5/2} Log N) Algorithm For The Rectilinear Minimum Link-Distance Problem In Three Dimensions (Extended Abstract), Robert Scot Drysdale, Clifford Stein, David P. Wagner
Computer Science Technical Reports
In this paper we consider the Rectilinear Minimum Link-Distance Problem in Three Dimensions. The problem is well studied in two dimensions, but is relatively unexplored in higher dimensions. We solve the problem in O(B n log n) time, where n is the number of corners among all obstacles, and B is the size of a BSP decomposition of the space containing the obstacles. It has been shown that in the worst case B = Theta(n^{3/2}), giving us an overall worst case time of O(n^{5/2} log n). Previously known algorithms have had worst-case running times of Omega(n^3).
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Computer Science Technical Reports
There is increasing interest in location-aware systems and applications. It is important for any designer of such systems and applications to understand the nature of user and device mobility. Furthermore, an understanding of the effect of user mobility on access points (APs) is also important for designing, deploying, and managing wireless networks. Although various studies of wireless networks have provided insights into different network environments and user groups, it is often hard to apply these findings to other situations, or to derive useful abstract models. In this paper, we present a general methodology for extracting mobility information from wireless network …
Department Of Computer Science Activity 1998-2004, David Kotz
Department Of Computer Science Activity 1998-2004, David Kotz
Computer Science Technical Reports
This report summarizes much of the research and teaching activity of the Department of Computer Science at Dartmouth College between late 1998 and late 2004. The material for this report was collected as part of the final report for NSF Institutional Infrastructure award EIA-9802068, which funded equipment and technical staff during that six-year period. This equipment and staff supported essentially all of the department's research activity during that period.
Graphical Models Of Residue Coupling In Protein Families, John Thomas, Naren Ramakrishnan, Chris Bailey-Kellogg
Graphical Models Of Residue Coupling In Protein Families, John Thomas, Naren Ramakrishnan, Chris Bailey-Kellogg
Computer Science Technical Reports
Identifying residue coupling relationships within a protein family can provide important insights into intrinsic molecular processes, and has significant applications in modeling structure and dynamics, understanding function, and designing new or modified proteins. We present the first algorithm to infer an undirected graphical model representing residue coupling in protein families. Such a model serves as a compact description of the joint amino acid distribution, and can be used for predictive (will this newly designed protein be folded and functional?), diagnostic (why is this protein not stable or functional?), and abductive reasoning (what if I attempt to graft features of one …
Shemp: Secure Hardware Enhanced Myproxy, John Marchesini, Sean Smith
Shemp: Secure Hardware Enhanced Myproxy, John Marchesini, Sean Smith
Computer Science Technical Reports
While PKI applications differ in how they use keys, all applications share one assumption: users have keypairs. In previous work, we established that desktop keystores are not safe places to store private keys, because the TCB is too large. These keystores are also immobile, difficult to use, and make it impossible for relying parties to make reasonable trust judgments. Since we would like to use desktops as PKI clients and cannot realistically expect to redesign the entire desktop, this paper presents a system that works within the confines of modern desktops to shrink the TCB needed for PKI applications. Our …
High-Throughput Inference Of Protein-Protein Interaction Sites From Unassigned Nmr Data By Analyzing Arrangements Induced By Quadratic Forms On 3-Manifolds, Ramgopal R. Mettu, Ryan H. Lilien, Bruce Randall Donald
High-Throughput Inference Of Protein-Protein Interaction Sites From Unassigned Nmr Data By Analyzing Arrangements Induced By Quadratic Forms On 3-Manifolds, Ramgopal R. Mettu, Ryan H. Lilien, Bruce Randall Donald
Computer Science Technical Reports
We cast the problem of identifying protein-protein interfaces, using only unassigned NMR spectra, into a geometric clustering problem. Identifying protein-protein interfaces is critical to understanding inter- and intra-cellular communication, and NMR allows the study of protein interaction in solution. However it is often the case that NMR studies of a protein complex are very time-consuming, mainly due to the bottleneck in assigning the chemical shifts, even if the apo structures of the constituent proteins are known. We study whether it is possible, in a high-throughput manner, to identify the interface region of a protein complex using only unassigned chemical shift …
Tr-2005005: Geometric Interpretation And Spherical Property Of The 2-D Poisson Kernel, Sergei Artamoshin
Tr-2005005: Geometric Interpretation And Spherical Property Of The 2-D Poisson Kernel, Sergei Artamoshin
Computer Science Technical Reports
No abstract provided.
Tr-2005009: Additive Preconditioning In Matrix Computations, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt
Tr-2005009: Additive Preconditioning In Matrix Computations, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt
Computer Science Technical Reports
No abstract provided.
Tr-2005013: Typing In Reflective Combinatory Logic, Nikolai Krupski
Tr-2005013: Typing In Reflective Combinatory Logic, Nikolai Krupski
Computer Science Technical Reports
No abstract provided.
Tr-2005002: The Basic Intuitionistic Logic Of Proofs, Sergei Artemov, Rosalie Iemhoff
Tr-2005002: The Basic Intuitionistic Logic Of Proofs, Sergei Artemov, Rosalie Iemhoff
Computer Science Technical Reports
No abstract provided.
Tr-2005004: Basic Systems Of Epistemic Logic With Justification, Sergei Artemov, Elena Nogina
Tr-2005004: Basic Systems Of Epistemic Logic With Justification, Sergei Artemov, Elena Nogina
Computer Science Technical Reports
No abstract provided.
Tr-2005006: Integration Of Laser Vibrometry With Infrared Video For Multimedia Surveillance Display, Zhigang Zhu, Weihong Li
Tr-2005006: Integration Of Laser Vibrometry With Infrared Video For Multimedia Surveillance Display, Zhigang Zhu, Weihong Li
Computer Science Technical Reports
No abstract provided.
Tr-2005007: Null Spaces, Eigensystems, And Small-Rank Modifications, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt
Tr-2005007: Null Spaces, Eigensystems, And Small-Rank Modifications, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt
Computer Science Technical Reports
No abstract provided.
Tr-2005008: Toeplitz And Hankel Meet Hensel And Newton Modulo A Power Of Two, Victor Y. Pan, Brian Murphy, Rhys E. Rosholt, Xinmao Wang
Tr-2005008: Toeplitz And Hankel Meet Hensel And Newton Modulo A Power Of Two, Victor Y. Pan, Brian Murphy, Rhys E. Rosholt, Xinmao Wang
Computer Science Technical Reports
No abstract provided.
Tr-2005010: Multi-Hop Probing Asymptotics In Available Bandwidth Estimation: Stochastic Analysis, Xiliang Liu, Kaliappa Ravindran, Dmitri Loguinov
Tr-2005010: Multi-Hop Probing Asymptotics In Available Bandwidth Estimation: Stochastic Analysis, Xiliang Liu, Kaliappa Ravindran, Dmitri Loguinov
Computer Science Technical Reports
No abstract provided.
Tr-2005011: Logic Of Proofs For Bounded Arithmetic, Evan Goris
Tr-2005011: Logic Of Proofs For Bounded Arithmetic, Evan Goris
Computer Science Technical Reports
No abstract provided.
Tr-2005012: Propositional Games With Explicit Strategies, Bryan Renne
Tr-2005012: Propositional Games With Explicit Strategies, Bryan Renne
Computer Science Technical Reports
No abstract provided.
Tr-2005001: Automatic Target Detection In E3d Images Using Mathematical Morphology Techniques, Ilknur Icke, Jose Hanchi, Robert M. Haralick
Tr-2005001: Automatic Target Detection In E3d Images Using Mathematical Morphology Techniques, Ilknur Icke, Jose Hanchi, Robert M. Haralick
Computer Science Technical Reports
No abstract provided.