Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Conjunction, Disjunction and Iterated Conditioning of Conditional Events
2013
Starting from a recent paper by S. Kaufmann, we introduce a notion of conjunction of two conditional events and then we analyze it in the setting of coherence. We give a representation of the conjoined conditional and we show that this new object is a conditional random quantity, whose set of possible values normally contains the probabilities assessed for the two conditional events. We examine some cases of logical dependencies, where the conjunction is a conditional event; moreover, we give the lower and upper bounds on the conjunction. We also examine an apparent paradox concerning stochastic independence which can actually be explained in terms of uncorrelation. We briefly introduce the…
Parallel Collision Queries on the GPU
2013
We present parallel algorithms to accelerate collision tests of rigid body objects for a high number of independent transformations as they occur in sampling-based motion planning and path validation problems. We compare various GPU approaches with a different level of parallelism against each other and against a parallel CPU implementation. Our algorithms require no sophisticated load balancing schemes. They make no assumption on the distribution of the input transformations and require no pre-processing. Yet, we can perform up to 1 million collision tests per second with our best GPU implementation in our benchmarks. This is about 2.5X faster than our reference multi-core CPU implementati…
Top-k String Similarity Joins
2020
Top-k joins have been extensively studied in relational databases as ranking operations when every object has, among others, at least one ranking attribute. However, the focus has mostly been the case when the join attributes are of primitive data types (e.g., numerical values) and the join predicate is equality. In this work, we consider string objects assigned such ranking attributes or simply scores. Given two collection of string objects and a string similarity measure (e.g., the Edit distance), we introduce the top-k string similarity join () which returns k sufficiently similar pairs of objects with respect to a similarity threshold ϵ, which have the highest combined score computed by…
An Improved Receiver Architecture for Cyclic-Prefixed OFDM
2009
A novel Orthogonal Frequency Division Multiplexing receiver architecture to be employed with standard (e.g. Wireless LAN) transmitters is proposed. It features enhanced error-rate performance with flexible computational complexity and robustness to imperfect channel estimation. It is based on exploitation of the redundancy available in the cyclic prefix after cancellation of interference from the previous block. In order to show the effectiveness of our proposal, a number of comparisons to the standard per-subcarrier receiver and a previously existing method are reported.
A simple algorithm for drawing large graphs on small screens
1995
Viewing a large graph in limited display space has traditionally been accomplished using either reduced scale rendering of the graph or by attaching scrollbars to a view window which shows only a small portion of the entire graph. Recent work, however, has concentrated on integrating a locally detailed view with a globally scaled view. We present an algorithm for constructing a view which smoothly integrates local detail and global context in a single view window and describe user interaction with such a display.
Electronic properties of graphene: A learning path for undergraduate students
2016
The purpose of this work is to present a learning path aimed at deepening student understanding of the fundamental concepts underlying the electronic properties of new materials, graphene in particular. To achieve this task, we propose a five-week long workshop where students may be introduced to fundamental concepts of advanced physics, rarely used in learning paths, such as the symmetry properties of the crystal lattice, the group theory , the features of the free electron wave functions and energy levels, the relativistic Dirac equation. Particular emphasis is given to the manner of introducing these concepts, since an essential knowledge of solid state physics, quantum physics and relat…
Recursive modeling for completed code generation
2009
Model-Driven Development is promising to software development because it can reduce the complexity and cost of developing large software systems. The basic idea is the use of different kinds of models during the software development process, transformations between them, and automatic code generation at the end of the development. But unlike the structural parts, fully-automated code generation from the behavior parts is still hard, if it works at all, restricted to specific application areas using a domain specific language, DSL.This paper proposes an approach to model the behavior parts of a system and to embed them into the structural models. The underlying idea is recursive refinements …
GPU-accelerated exhaustive search for third-order epistatic interactions in case–control studies
2015
This is a post-peer-review, pre-copyedit version of an article published in Journal of Computational Science. The final authenticated version is available online at: https://doi.org/10.1016/j.jocs.2015.04.001 [Abstract] Interest in discovering combinations of genetic markers from case–control studies, such as Genome Wide Association Studies (GWAS), that are strongly associated to diseases has increased in recent years. Detecting epistasis, i.e. interactions among k markers (k ≥ 2), is an important but time consuming operation since statistical computations have to be performed for each k-tuple of measured markers. Efficient exhaustive methods have been proposed for k = 2, but exhaustive thi…
Challenges of Program Synthesis with Grammatical Evolution
2020
Program synthesis is an emerging research topic in the field of EC with the potential to improve real-world software development. Grammar-guided approaches like GE are suitable for program synthesis as they can express common programming languages with their required properties. This work uses common software metrics (lines of code, McCabe metric, size and depth of the abstract syntax tree) for an analysis of GE’s search behavior and the resulting problem structure. We find that GE is not able to solve program synthesis problems, where correct solutions have higher values of the McCabe metric (which means they require conditions or loops). Since small mutations of high-quality solutions str…
Artificial Intelligence + Distributed Systems = Agents
2009
The connection with Wirth’s book goes beyond the title, albeit confining the area to modern Artificial Intelligence (AI). Whereas thirty years ago, to devise effective programs, it became necessary to enhance the classical algorithmic framework with approaches applied to limited and focused subdomains, in the context of broad-band technology and semantic web, applications - running in open, heterogeneous, dynamic and uncertain environments-current paradigms are not enough, because of the shift from programs to processes. Beside the structure as position paper, to give more weight to some basic assertions, results of recent research are abridged and commented upon in line with new paradigms.…