title: Time and the Prisoner's Dilemma

abstract:
  This paper examines the integration of computational complexity into game
theoretic models. The example focused on is the Prisoner's Dilemma, repeated
for a finite length of time. We show that a minimal bound on the players'
computational ability is sufficient to enable cooperative behavior.
  In addition, a variant of the repeated Prisoner's Dilemma game is suggested,
in which players have the choice of opting out. This modification enriches the
game and suggests dominance of cooperative strategies.
  Competitive analysis is suggested as a tool for investigating sub-optimal
(but computationally tractable) strategies and game theoretic models in
general. Using competitive analysis, it is shown that for bounded players, a
sub-optimal strategy might be the optimal choice, given resource limitations.


title: Predicate Abstraction with Under-approximation Refinement

abstract:
  We propose an abstraction-based model checking method which relies on
refinement of an under-approximation of the feasible behaviors of the system
under analysis. The method preserves errors to safety properties, since all
analyzed behaviors are feasible by definition. The method does not require an
abstract transition relation to be generated, but instead executes the concrete
transitions while storing abstract versions of the concrete states, as
specified by a set of abstraction predicates. For each explored transition the
method checks, with the help of a theorem prover, whether there is any loss of
precision introduced by abstraction. The results of these checks are used to
decide termination or to refine the abstraction by generating new abstraction
predicates. If the (possibly infinite) concrete system under analysis has a
finite bisimulation quotient, then the method is guaranteed to eventually
explore an equivalent finite bisimilar structure. We illustrate the application
of the approach for checking concurrent programs.


title: The Fundamental Theorems of Interval Analysis

abstract:
  Expressions are not functions. Confusing the two concepts or failing to
define the function that is computed by an expression weakens the rigour of
interval arithmetic. We give such a definition and continue with the required
re-statements and proofs of the fundamental theorems of interval arithmetic and
interval analysis.
  Revision Feb. 10, 2009: added reference to and acknowledgement of P. Taylor.


title: Knowledge State Algorithms: Randomization with Limited Information

abstract:
  We introduce the concept of knowledge states; many well-known algorithms can
be viewed as knowledge state algorithms. The knowledge state approach can be
used to to construct competitive randomized online algorithms and study the
tradeoff between competitiveness and memory. A knowledge state simply states
conditional obligations of an adversary, by fixing a work function, and gives a
distribution for the algorithm. When a knowledge state algorithm receives a
request, it then calculates one or more "subsequent" knowledge states, together
with a probability of transition to each. The algorithm then uses randomization
to select one of those subsequents to be the new knowledge state. We apply the
method to the paging problem. We present optimally competitive algorithm for
paging for the cases where the cache sizes are k=2 and k=3. These algorithms
use only a very limited number of bookmarks.


title:
Dirac Notation, Fock Space and Riemann Metric Tensor in Information
  Retrieval Models

abstract:
  Using Dirac Notation as a powerful tool, we investigate the three classical
Information Retrieval (IR) models and some their extensions. We show that
almost all such models can be described by vectors in Occupation Number
Representations (ONR) of Fock spaces with various specifications on, e.g.,
occupation number, inner product or term-term interactions. As important cases
of study, Concept Fock Space (CFS) is introduced for Boolean model; the basic
formulas for Singular Value Decomposition (SVD) of Latent Semantic Indexing
(LSI) Model are manipulated in terms of Dirac notation. And, based on SVD, a
Riemannian metric tensor is introduced, which not only can be used to calculate
the relevance of documents to a query, but also may be used to measure the
closeness of documents in data clustering.


title: Trusted Ticket Systems and Applications

abstract:
  Trusted Computing is a security base technology that will perhaps be
ubiquitous in a few years in personal computers and mobile devices alike.
Despite its neutrality with respect to applications, it has raised some privacy
concerns. We show that trusted computing can be applied for service access
control in a manner protecting users' privacy. We construct a ticket system --
a concept which is at the heart of Identity Management -- relying solely on the
capabilities of the trusted platform module and the standards specified by the
Trusted Computing Group. Two examples show how it can be used for pseudonymous
and protected service access.


title: Non-Repudiation in Internet Telephony

abstract:
  We present a concept to achieve non-repudiation for natural language
conversations over the Internet. The method rests on chained electronic
signatures applied to pieces of packet-based, digital, voice communication. It
establishes the integrity and authenticity of the bidirectional data stream and
its temporal sequence and thus the security context of a conversation. The
concept is close to the protocols for Voice over the Internet (VoIP), provides
a high level of inherent security, and extends naturally to multilateral
non-repudiation, e.g., for conferences. Signatures over conversations can
become true declarations of will in analogy to electronically signed, digital
documents. This enables binding verbal contracts, in principle between
unacquainted speakers, and in particular without witnesses. A reference
implementation of a secure VoIP archive is exhibited.


title: State constraints and list decoding for the AVC

abstract:
  List decoding for arbitrarily varying channels (AVCs) under state constraints
is investigated. It is shown that rates within $\epsilon$ of the randomized
coding capacity of AVCs with input-dependent state can be achieved under
maximal error with list decoding using lists of size $O(1/\epsilon)$. Under
average error an achievable rate region and converse bound are given for lists
of size $L$. These bounds are based on two different notions of
symmetrizability and do not coincide in general. An example is given that shows
that for list size $L$ the capacity may be positive but strictly smaller than
the randomized coding capacity. This behavior is different than the situation
without state constraints.


title: A Generic Analysis Environment for Curry Programs

abstract:
  We present CurryBrowser, a generic analysis environment for the declarative
multi-paradigm language Curry. CurryBrowser supports browsing through the
program code of an application written in Curry, i.e., the main module and all
directly or indirectly imported modules. Each module can be shown in different
formats (e.g., source code, interface, intermediate code) and, inside each
module, various properties of functions defined in this module can be analyzed.
In order to support the integration of various program analyses, CurryBrowser
has a generic interface to connect local and global analyses implemented in
Curry. CurryBrowser is completely implemented in Curry using libraries for GUI
programming and meta-programming.


title:
Proceedings of the 16th Workshop in Logic-based Methods in Programming
  Environments (WLPE2006)

abstract:
  This volume contains the papers presented at WLPE'06: the 16th Workshop on
Logic-based Methods in Programming Environments held on August 16, 2006 in the
Seattle Sheraton Hotel and Towers, Seattle, Washington (USA). It was organised
as a satellite workshop of ICLP'06, the 22th International Conference on Logic
Programming.


title: Power-Bandwidth Tradeoff in Dense Multi-Antenna Relay Networks

abstract:
  We consider a dense fading multi-user network with multiple active
multi-antenna source-destination pair terminals communicating simultaneously
through a large common set of $K$ multi-antenna relay terminals in the full
spatial multiplexing mode. We use Shannon-theoretic tools to analyze the
tradeoff between energy efficiency and spectral efficiency (known as the power-
bandwidth tradeoff) in meaningful asymptotic regimes of signal-to-noise ratio
(SNR) and network size. We design linear distributed multi-antenna relay
beamforming (LDMRB) schemes that exploit the spatial signature of multi-user
interference and characterize their power-bandwidth tradeoff under a system
wide power constraint on source and relay transmissions. The impact of multiple
users, multiple relays and multiple antennas on the key performance measures of
the high and low SNR regimes is investigated in order to shed new light on the
possible reduction in power and bandwidth requirements through the usage of
such practical relay cooperation techniques. Our results indicate that
point-to-point coded multi-user networks supported by distributed relay
beamforming techniques yield enhanced energy efficiency and spectral
efficiency, and with appropriate signaling and sufficient antenna degrees of
freedom, can achieve asymptotically optimal power-bandwidth tradeoff with the
best possible (i.e., as in the cutset bound) energy scaling of $K^{-1}$ and the
best possible spectral efficiency slope at any SNR for large number of relay
terminals.


title: Contains and Inside relationships within combinatorial Pyramids

abstract:
  Irregular pyramids are made of a stack of successively reduced graphs
embedded in the plane. Such pyramids are used within the segmentation framework
to encode a hierarchy of partitions. The different graph models used within the
irregular pyramid framework encode different types of relationships between
regions. This paper compares different graph models used within the irregular
pyramid framework according to a set of relationships between regions. We also
define a new algorithm based on a pyramid of combinatorial maps which allows to
determine if one region contains the other using only local calculus.


title: Time- and Space-Efficient Evaluation of Some Hypergeometric Constants

abstract:
  The currently best known algorithms for the numerical evaluation of
hypergeometric constants such as $\zeta(3)$ to $d$ decimal digits have time
complexity $O(M(d) \log^2 d)$ and space complexity of $O(d \log d)$ or $O(d)$.
Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm
with the same asymptotic complexity, but more efficient in practice. Our
implementation of this algorithm improves slightly over existing programs for
the computation of $\pi$, and we announce a new record of 2 billion digits for
$\zeta(3)$.


title:
Characterization of Rate Region in Interference Channels with
  Constrained Power

abstract:
  In this paper, an $n$-user Gaussian interference channel, where the power of
the transmitters are subject to some upper-bounds is studied. We obtain a
closed-form expression for the rate region of such a channel based on the
Perron-Frobenius theorem. While the boundary of the rate region for the case of
unconstrained power is a well-established result, this is the first result for
the case of constrained power. We extend this result to the time-varying
channels and obtain a closed-form solution for the rate region of such
channels.


title: Online Bandwidth Allocation

abstract:
  The paper investigates a version of the resource allocation problem arising
in the wireless networking, namely in the OVSF code reallocation process. In
this setting a complete binary tree of a given height $n$ is considered,
together with a sequence of requests which have to be served in an online
manner. The requests are of two types: an insertion request requires to
allocate a complete subtree of a given height, and a deletion request frees a
given allocated subtree. In order to serve an insertion request it might be
necessary to move some already allocated subtrees to other locations in order
to free a large enough subtree. We are interested in the worst case average
number of such reallocations needed to serve a request.
  It was proved in previous work that the competitive ratio of the optimal
online algorithm solving this problem is between 1.5 and O(n). We partially
answer the question about its exact value by giving an O(1)-competitive online
algorithm.
  Same model has been used in the context of memory management systems, and
analyzed for the number of reallocations needed to serve a request in the worst
case. In this setting, our result is a corresponding amortized analysis.


title: Logic Meets Algebra: the Case of Regular Languages

abstract:
  The study of finite automata and regular languages is a privileged meeting
point of algebra and logic. Since the work of Buchi, regular languages have
been classified according to their descriptive complexity, i.e. the type of
logical formalism required to define them. The algebraic point of view on
automata is an essential complement of this classification: by providing
alternative, algebraic characterizations for the classes, it often yields the
only opportunity for the design of algorithms that decide expressibility in
some logical fragment.
  We survey the existing results relating the expressibility of regular
languages in logical fragments of MSO[S] with algebraic properties of their
minimal automata. In particular, we show that many of the best known results in
this area share the same underlying mechanics and rely on a very strong
relation between logical substitutions and block-products of pseudovarieties of
monoid. We also explain the impact of these connections on circuit complexity
theory.


title:
Data Cube: A Relational Aggregation Operator Generalizing Group-By,
  Cross-Tab, and Sub-Totals

abstract:
  Data analysis applications typically aggregate data across many dimensions
looking for anomalies or unusual patterns. The SQL aggregate functions and the
GROUP BY operator produce zero-dimensional or one-dimensional aggregates.
Applications need the N-dimensional generalization of these operators. This
paper defines that operator, called the data cube or simply cube. The cube
operator generalizes the histogram, cross-tabulation, roll-up, drill-down, and
sub-total constructs found in most report writers. The novelty is that cubes
are relations. Consequently, the cube operator can be imbedded in more complex
non-procedural data analysis programs. The cube operator treats each of the N
aggregation attributes as a dimension of N-space. The aggregate of a particular
set of attribute values is a point in this space. The set of points forms an
N-dimensional cube. Super-aggregates are computed by aggregating the N-cube to
lower dimensional spaces. This paper (1) explains the cube and roll-up
operators, (2) shows how they fit in SQL, (3) explains how users can define new
aggregate functions for cubes, and (4) discusses efficient techniques to
compute the cube. Many of these features are being added to the SQL Standard.


title: Data Management: Past, Present, and Future

abstract:
  Soon most information will be available at your fingertips, anytime,
anywhere. Rapid advances in storage, communications, and processing allow us
move all information into Cyberspace. Software to define, search, and visualize
online information is also a key to creating and accessing online information.
This article traces the evolution of data management systems and outlines
current trends. Data management systems began by automating traditional tasks:
recording transactions in business, science, and commerce. This data consisted
primarily of numbers and character strings. Today these systems provide the
infrastructure for much of our society, allowing fast, reliable, secure, and
automatic access to data distributed throughout the world. Increasingly these
systems automatically design and manage access to the data. The next steps are
to automate access to richer forms of data: images, sound, video, maps, and
other media. A second major challenge is automatically summarizing and
abstracting data in anticipation of user requests. These multi-media databases
and tools to access them will be a cornerstone of our move to Cyberspace.


title: A Critique of ANSI SQL Isolation Levels

abstract:
  ANSI SQL-92 defines Isolation Levels in terms of phenomena: Dirty Reads,
Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and
the ANSI SQL definitions fail to characterize several popular isolation levels,
including the standard locking implementations of the levels. Investigating the
ambiguities of the phenomena leads to clearer definitions; in addition new
phenomena that better characterize isolation types are introduced. An important
multiversion isolation type, Snapshot Isolation, is defined.


title: Queues Are Databases

abstract:
  Message-oriented-middleware (MOM) has become an small industry. MOM offers
queued transaction processing as an advance over pure client-server transaction
processing. This note makes four points: Queued transaction processing is less
general than direct transaction processing. Queued systems are built on top of
direct systems. You cannot build a direct system atop a queued system. It is
difficult to build direct, conversational, or distributed transactions atop a
queued system. Queues are interesting databases with interesting concurrency
control. It is best to build these mechanisms into a standard database system
so other applications can use these interesting features. Queue systems need
DBMS functionality. Queues need security, configuration, performance
monitoring, recovery, and reorganization utilities. Database systems already
have these features. A full-function MOM system duplicates these database
features. Queue managers are simple TP-monitors managing server pools driven by
queues. Database systems are encompassing many server pool features as they
evolve to TP-lite systems.


title:
Supporting Finite Element Analysis with a Relational Database Backend,
  Part I: There is Life beyond Files

abstract:
  In this paper, we show how to use a Relational Database Management System in
support of Finite Element Analysis. We believe it is a new way of thinking
about data management in well-understood applications to prepare them for two
major challenges, - size and integration (globalization). Neither extreme size
nor integration (with other applications over the Web) was a design concern 30
years ago when the paradigm for FEA implementation first was formed. On the
other hand, database technology has come a long way since its inception and it
is past time to highlight its usefulness to the field of scientific computing
and computer based engineering. This series aims to widen the list of
applications for database designers and for FEA users and application
developers to reap some of the benefits of database development.


title:
Supporting Finite Element Analysis with a Relational Database Backend,
  Part II: Database Design and Access

abstract:
  This is Part II of a three article series on using databases for Finite
Element Analysis (FEA). It discusses (1) db design, (2) data loading, (3)
typical use cases during grid building, (4) typical use cases during simulation
(get and put), (5) typical use cases during analysis (also done in Part III)
and some performance measures of these cases. It argues that using a database
is simpler to implement than custom data schemas, has better performance
because it can use data parallelism, and better supports FEA modularity and
tool evolution because database schema evolution, data independence, and
self-defining data.


title: Thousands of DebitCredit Transactions-Per-Second: Easy and Inexpensive

abstract:
  A $2k computer can execute about 8k transactions per second. This is 80x more
than one of the largest US bank's 1970's traffic - it approximates the total US
1970's financial transaction volume. Very modest modern computers can easily
solve yesterday's problems.


title: A Measure of Transaction Processing 20 Years Later

abstract:
  This provides a retrospective of the paper "A Measure of Transaction
Processing" published in 1985. It shows that transaction processing peak
performance and price-peformance have improved about 100,000x respectively and
that sort/sequential performance has approximately doubled each year (so a
million fold improvement) even though processor performance plateaued in 1995.


title:
Using Table Valued Functions in SQL Server 2005 To Implement a Spatial
  Data Library

abstract:
  This article explains how to add spatial search functions (point-near-point
and point in polygon) to Microsoft SQL Server 2005 using C# and table-valued
functions. It is possible to use this library to add spatial search to your
application without writing any special code. The library implements the
public-domain C# Hierarchical Triangular Mesh (HTM) algorithms from Johns
Hopkins University. That C# library is connected to SQL Server 2005 via a set
of scalar-valued and table-valued functions. These functions act as a spatial
index.


title: Indexing the Sphere with the Hierarchical Triangular Mesh

abstract:
  We describe a method to subdivide the surface of a sphere into spherical
triangles of similar, but not identical, shapes and sizes. The Hierarchical
Triangular Mesh (HTM) is a quad-tree that is particularly good at supporting
searches at different resolutions, from arc seconds to hemispheres. The
subdivision scheme is universal, providing the basis for addressing and for
fast lookups. The HTM provides the basis for an efficient geospatial indexing
scheme in relational databases where the data have an inherent location on
either the celestial sphere or the Earth. The HTM index is superior to
cartographical methods using coordinates with singularities at the poles. We
also describe a way to specify surface regions that efficiently represent
spherical query areas. This article presents the algorithms used to identify
the HTM triangles covering such regions.


title: Petascale Computational Systems

abstract:
  Computational science is changing to be data intensive. Super-Computers must
be balanced systems; not just CPU farms but also petascale IO and networking
arrays. Anyone building CyberInfrastructure should allocate resources to
support a balanced Tier-1 through Tier-3 design.


title: Empirical Measurements of Disk Failure Rates and Error Rates

abstract:
  The SATA advertised bit error rate of one error in 10 terabytes is
frightening. We moved 2 PB through low-cost hardware and saw five disk read
error events, several controller failures, and many system reboots caused by
security patches. We conclude that SATA uncorrectable read errors are not yet a
dominant system-fault source - they happen, but are rare compared to other
problems. We also conclude that UER (uncorrectable error rate) is not the
relevant metric for our needs. When an uncorrectable read error happens, there
are typically several damaged storage blocks (and many uncorrectable read
errors.) Also, some uncorrectable read errors may be masked by the operating
system. The more meaningful metric for data architects is Mean Time To Data
Loss (MTTDL.)


title: Large-Scale Query and XMatch, Entering the Parallel Zone

abstract:
  Current and future astronomical surveys are producing catalogs with millions
and billions of objects. On-line access to such big datasets for data mining
and cross-correlation is usually as highly desired as unfeasible. Providing
these capabilities is becoming critical for the Virtual Observatory framework.
In this paper we present various performance tests that show how using
Relational Database Management Systems (RDBMS) and a Zoning algorithm to
partition and parallelize the computation, we can facilitate large-scale query
and cross-match.


title:
To BLOB or Not To BLOB: Large Object Storage in a Database or a
  Filesystem?

abstract:
  Application designers often face the question of whether to store large
objects in a filesystem or in a database. Often this decision is made for
application design simplicity. Sometimes, performance measurements are also
used. This paper looks at the question of fragmentation - one of the
operational issues that can affect the performance and/or manageability of the
system as deployed long term. As expected from the common wisdom, objects
smaller than 256KB are best stored in a database while objects larger than 1M
are best stored in the filesystem. Between 256KB and 1MB, the read:write ratio
and rate of object overwrite or replacement are important factors. We used the
notion of "storage age" or number of object overwrites as way of normalizing
wall clock time. Storage age allows our results or similar such results to be
applied across a number of read:write ratios and object replacement rates.


title:
A Framework for Designing MIMO systems with Decision Feedback
  Equalization or Tomlinson-Harashima Precoding

abstract:
  We consider joint transceiver design for general Multiple-Input
Multiple-Output communication systems that implement interference
(pre-)subtraction, such as those based on Decision Feedback Equalization (DFE)
or Tomlinson-Harashima precoding (THP). We develop a unified framework for
joint transceiver design by considering design criteria that are expressed as
functions of the Mean Square Error (MSE) of the individual data streams. By
deriving two inequalities that involve the logarithms of the individual MSEs,
we obtain optimal designs for two classes of communication objectives, namely
those that are Schur-convex and Schur-concave functions of these logarithms.
For Schur-convex objectives, the optimal design results in data streams with
equal MSEs. This design simultaneously minimizes the total MSE and maximizes
the mutual information for the DFE-based model. For Schur-concave objectives,
the optimal DFE design results in linear equalization and the optimal THP
design results in linear precoding. The proposed framework embraces a wide
range of design objectives and can be regarded as a counterpart of the existing
framework of linear transceiver design.


title:
Life Under Your Feet: An End-to-End Soil Ecology Sensor Network,
  Database, Web Server, and Analysis Service

abstract:
  Wireless sensor networks can revolutionize soil ecology by providing
measurements at temporal and spatial granularities previously impossible. This
paper presents a soil monitoring system we developed and deployed at an urban
forest in Baltimore as a first step towards realizing this vision. Motes in
this network measure and save soil moisture and temperature in situ every
minute. Raw measurements are periodically retrieved by a sensor gateway and
stored in a central database where calibrated versions are derived and stored.
The measurement database is published through Web Services interfaces. In
addition, analysis tools let scientists analyze current and historical data and
help manage the sensor network. The article describes the system design, what
we learned from the deployment, and initial results obtained from the sensors.
The system measures soil factors with unprecedented temporal precision.
However, the deployment required device-level programming, sensor calibration
across space and time, and cross-referencing measurements with external
sources. The database, web server, and data analysis design required
considerable innovation and expertise. So, the ratio of computer-scientists to
ecologists was 3:1. Before sensor networks can fulfill their potential as
instruments that can be easily deployed by scientists, these technical problems
must be addressed so that the ratio is one nerd per ten ecologists.


title:
The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching
  Spatial Datasets

abstract:
  Zones index an N-dimensional Euclidian or metric space to efficiently support
points-near-a-point queries either within a dataset or between two datasets.
The approach uses relational algebra and the B-Tree mechanism found in almost
all relational database systems. Hence, the Zones Algorithm gives a
portable-relational implementation of points-near-point, spatial cross-match,
and self-match queries. This article corrects some mistakes in an earlier
article we wrote on the Zones Algorithm and describes some algorithmic
improvements. The Appendix includes an implementation of point-near-point,
self-match, and cross-match using the USGS city and stream gauge database.


abstract:
  Cross-match spatially clusters and organizes several astronomical
point-source measurements from one or more surveys. Ideally, each object would
be found in each survey. Unfortunately, the observation conditions and the
objects themselves change continually. Even some stationary objects are missing
in some observations; sometimes objects have a variable light flux and
sometimes the seeing is worse. In most cases we are faced with a substantial
number of differences in object detections between surveys and between
observations taken at different times within the same survey or instrument.
Dealing with such missing observations is a difficult problem. The first step
is to classify misses as ephemeral - when the object moved or simply
disappeared, masked - when noise hid or corrupted the object observation, or
edge - when the object was near the edge of the observational field. This
classification and a spatial library to represent and manipulate observational
footprints help construct a Match table recording both hits and misses.
Transitive closure clusters friends-of-friends into object bundles. The bundle
summary statistics are recorded in a Bundle table. This design is an evolution
of the Sloan Digital Sky Survey cross-match design that compared overlapping
observations taken at different times. Cross-Matching Multiple Spatial
Observations and Dealing with Missing Data.


title: SkyServer Traffic Report - The First Five Years

abstract:
  The SkyServer is an Internet portal to the Sloan Digital Sky Survey Catalog
Archive Server. From 2001 to 2006, there were a million visitors in 3 million
sessions generating 170 million Web hits, 16 million ad-hoc SQL queries, and 62
million page views. The site currently averages 35 thousand visitors and 400
thousand sessions per month. The Web and SQL logs are public. We analyzed
traffic and sessions by duration, usage pattern, data product, and client type
(mortal or bot) over time. The analysis shows (1) the site's popularity, (2)
the educational website that delivered nearly fifty thousand hours of
interactive instruction, (3) the relative use of interactive, programmatic, and
batch-local access, (4) the success of offering ad-hoc SQL, personal database,
and batch job access to scientists as part of the data publication, (5) the
continuing interest in "old" datasets, (6) the usage of SQL constructs, and (7)
a novel approach of using the corpus of correct SQL queries to suggest similar
but correct statements when a user presents an incorrect SQL statement.


title:
A Prototype for Educational Planning Using Course Constraints to
  Simulate Student Populations

abstract:
  Distance learning universities usually afford their students the flexibility
to advance their studies at their own pace. This can lead to a considerable
fluctuation of student populations within a program's courses, possibly
affecting the academic viability of a program as well as the related required
resources. Providing a method that estimates this population could be of
substantial help to university management and academic personnel. We describe
how to use course precedence constraints to calculate alternative tuition paths
and then use Markov models to estimate future populations. In doing so, we
identify key issues of a large scale potential deployment.


title:
On the Software and Knowledge Engineering Aspects of the Educational
  Process

abstract:
  The Hellenic Open University has embarked on a large-scale effort to enhance
its textbook-based material with content that demonstrably supports the basic
tenets of distance learning. The challenge is to set up a framework that allows
for the production-level creation, distribution and consumption of content, and
at the same time, evaluate the effort in terms of technological, educational
and organizational knowledge gained. This paper presents a model of the
educational process that is used as a development backbone and argues about its
conceptual and technical practicality at large.


title: Towards Practical Typechecking for Macro Tree Transducers

abstract:
  Macro tree transducers (mtt) are an important model that both covers many
useful XML transformations and allows decidable exact typechecking. This paper
reports our first step toward an implementation of mtt typechecker that has a
practical efficiency. Our approach is to represent an input type obtained from
a backward inference as an alternating tree automaton, in a style similar to
Tozawa's XSLT0 typechecking. In this approach, typechecking reduces to checking
emptiness of an alternating tree automaton. We propose several optimizations
(Cartesian factorization, state partitioning) on the backward inference process
in order to produce much smaller alternating tree automata than the naive
algorithm, and we present our efficient algorithm for checking emptiness of
alternating tree automata, where we exploit the explicit representation of
alternation for local optimizations. Our preliminary experiments confirm that
our algorithm has a practical performance that can typecheck simple
transformations with respect to the full XHTML in a reasonable time.


title:
Pitch Tracking of Acoustic Signals based on Average Squared Mean
  Difference Function

abstract:
  In this paper, a method of pitch tracking based on variance minimization of
locally periodic subsamples of an acoustic signal is presented. Replicates
along the length of the periodically sampled data of the signal vector are
taken and locally averaged sample variances are minimized to estimate the
fundamental frequency. Using this method, pitch tracking of any text
independent voiced signal is possible for different speakers.


title: Distributed Detection in Sensor Networks with Limited Range Sensors

abstract:
  We consider a multi-object detection problem over a sensor network (SNET)
with limited range sensors. This problem complements the widely considered
decentralized detection problem where all sensors observe the same object.
While the necessity for global collaboration is clear in the decentralized
detection problem, the benefits of collaboration with limited range sensors is
unclear and has not been widely explored. In this paper we develop a
distributed detection approach based on recent development of the false
discovery rate (FDR). We first extend the FDR procedure and develop a
transformation that exploits complete or partial knowledge of either the
observed distributions at each sensor or the ensemble (mixture) distribution
across all sensors. We then show that this transformation applies to
multi-dimensional observations, thus extending FDR to multi-dimensional
settings. We also extend FDR theory to cases where distributions under both
null and positive hypotheses are uncertain. We then propose a robust
distributed algorithm to perform detection. We further demonstrate scalability
to large SNETs by showing that the upper bound on the communication complexity
scales linearly with the number of sensors that are in the vicinity of objects
and is independent of the total number of sensors. Finally, we deal with
situations where the sensing model may be uncertain and establish robustness of
our techniques to such uncertainties.


title: Scatter of Weak Robots

abstract:
  In this paper, we first formalize the problem to be solved, i.e., the Scatter
Problem (SP). We then show that SP cannot be deterministically solved. Next, we
propose a randomized algorithm for this problem. The proposed solution is
trivially self-stabilizing. We then show how to design a self-stabilizing
version of any deterministic solution for the Pattern Formation and the
Gathering problems.


title: Ontology from Local Hierarchical Structure in Text

abstract:
  We study the notion of hierarchy in the context of visualizing textual data
and navigating text collections. A formal framework for ``hierarchy'' is given
by an ultrametric topology. This provides us with a theoretical foundation for
concept hierarchy creation. A major objective is {\em scalable} annotation or
labeling of concept maps. Serendipitously we pursue other objectives such as
deriving common word pair (and triplet) phrases, i.e., word 2- and 3-grams. We
evaluate our approach using (i) a collection of texts, (ii) a single text
subdivided into successive parts (for which we provide an interactive
demonstrator), and (iii) a text subdivided at the sentence or line level. While
detailing a generic framework, a distinguishing feature of our work is that we
focus on {\em locality} of hierarchic structure in order to extract semantic
information.


title: A Note on Local Ultrametricity in Text

abstract:
  High dimensional, sparsely populated data spaces have been characterized in
terms of ultrametric topology. This implies that there are natural, not
necessarily unique, tree or hierarchy structures defined by the ultrametric
topology. In this note we study the extent of local ultrametric topology in
texts, with the aim of finding unique ``fingerprints'' for a text or corpus,
discriminating between texts from different domains, and opening up the
possibility of exploiting hierarchical structures in the data. We use coherent
and meaningful collections of over 1000 texts, comprising over 1.3 million
words.


title:
Supplement to: Code Spectrum and Reliability Function: Binary Symmetric
  Channel

abstract:
  A much simpler proof of Theorem 1 from M.Burnashev "Code spectrum and
reliability function: Binary symmetric channel" is presented.


title: Certification of the QR factor R, and of lattice basis reducedness

abstract:
  Given a lattice basis of n vectors in Z^n, we propose an algorithm using
12n^3+O(n^2) floating point operations for checking whether the basis is
LLL-reduced. If the basis is reduced then the algorithm will hopefully answer
''yes''. If the basis is not reduced, or if the precision used is not
sufficient with respect to n, and to the numerical properties of the basis, the
algorithm will answer ''failed''. Hence a positive answer is a rigorous
certificate. For implementing the certificate itself, we propose a floating
point algorithm for computing (certified) error bounds for the entries of the R
factor of the QR matrix factorization. This algorithm takes into account all
possible approximation and rounding errors. The cost 12n^3+O(n^2) of the
certificate is only six times more than the cost of numerical algorithms for
computing the QR factorization itself, and the certificate may be implemented
using matrix library routines only. We report experiments that show that for a
reduced basis of adequate dimension and quality the certificate succeeds, and
establish the effectiveness of the certificate. This effectiveness is applied
for certifying the output of fastest existing floating point heuristics of LLL
reduction, without slowing down the whole process.


title:
Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in<br>
  SAT-Based Planning

abstract:
  In Verification and in (optimal) AI Planning, a successful method is to
formulate the application as boolean satisfiability (SAT), and solve it with
state-of-the-art DPLL-based procedures. There is a lack of understanding of why
this works so well. Focussing on the Planning context, we identify a form of
problem structure concerned with the symmetrical or asymmetrical nature of the
cost of achieving the individual planning goals. We quantify this sort of
structure with a simple numeric parameter called AsymRatio, ranging between 0
and 1. We run experiments in 10 benchmark domains from the International
Planning Competitions since 2000; we show that AsymRatio is a good indicator of
SAT solver performance in 8 of these domains. We then examine carefully crafted
synthetic planning domains that allow control of the amount of structure, and
that are clean enough for a rigorous analysis of the combinatorial search
space. The domains are parameterized by size, and by the amount of structure.
The CNFs we examine are unsatisfiable, encoding one planning step less than the
length of the optimal plan. We prove upper and lower bounds on the size of the
best possible DPLL refutations, under different settings of the amount of
structure, as a function of size. We also identify the best possible sets of
branching variables (backdoors). With minimum AsymRatio, we prove exponential
lower bounds, and identify minimal backdoors of size linear in the number of
variables. With maximum AsymRatio, we identify logarithmic DPLL refutations
(and backdoors), showing a doubly exponential gap between the two structural
extreme cases. The reasons for this behavior -- the proof arguments --
illuminate the prototypical patterns of structure causing the empirical
behavior observed in the competition benchmarks.


title: Graph Operations on Clique-Width Bounded Graphs

abstract:
  Clique-width is a well-known graph parameter. Many NP-hard graph problems
admit polynomial-time solutions when restricted to graphs of bounded
clique-width. The same holds for NLC-width. In this paper we study the behavior
of clique-width and NLC-width under various graph operations and graph
transformations. We give upper and lower bounds for the clique-width and
NLC-width of the modified graphs in terms of the clique-width and NLC-width of
the involved graphs.


title: Certification of bounds on expressions involving rounded operators

abstract:
  Gappa uses interval arithmetic to certify bounds on mathematical expressions
that involve rounded as well as exact operators. Gappa generates a theorem with
its proof for each bound treated. The proof can be checked with a higher order
logic automatic proof checker, either Coq or HOL Light, and we have developed a
large companion library of verified facts for Coq dealing with the addition,
multiplication, division, and square root, in fixed- and floating-point
arithmetics. Gappa uses multiple-precision dyadic fractions for the endpoints
of intervals and performs forward error analysis on rounded operators when
necessary. When asked, Gappa reports the best bounds it is able to reach for a
given expression in a given context. This feature is used to quickly obtain
coarse bounds. It can also be used to identify where the set of facts and
automatic techniques implemented in Gappa becomes insufficient. Gappa handles
seamlessly additional properties expressed as interval properties or rewriting
rules in order to establish more intricate bounds. Recent work showed that
Gappa is perfectly suited to the proof of correctness of small pieces of
software. Proof obligations can be written by designers, produced by
third-party tools or obtained by overloading arithmetic operators.


title: Verification Across Intellectual Property Boundaries

abstract:
  In many industries, the importance of software components provided by
third-party suppliers is steadily increasing. As the suppliers seek to secure
their intellectual property (IP) rights, the customer usually has no direct
access to the suppliers' source code, and is able to enforce the use of
verification tools only by legal requirements. In turn, the supplier has no
means to convince the customer about successful verification without revealing
the source code. This paper presents an approach to resolve the conflict
between the IP interests of the supplier and the quality interests of the
customer. We introduce a protocol in which a dedicated server (called the
"amanat") is controlled by both parties: the customer controls the verification
task performed by the amanat, while the supplier controls the communication
channels of the amanat to ensure that the amanat does not leak information
about the source code. We argue that the protocol is both practically useful
and mathematically sound. As the protocol is based on well-known (and
relatively lightweight) cryptographic primitives, it allows a straightforward
implementation on top of existing verification tool chains. To substantiate our
security claims, we establish the correctness of the protocol by cryptographic
reduction proofs.


title:
Faster Inversion and Other Black Box Matrix Computations Using Efficient
  Block Projections

abstract:
  Block projections have been used, in [Eberly et al. 2006], to obtain an
efficient algorithm to find solutions for sparse systems of linear equations. A
bound of softO(n^(2.5)) machine operations is obtained assuming that the input
matrix can be multiplied by a vector with constant-sized entries in softO(n)
machine operations. Unfortunately, the correctness of this algorithm depends on
the existence of efficient block projections, and this has been conjectured. In
this paper we establish the correctness of the algorithm from [Eberly et al.
2006] by proving the existence of efficient block projections over sufficiently
large fields. We demonstrate the usefulness of these projections by deriving
improved bounds for the cost of several matrix problems, considering, in
particular, ``sparse'' matrices that can be be multiplied by a vector using
softO(n) field operations. We show how to compute the inverse of a sparse
matrix over a field F using an expected number of softO(n^(2.27)) operations in
F. A basis for the null space of a sparse matrix, and a certification of its
rank, are obtained at the same cost. An application to Kaltofen and Villard's
Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an
integer matrix yields algorithms requiring softO(n^(2.66)) machine operations.
The derived algorithms are all probabilistic of the Las Vegas type.


title: A New Self-Stabilizing Maximal Matching Algorithm

abstract:
  The maximal matching problem has received considerable attention in the
self-stabilizing community. Previous work has given different self-stabilizing
algorithms that solves the problem for both the adversarial and fair
distributed daemon, the sequential adversarial daemon, as well as the
synchronous daemon. In the following we present a single self-stabilizing
algorithm for this problem that unites all of these algorithms in that it
stabilizes in the same number of moves as the previous best algorithms for the
sequential adversarial, the distributed fair, and the synchronous daemon. In
addition, the algorithm improves the previous best moves complexities for the
distributed adversarial daemon from O(n^2) and O(delta m) to O(m) where n is
the number of processes, m is thenumber of edges, and delta is the maximum
degree in the graph.


title:
A Peer-to-Peer Browsable File Index using a Popularity Based Global
  Namespace

abstract:
  The distribution of files using decentralized, peer-to-peer (P2P) systems,
has significant advantages over centralized approaches. It is however more
difficult to settle on the best approach for file sharing. Most file sharing
systems are based on query string searches, leading to a relatively simple but
inefficient broadcast or to an efficient but relatively complicated index in a
structured environment. In this paper we use a browsable peer-to-peer file
index consisting of files which serve as directory nodes, interconnecting to
form a directory network. We implemented the system based on BitTorrent and
Kademlia. The directory network inherits all of the advantages of
decentralization and provides browsable, efficient searching. To avoid conflict
between users in the P2P system while also imposing no additional restrictions,
we allow multiple versions of each directory node to simultaneously exist --
using popularity as the basis for default browsing behavior. Users can freely
add files and directory nodes to the network. We show, using a simulation of
user behavior and file quality, that the popularity based system consistently
leads users to a high quality directory network; above the average quality of
user updates. Q


title: The parallel implementation of the Astr\'{e}e static analyzer

abstract:
  The Astr\'{e}e static analyzer is a specialized tool that can prove the
absence of runtime errors, including arithmetic overflows, in large critical
programs. Keeping analysis times reasonable for industrial use is one of the
design objectives. In this paper, we discuss the parallel implementation of the
analysis.


title: The pitfalls of verifying floating-point computations

abstract:
  Current critical systems commonly use a lot of floating-point computations,
and thus the testing or static analysis of programs containing floating-point
operators has become a priority. However, correctly defining the semantics of
common implementations of floating-point is tricky, because semantics may
change with many factors beyond source-code level, such as choices made by
compilers. We here give concrete examples of problems that can appear and
solutions to implement in analysis software.


title: A Static Analyzer for Large Safety-Critical Software

abstract:
  We show that abstract interpretation-based static program analysis can be
made efficient and precise enough to formally verify a class of properties for
a family of large programs with few or no false alarms. This is achieved by
refinement of a general purpose static analyzer and later adaptation to
particular programs of the family by the end-user through parametrization. This
is applied to the proof of soundness of data manipulation operations at the
machine level for periodic synchronous safety critical embedded software. The
main novelties are the design principle of static analyzers by refinement and
adaptation through parametrization, the symbolic manipulation of expressions to
improve the precision of abstract transfer functions, the octagon, ellipsoid,
and decision tree abstract domains, all with sound handling of rounding errors
in floating point computations, widening strategies (with thresholds, delayed)
and the automatic determination of the parameters (parametrized packing).


title: Menzerath-Altmann Law for Syntactic Structures in Ukrainian

abstract:
  In the paper, the definition of clause suitable for an automated processing
of a Ukrainian text is proposed. The Menzerath-Altmann law is verified on the
sentence level and the parameters for the dependences of the clause length
counted in words and syllables on the sentence length counted in clauses are
calculated for "Perekhresni Stezhky" ("The Cross-Paths"), a novel by Ivan
Franko.


title:
An Abstract Monte-Carlo Method for the Analysis of Probabilistic
  Programs

abstract:
  We introduce a new method, combination of random testing and abstract
interpretation, for the analysis of programs featuring both probabilistic and
non-probabilistic nondeterminism. After introducing "ordinary" testing, we show
how to combine testing and abstract interpretation and give formulas linking
the precision of the results to the number of iterations. We then discuss
complexity and optimization issues and end with some experimental results.


title:
One-bit Distributed Sensing and Coding for Field Estimation in Sensor
  Networks

abstract:
  This paper formulates and studies a general distributed field reconstruction
problem using a dense network of noisy one-bit randomized scalar quantizers in
the presence of additive observation noise of unknown distribution. A
constructive quantization, coding, and field reconstruction scheme is developed
and an upper-bound to the associated mean squared error (MSE) at any point and
any snapshot is derived in terms of the local spatio-temporal smoothness
properties of the underlying field. It is shown that when the noise, sensor
placement pattern, and the sensor schedule satisfy certain weak technical
requirements, it is possible to drive the MSE to zero with increasing sensor
density at points of field continuity while ensuring that the per-sensor
bitrate and sensing-related network overhead rate simultaneously go to zero.
The proposed scheme achieves the order-optimal MSE versus sensor density
scaling behavior for the class of spatially constant spatio-temporal fields.


title: On Delayed Sequential Coding of Correlated Sources

abstract:
  Motivated by video coding applications, the problem of sequential coding of
correlated sources with encoding and/or decoding frame-delays is studied. The
fundamental tradeoffs between individual frame rates, individual frame
distortions, and encoding/decoding frame-delays are derived in terms of a
single-letter information-theoretic characterization of the rate-distortion
region for general inter-frame source correlations and certain types of
potentially frame specific and coupled single-letter fidelity criteria. The
sum-rate-distortion region is characterized in terms of generalized directed
information measures highlighting their role in delayed sequential source
coding problems. For video sources which are spatially stationary memoryless
and temporally Gauss-Markov, MSE frame distortions, and a sum-rate constraint,
our results expose the optimality of idealized differential predictive coding
among all causal sequential coders, when the encoder uses a positive rate to
describe each frame. Somewhat surprisingly, causal sequential encoding with
one-frame-delayed noncausal sequential decoding can exactly match the
sum-rate-MSE performance of joint coding for all nontrivial MSE-tuples
satisfying certain positive semi-definiteness conditions. Thus, even a single
frame-delay holds potential for yielding significant performance improvements.
Generalizations to higher order Markov sources are also presented and
discussed. A rate-distortion performance equivalence between, causal sequential
encoding with delayed noncausal sequential decoding, and, delayed noncausal
sequential encoding with causal sequential decoding, is also established.


title: Fitting the WHOIS Internet data

abstract:
  We consider the RIPE WHOIS Internet data as characterized by the Cooperative
Association for Internet Data Analysis (CAIDA), and show that the Tempered
Preferential Attachment model [1] provides an excellent fit to this data.
  [1] D'Souza, Borgs, Chayes, Berger and Kleinberg, to appear PNAS USA, 2007.


title: A Virtual Logo Keyboard for People with Motor Disabilities

abstract:
  In our society, people with motor impairments are oftentimes socially
excluded from their environment. This is unfortunate because every human being
should have the possibility to obtain the necessary conditions to live a normal
life. Although there is technology to assist people with motor impairments, few
systems are targeted for programming environments. We have created a system,
called Logo Keyboard, to assist people with motor disabilities to program with
the Logo programming language. With this special keyboard we can help more
people to get involved into computer programming and to develop projects in
different areas.


title: Reasoning from a schema and from an analog in software code reuse

abstract:
  The activity of design involves the decomposition of problems into
subproblems and the development and evaluation of solutions. In many cases,
solution development is not done from scratch. Designers often evoke and adapt
solutions developed in the past. These solutions may come from an internal
source, i.e. the memory of the designers, and/or from an external source. The
goal of this paper is to analyse the characteristics of the cognitive
mechanisms, the knowledge and the representations involved in the code reuse
activity performed by experienced programmers. More generally, the focus is the
control structure of the reuse activity. Data collected in an experiment in
which programmers had to design programs are analyzed. Two code reuse
situations are distinguished depending on whether or not the processes involved
in reuse start before the elaboration of what acts as a source-solution. Our
analysis highlights the use of reasoning from a schema and from an analog in
the code reuse activity.


title: Measuring Cognitive Activities in Software Engineering

abstract:
  This paper presents an approach to the study of cognitive activities in
collaborative software development. This approach has been developed by a
multidisciplinary team made up of software engineers and cognitive
psychologists. The basis of this approach is to improve our understanding of
software development by observing professionals at work. The goal is to derive
lines of conduct or good practices based on observations and analyses of the
processes that are naturally used by software engineers. The strategy involved
is derived from a standard approach in cognitive science. It is based on the
videotaping of the activities of software engineers, transcription of the
videos, coding of the transcription, defining categories from the coded
episodes and defining cognitive behaviors or dialogs from the categories. This
project presents two original contributions that make this approach generic in
software engineering. The first contribution is the introduction of a formal
hierarchical coding scheme, which will enable comparison of various types of
observations. The second is the merging of psychological and statistical
analysis approaches to build a cognitive model. The details of this new
approach are illustrated with the initial data obtained from the analysis of
technical review meetings.


title:
The Effect of Object-Oriented Programming Expertise in Several
  Dimensions of Comprehension Strategies

abstract:
  This study analyzes object-oriented (OO) program comprehension by experts and
novices. We examine the effect of expertise in three dimensions of
comprehension strategies: the scope of the comprehension, the top-down versus
bottom-up direction of the processes, and the guidance of the comprehension
activity. Overall, subjects were similar in the scope of their comprehension,
although the experts tended to consult more files. We found strong evidence of
top-down, inference-driven behaviors, as well as multiple guidance in expert
comprehension. We also found evidence of execution-based guidance and less use
of top-down processes in novice comprehension. Guidance by inheritance and
composition relationships in the OO program was not dominant, but nevertheless
played a substantial role in expert program comprehension. However, these
static relationships more closely tied to the OO nature of the program were
exploited poorly by novices. To conclude, these results are discussed with
respect to the literature on procedural program comprehension.


title: Expert Programming Knowledge: a Schema-Based Approach

abstract:
  The topic of this chapter is the role of expert programming knowledge in the
understanding activity. In the "schema-based approach", the role of semantic
structures is emphasized whereas, in the "control-flow approach", the role of
syntactic structures is emphasized. Data which support schema-based models of
understanding are presented. Data which are more consistent with the
"control-flow approach" allow to discuss the limits of the former kind of
models.


title: What model(s) for program understanding?

abstract:
  The first objective of this paper is to present and discuss various types of
models of program understanding. They are discussed in relation to models of
text understanding. The second objective of this paper is to assess the effect
of purpose for reading, or more specifically programming task, on the cognitive
processes involved and representations constructed in program understanding.
This is done in the theoretical framework of van Dijk and Kintsch's model of
text understanding (1983).


title:
An empirical study of software reuse by experts in object-oriented
  design

abstract:
  This paper presents an empirical study of the software reuse activity by
expert designers in the context of object-oriented design. Our study focuses on
the three following aspects of reuse : (1) the interaction between some design
processes, e.g. constructing a problem representation, searching for and
evaluating solutions, and reuse processes, i.e. retrieving and using previous
solutions, (2) the mental processes involved in reuse, e.g. example-based
retrieval or bottom-up versus top-down expanding of the solution, and (3) the
mental representations constructed throughout the reuse activity, e.g. dynamic
versus static representations. Some implications of these results for the
specification of software reuse support environments are discussed.


title:
Negotiation in collaborative assessment of design solutions: an
  empirical study on a Concurrent Engineering process

abstract:
  In Concurrent engineering, design solutions are not only produced by
individuals specialized in a given field. Due to the team nature of the design
activity, solutions are negotiated. Our objective is to analyse the
argumentation processes leading to these negotiated solutions. These processes
take place in the meetings which group together specialists with a co-design
aim. We conducted cognitive ergonomics research work during the definition
phase of an aeronautical design project in which the participants work in
Concurrent Engineering. We recorded, retranscribed and analysed 7
multi-speciality meetings. These meetings were organised, as needed, to assess
the integration of the solutions of each speciality into a global solution. We
found that there are three main design proposal assessment modes which can be
combined in these meetings: (a) analytical assessment mode, (b) comparative
assessment mode (c) analogical assessment mode. Within these assessment modes,
different types of arguments are used. Furthermore we found a typical temporal
negotiation process.


title:
Power Optimal Scheduling for Guaranteed Throughput in Multi-access
  Fading Channels

abstract:
  A power optimal scheduling algorithm that guarantees desired throughput and
bounded delay to each user is developed for fading multi-access multi-band
systems. The optimization is over the joint space of all rate allocation and
coding strategies. The proposed scheduling assigns rates on each band based
only on the current system state, and subsequently uses optimal multi-user
signaling to achieve these rates. The scheduling is computationally simple, and
hence scalable. Due to uplink-downlink duality, all the results extend in
straightforward fashion to the broadcast channels.


title: MMSE Optimal Algebraic Space-Time Codes

abstract:
  Design of Space-Time Block Codes (STBCs) for Maximum Likelihood (ML)
reception has been predominantly the main focus of researchers. However, the ML
decoding complexity of STBCs becomes prohibitive large as the number of
transmit and receive antennas increase. Hence it is natural to resort to a
suboptimal reception technique like linear Minimum Mean Squared Error (MMSE)
receiver. Barbarossa et al and Liu et al have independently derived necessary
and sufficient conditions for a full rate linear STBC to be MMSE optimal, i.e
achieve least Symbol Error Rate (SER). Motivated by this problem, certain
existing high rate STBC constructions from crossed product algebras are
identified to be MMSE optimal. Also, it is shown that a certain class of codes
from cyclic division algebras which are special cases of crossed product
algebras are MMSE optimal. Hence, these STBCs achieve least SER when MMSE
reception is employed and are fully diverse when ML reception is employed.


title:
On Evaluating the Rate-Distortion Function of Sources with Feed-Forward
  and the Capacity of Channels with Feedback

abstract:
  We study the problem of computing the rate-distortion function for sources
with feed-forward and the capacity for channels with feedback. The formulas
(involving directed information) for the optimal rate-distortion function with
feed-forward and channel capacity with feedback are multi-letter expressions
and cannot be computed easily in general. In this work, we derive conditions
under which these can be computed for a large class of sources/channels with
memory and distortion/cost measures. Illustrative examples are also provided.


title: A canonical form for some piecewise defined functions

abstract:
  We define a canonical form for piecewise defined functions. We show that this
has a wider range of application as well as better complexity properties than
previous work.


title: Dealing With Logical Omniscience: Expressiveness and Pragmatics

abstract:
  We examine four approaches for dealing with the logical omniscience problem
and their potential applicability: the syntactic approach, awareness,
algorithmic knowledge, and impossible possible worlds. Although in some
settings these approaches are equi-expressive and can capture all epistemic
states, in other settings of interest (especially with probability in the
picture), we show that they are not equi-expressive. We then consider the
pragmatics of dealing with logical omniscience-- how to choose an approach and
construct an appropriate model.


title: Plagiarism Detection in arXiv

abstract:
  We describe a large-scale application of methods for finding plagiarism in
research document collections. The methods are applied to a collection of
284,834 documents collected by arXiv.org over a 14 year period, covering a few
different research disciplines. The methodology efficiently detects a variety
of problematic author behaviors, and heuristics are developed to reduce the
number of false positives. The methods are also efficient enough to implement
as a real-time submission screen for a collection many times larger.


title:
A polynomial time algorithm to approximate the mixed volume within a
  simply exponential factor

abstract:
  Let ${\bf K} = (K_1, ..., K_n)$ be an $n$-tuple of convex compact subsets in
the Euclidean space $\R^n$, and let $V(\cdot)$ be the Euclidean volume in
$\R^n$. The Minkowski polynomial $V_{{\bf K}}$ is defined as $V_{{\bf
K}}(\lambda_1, ... ,\lambda_n) = V(\lambda_1 K_1 +, ..., + \lambda_n K_n)$ and
the mixed volume $V(K_1, ..., K_n)$ as $$ V(K_1, ..., K_n) =
\frac{\partial^n}{\partial \lambda_1...\partial \lambda_n} V_{{\bf
K}}(\lambda_1 K_1 +, ..., + \lambda_n K_n). $$ Our main result is a poly-time
algorithm which approximates $V(K_1, ..., K_n)$ with multiplicative error $e^n$
and with better rates if the affine dimensions of most of the sets $K_i$ are
small. Our approach is based on a particular approximation of $\log(V(K_1, ...,
K_n))$ by a solution of some convex minimization problem. We prove the mixed
volume analogues of the Van der Waerden and Schrijver-Valiant conjectures on
the permanent. These results, interesting on their own, allow us to justify the
abovementioned approximation by a convex minimization, which is solved using
the ellipsoid method and a randomized poly-time time algorithm for the
approximation of the volume of a convex set.


title: Probabilistic Analysis of Linear Programming Decoding

abstract:
  We initiate the probabilistic analysis of linear programming (LP) decoding of
low-density parity-check (LDPC) codes. Specifically, we show that for a random
LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds
in correcting a constant fraction of errors with high probability. The fraction
of correctable errors guaranteed by our analysis surpasses previous
non-asymptotic results for LDPC codes, and in particular exceeds the best
previous finite-length result on LP decoding by a factor greater than ten. This
improvement stems in part from our analysis of probabilistic bit-flipping
channels, as opposed to adversarial channels. At the core of our analysis is a
novel combinatorial characterization of LP decoding success, based on the
notion of a generalized matching. An interesting by-product of our analysis is
to establish the existence of ``probabilistic expansion'' in random bipartite
graphs, in which one requires only that almost every (as opposed to every) set
of a certain size expands, for sets much larger than in the classical
worst-case setting.


title: Network Coding for Distributed Storage Systems

abstract:
  Peer-to-peer distributed storage systems provide reliable access to data
through redundancy spread over nodes across the Internet. A key goal is to
minimize the amount of bandwidth used to maintain that redundancy. Storing a
file using an erasure code, in fragments spread across nodes, promises to
require less redundancy and hence less maintenance bandwidth than simple
replication to provide the same level of reliability. However, since fragments
must be periodically replaced as nodes fail, a key question is how to generate
a new fragment in a distributed way while transferring as little data as
possible across the network.
  In this paper, we introduce a general technique to analyze storage
architectures that combine any form of coding and replication, as well as
presenting two new schemes for maintaining redundancy using erasure codes.
First, we show how to optimally generate MDS fragments directly from existing
fragments in the system. Second, we introduce a new scheme called Regenerating
Codes which use slightly larger fragments than MDS but have lower overall
bandwidth use. We also show through simulation that in realistic environments,
Regenerating Codes can reduce maintenance bandwidth use by 25 percent or more
compared with the best previous design--a hybrid of replication and erasure
codes--while simplifying system architecture.


title: A multivariate interlace polynomial

abstract:
  We define a multivariate polynomial that generalizes several interlace
polynomials defined by Arratia, Bollobas and Sorkin on the one hand, and Aigner
and van der Holst on the other. We follow the route traced by Sokal, who
defined a multivariate generalization of Tutte's polynomial. We also show that
bounded portions of our interlace polynomial can be evaluated in polynomial
time for graphs of bounded clique-width. Its full evaluation is necessarly
exponential just because of the size of the result.


title:
Comment on Improved Analysis of List Decoding and Its Application to
  Convolutional Codes and Turbo Codes

abstract:
  In a recent paper [1] an improved analysis concerning the analysis of List
Decoding was presented. The event that the correct codeword is excluded from
the list is central. For the additive white Gaussian noise (AWGN) channel an
important quantity is the in [1] called effective Euclidean distance. This was
earlier considered in [2] under the name Vector Euclidean Distance, where also
a simple mathematical expression for this quantity was easily derived for any
list size. In [1], a geometrical analysis gives this when the list size is 1, 2
or 3.


title: Estimation of the Rate-Distortion Function

abstract:
  Motivated by questions in lossy data compression and by theoretical
considerations, we examine the problem of estimating the rate-distortion
function of an unknown (not necessarily discrete-valued) source from empirical
data. Our focus is the behavior of the so-called "plug-in" estimator, which is
simply the rate-distortion function of the empirical distribution of the
observed data. Sufficient conditions are given for its consistency, and
examples are provided to demonstrate that in certain cases it fails to converge
to the true rate-distortion function. The analysis of its performance is
complicated by the fact that the rate-distortion function is not continuous in
the source distribution; the underlying mathematical problem is closely related
to the classical problem of establishing the consistency of maximum likelihood
estimators. General consistency results are given for the plug-in estimator
applied to a broad class of sources, including all stationary and ergodic ones.
A more general class of estimation problems is also considered, arising in the
context of lossy data compression when the allowed class of coding
distributions is restricted; analogous results are developed for the plug-in
estimator in that case. Finally, consistency theorems are formulated for
modified (e.g., penalized) versions of the plug-in, and for estimating the
optimal reproduction distribution.


title: A Dynamic I/O Model for TRACON Traffic Management

abstract:
  This work investigates the TRACON flow management around a major airport.
Aircraft flows are analyzed through a study of TRACON trajectories records.
Rerouting and queuing processes are highlighted and airport characteristics are
shown as function of the number of planes in the TRACON. Then, a simple
input-output TRACON queuing and landing model is proposed. This model is
calibrated and validated using available TRACON data. It reproduces the same
phenomenon as the real system. This model is used to show the impact of
limiting the number of aircrafts in the TRACON. A limited number of aircraft
does not increase delays but reduces the controller's workload and increases
safety.


title:
Construction of Minimal Tail-Biting Trellises for Codes over Finite
  Abelian Groups

abstract:
  A definition of atomic codeword for a group code is presented. Some
properties of atomic codewords of group codes are investigated. Using these
properties, it is shown that every minimal tail-biting trellis for a group code
over a finite abelian group can be constructed from its characteristic
generators, which extends the work of Koetter and Vardy who treated the case of
a linear code over a field. We also present an efficient algorithm for
constructing the minimal tail-biting trellis of a group code over a finite
abelian group, given a generator matrix.


title:
Probability Bracket Notation, Probability Vectors, Markov Chains and
  Stochastic Processes

abstract:
  Dirac notation has been widely used for vectors in Hilbert spaces of Quantum
Theories and now also in Information Retrieval. In this paper, we propose to
use Probability Bracket Notation (PBN) for probability modeling. The new
symbols are defined similarly (but not identically) as in Dirac notation. By
using PBN to represent fundamental definitions and theorems for discrete and
continuous random variables, we show that PBN could play a similar role in
probability sample space as Dirac notation in Hilbert space. We also find a
close relation between our system state P-kets and probability vectors in
Markov chains. In the end, we apply PBN to some important stochastic processes,
present the master equation of time-continuous Markov chains in both
Schrodinger and Heisenberg pictures. We identify our system state P-bra with
Doi's state function and Peliti's standard bra. We summarize the similarities
and differences between PBN and Dirac Notation in the two tables of Appendix A.


title: Gnutella: Topology Dynamics On Phase Space

abstract:
  In this paper, the topology dynamic of Gnutella is studied through phase
space. The dynamic changes in peer degree are studied as a time series in two
dimensional phase space which is defined as the number of connected leaves and
the number of connected ultras. The reported degrees are concentrated in three
special Software related regions that we named as Ultra Stable Region, Leaf
Stable Region and Transition Belt. A method is proposed to classify degree
traces in phase space into different classes. Connection churn then is studied
along with the churn in degree. It shows that the topological structure of
Gnutella is rather stable in its connection degree but not the topology itself.
The connection drop rate is estimated and the live time of connections is
inferred afterwards. M/M/m/m loss queue system is introduced to model the
degree keeping process in Gnutella. This model revealed that the degree stable
is ensured by large new connection efforts. In other words the stable in
topological structure of Gnutella is a results of essential unstable in its
topology. That opens a challenge to the basic design philosophy of this
network.


title: High-rate, Multi-Symbol-Decodable STBCs from Clifford Algebras

abstract:
  It is well known that Space-Time Block Codes (STBCs) obtained from Orthogonal
Designs (ODs) are single-symbol-decodable (SSD) and from Quasi-Orthogonal
Designs (QODs) are double-symbol decodable. However, there are SSD codes that
are not obtainable from ODs and DSD codes that are not obtainable from QODs. In
this paper a method of constructing $g$-symbol decodable ($g$-SD) STBCs using
representations of Clifford algebras are presented which when specialized to
$g=1,2$ gives SSD and DSD codes respectively. For the number of transmit
antennas $2^a$ the rate (in complex symbols per channel use) of the $g$-SD
codes presented in this paper is $\frac{a+1-g}{2^{a-g}}$. The maximum rate of
the DSD STBCs from QODs reported in the literature is $\frac{a}{2^{a-1}}$ which
is smaller than the rate $\frac{a-1}{2^{a-2}}$ of the DSD codes of this paper,
for $2^a$ transmit antennas. In particular, the reported DSD codes for 8 and 16
transmit antennas offer rates 1 and 3/4 respectively whereas the known STBCs
from QODs offer only 3/4 and 1/2 respectively. The construction of this paper
is applicable for any number of transmit antennas.


title: Searching for low weight pseudo-codewords

abstract:
  Belief Propagation (BP) and Linear Programming (LP) decodings of Low Density
Parity Check (LDPC) codes are discussed. We summarize results of
instanton/pseudo-codeword approach developed for analysis of the error-floor
domain of the codes. Instantons are special, code and decoding specific,
configurations of the channel noise contributing most to the Frame-Error-Rate
(FER). Instantons are decoded into pseudo-codewords. Instanton/pseudo-codeword
with the lowest weight describes the largest Signal-to-Noise-Ratio (SNR)
asymptotic of FER, while the whole spectra of the low weight instantons is
descriptive of the FER vs SNR profile in the extended error-floor domain.
First, we describe a general optimization method that allows to find the
instantons for any coding/decoding. Second, we introduce LP-specific
pseudo-codeword search algorithm that allows efficient calculations of the
pseudo-codeword spectra. Finally, we discuss results of combined BP/LP
error-floor exploration experiments for two model codes.


title:
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for
  DCTs and DSTs

abstract:
  This paper presents a systematic methodology based on the algebraic theory of
signal processing to classify and derive fast algorithms for linear transforms.
Instead of manipulating the entries of transform matrices, our approach derives
the algorithms by stepwise decomposition of the associated signal models, or
polynomial algebras. This decomposition is based on two generic methods or
algebraic principles that generalize the well-known Cooley-Tukey FFT and make
the algorithms' derivations concise and transparent. Application to the 16
discrete cosine and sine transforms yields a large class of fast algorithms,
many of which have not been found before.


title: Shape preservation behavior of spline curves

abstract:
  Shape preservation behavior of a spline consists of criterial conditions for
preserving convexity, inflection, collinearity, torsion and coplanarity shapes
of data polgonal arc. We present our results which acts as an improvement in
the definitions of and provide geometrical insight into each of the above shape
preservation criteria. We also investigate the effect of various results from
the literature on various shape preservation criteria. These results have not
been earlier refered in the context of shape preservation behaviour of splines.
We point out that each curve segment need to satisfy more than one shape
preservation criteria. We investigate the conflict between different shape
preservation criteria 1)on each curve segment and 2)of adjacent curve segments.
We derive simplified formula for shape preservation criteria for cubic curve
segments. We study the shape preservation behavior of cubic Catmull-Rom splines
and see that, though being very simple spline curve, it indeed satisfy all the
shape preservation criteria.


title:
The Suspension Calculus and its Relationship to Other Explicit
  Treatments of Substitution in Lambda Calculi

abstract:
  The intrinsic treatment of binding in the lambda calculus makes it an ideal
data structure for representing syntactic objects with binding such as
formulas, proofs, types, and programs. Supporting such a data structure in an
implementation is made difficult by the complexity of the substitution
operation relative to lambda terms. In this paper we present the suspension
calculus, an explicit treatment of meta level binding in the lambda calculus.
We prove properties of this calculus which make it a suitable replacement for
the lambda calculus in implementation. Finally, we compare the suspension
calculus with other explicit treatments of substitution.


title: Uniform and Partially Uniform Redistribution Rules

abstract:
  This short paper introduces two new fusion rules for combining quantitative
basic belief assignments. These rules although very simple have not been
proposed in literature so far and could serve as useful alternatives because of
their low computation cost with respect to the recent advanced Proportional
Conflict Redistribution rules developed in the DSmT framework.


title: On the variance of subset sum estimation

abstract:
  For high volume data streams and large data warehouses, sampling is used for
efficient approximate answers to aggregate queries over selected subsets.
Mathematically, we are dealing with a set of weighted items and want to support
queries to arbitrary subset sums. With unit weights, we can compute subset
sizes which together with the previous sums provide the subset averages. The
question addressed here is which sampling scheme we should use to get the most
accurate subset sum estimates.
  We present a simple theorem on the variance of subset sum estimation and use
it to prove variance optimality and near-optimality of subset sum estimation
with different known sampling schemes. This variance is measured as the average
over all subsets of any given size. By optimal we mean there is no set of input
weights for which any sampling scheme can have a better average variance. Such
powerful results can never be established experimentally. The results of this
paper are derived mathematically. For example, we show that appropriately
weighted systematic sampling is simultaneously optimal for all subset sizes.
More standard schemes such as uniform sampling and
probability-proportional-to-size sampling with replacement can be arbitrarily
bad.
  Knowing the variance optimality of different sampling schemes can help
deciding which sampling scheme to apply in a given context.


title: Optimizing the SINR operating point of spatial networks

abstract:
  This paper addresses the following question, which is of interest in the
design and deployment of a multiuser decentralized network. Given a total
system bandwidth of W Hz and a fixed data rate constraint of R bps for each
transmission, how many frequency slots N of size W/N should the band be
partitioned into to maximize the number of simultaneous transmissions in the
network? In an interference-limited ad-hoc network, dividing the available
spectrum results in two competing effects: on the positive side, it reduces the
number of users on each band and therefore decreases the interference level
which leads to an increased SINR, while on the negative side the SINR
requirement for each transmission is increased because the same information
rate must be achieved over a smaller bandwidth. Exploring this tradeoff between
bandwidth and SINR and determining the optimum value of N in terms of the
system parameters is the focus of the paper. Using stochastic geometry, we
analytically derive the optimal SINR threshold (which directly corresponds to
the optimal spectral efficiency) on this tradeoff curve and show that it is a
function of only the path loss exponent. Furthermore, the optimal SINR point
lies between the low-SINR (power-limited) and high-SINR (bandwidth-limited)
regimes. In order to operate at this optimal point, the number of frequency
bands (i.e., the reuse factor) should be increased until the threshold SINR,
which is an increasing function of the reuse factor, is equal to the optimal
value.


title:
Quantized vs. Analog Feedback for the MIMO Downlink: A Comparison
  between Zero-Forcing Based Achievable Rates

abstract:
  We consider a MIMO fading broadcast channel and compare the achievable
ergodic rates when the channel state information at the transmitter is provided
by analog noisy feedback or by quantized (digital) feedback. The superiority of
digital feedback is shown, with perfect or imperfect CSIR, whenever the number
of feedback channel uses per channel coefficient is larger than 1. Also, we
show that by proper design of the digital feedback link, errors in the feedback
have a minor effect even by using very simple uncoded modulation. Finally, we
show that analog feedback achieves a fraction 1 - 2F of the optimal
multiplexing gain even in the presence of a feedback delay, when the fading
belongs to the class of Doppler processes with normalized maximum Doppler
frequency shift 0 <= F <= 1/2.


title: Finding large and small dense subgraphs

abstract:
  We consider two optimization problems related to finding dense subgraphs. The
densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of
highest average degree among all subgraphs with at least k vertices, and the
densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems
are related to the well-known densest k-subgraph problem (DkS), which is to
find the densest subgraph on exactly k vertices. We show that DalkS can be
approximated efficiently, while DamkS is nearly as hard to approximate as the
densest k-subgraph problem.


title: Bounds on ordered codes and orthogonal arrays

abstract:
  We derive new estimates of the size of codes and orthogonal arrays in the
ordered Hamming space (the Niederreiter-Rosenbloom-Tsfasman space). We also
show that the eigenvalues of the ordered Hamming scheme, the association scheme
that describes the combinatorics of the space, are given by the multivariable
Krawtchouk polynomials, and establish some of their properties.


title: Graph Splicing System

abstract:
  The string splicing was introduced by Tom Head which stands as an abstract
model for the DNA recombination under the influence of restriction enzymes. The
complex chemical process of three dimensional molecules in three dimensional
space can be modeled using graphs. The graph splicing systems which were
studied so far, can only be applied to a particular type of graphs which could
be interpreted as linear or circular graphs. In this paper, we take a different
and a novel approach to splice two graphs and introduce a splicing system for
graphs that can be applied to all types of graphs. Splicing two graphs can be
thought of as a new operation, among the graphs, that generates many new graphs
from the given two graphs. Taking a different line of thinking, some of the
graph theoretical results of the splicing are studied.


title: New Models for the Correlation in Sensor Data

abstract:
  In this paper, we propose two new models of spatial correlations in sensor
data in a data-gathering sensor network. A particular property of these models
is that if a sensor node knows in \textit{how many} bits it needs to transmit
its data, then it also knows \textit{which} bits of its data it needs to
transmit.


title: Efficient First-Order Temporal Logic for Infinite-State Systems

abstract:
  In this paper we consider the specification and verification of
infinite-state systems using temporal logic. In particular, we describe
parameterised systems using a new variety of first-order temporal logic that is
both powerful enough for this form of specification and tractable enough for
practical deductive verification. Importantly, the power of the temporal
language allows us to describe (and verify) asynchronous systems, communication
delays and more complex properties such as liveness and fairness properties.
These aspects appear difficult for many other approaches to infinite-state
verification.


title: Evolutionary Approaches to Minimizing Network Coding Resources

abstract:
  We wish to minimize the resources used for network coding while achieving the
desired throughput in a multicast scenario. We employ evolutionary approaches,
based on a genetic algorithm, that avoid the computational complexity that
makes the problem NP-hard. Our experiments show great improvements over the
sub-optimal solutions of prior methods. Our new algorithms improve over our
previously proposed algorithm in three ways. First, whereas the previous
algorithm can be applied only to acyclic networks, our new method works also
with networks with cycles. Second, we enrich the set of components used in the
genetic algorithm, which improves the performance. Third, we develop a novel
distributed framework. Combining distributed random network coding with our
distributed optimization yields a network coding protocol where the resources
used for coding are optimized in the setup phase by running our evolutionary
algorithm at each node of the network. We demonstrate the effectiveness of our
approach by carrying out simulations on a number of different sets of network
topologies.


title:
Genetic Representations for Evolutionary Minimization of Network Coding
  Resources

abstract:
  We demonstrate how a genetic algorithm solves the problem of minimizing the
resources used for network coding, subject to a throughput constraint, in a
multicast scenario. A genetic algorithm avoids the computational complexity
that makes the problem NP-hard and, for our experiments, greatly improves on
sub-optimal solutions of established methods. We compare two different genotype
encodings, which tradeoff search space size with fitness landscape, as well as
the associated genetic operators. Our finding favors a smaller encoding despite
its fewer intermediate solutions and demonstrates the impact of the modularity
enforced by genetic operators on the performance of the algorithm.


title: Hadwiger and Helly-type theorems for disjoint unit spheres

abstract:
  We prove Helly-type theorems for line transversals to disjoint unit balls in
$\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit
balls in $\R^d$ has a line transversal if, for some ordering $\prec$ of the
balls, any subfamily of 2d balls admits a line transversal consistent with
$\prec$. We also prove that a family of $n \geq 4d-1$ disjoint unit balls in
$\R^d$ admits a line transversal if any subfamily of size $4d-1$ admits a
transversal.


title: Polygraphs for termination of left-linear term rewriting systems

abstract:
  We present a methodology for proving termination of left-linear term
rewriting systems (TRSs) by using Albert Burroni's polygraphs, a kind of
rewriting systems on algebraic circuits. We translate the considered TRS into a
polygraph of minimal size whose termination is proven with a polygraphic
interpretation, then we get back the property on the TRS. We recall Yves
Lafont's general translation of TRSs into polygraphs and known links between
their termination properties. We give several conditions on the original TRS,
including being a first-order functional program, that ensure that we can
reduce the size of the polygraphic translation. We also prove sufficient
conditions on the polygraphic interpretations of a minimal translation to imply
termination of the original TRS. Examples are given to compare this method with
usual polynomial interpretations.


title: The Fibers and Range of Reduction Graphs in Ciliates

abstract:
  The biological process of gene assembly has been modeled based on three types
of string rewriting rules, called string pointer rules, defined on so-called
legal strings. It has been shown that reduction graphs, graphs that are based
on the notion of breakpoint graph in the theory of sorting by reversal, for
legal strings provide valuable insights into the gene assembly process. We
characterize which legal strings obtain the same reduction graph (up to
isomorphism), and moreover we characterize which graphs are (isomorphic to)
reduction graphs.


title: A Formal Model for Programming Wireless Sensor Networks

abstract:
  In this paper we present new developments in the expressiveness and in the
theory of a Calculus for Sensor Networks (CSN). We combine a network layer of
sensor devices with a local object model to describe sensor devices with state.
The resulting calculus is quite small and yet very expressive. We also present
a type system and a type invariance result for the calculus. These results
provide the fundamental framework for the development of programming languages
and run-time environments.


title: Deciding k-colourability of $P_5$-free graphs in polynomial time

abstract:
  The problem of computing the chromatic number of a $P_5$-free graph is known
to be NP-hard. In contrast to this negative result, we show that determining
whether or not a $P_5$-free graph admits a $k$-colouring, for each fixed number
of colours $k$, can be done in polynomial time. If such a colouring exists, our
algorithm produces it.


title: Transmission Capacity of Ad Hoc Networks with Spatial Diversity

abstract:
  This paper derives the outage probability and transmission capacity of ad hoc
wireless networks with nodes employing multiple antenna diversity techniques,
for a general class of signal distributions. This analysis allows system
performance to be quantified for fading or non-fading environments. The
transmission capacity is given for interference-limited uniformly random
networks on the entire plane with path loss exponent $\alpha>2$ in which nodes
use: (1) static beamforming through $M$ sectorized antennas, for which the
increase in transmission capacity is shown to be $\Theta(M^2)$ if the antennas
are without sidelobes, but less in the event of a nonzero sidelobe level; (2)
dynamic eigen-beamforming (maximal ratio transmission/combining), in which the
increase is shown to be $\Theta(M^{\frac{2}{\alpha}})$; (3) various transmit
antenna selection and receive antenna selection combining schemes, which give
appreciable but rapidly diminishing gains; and (4) orthogonal space-time block
coding, for which there is only a small gain due to channel hardening,
equivalent to Nakagami-$m$ fading for increasing $m$. It is concluded that in
ad hoc networks, static and dynamic beamforming perform best, selection
combining performs well but with rapidly diminishing returns with added
antennas, and that space-time block coding offers only marginal gains.


title: Gaussian Interference Channel Capacity to Within One Bit

abstract:
  The capacity of the two-user Gaussian interference channel has been open for
thirty years. The understanding on this problem has been limited. The best
known achievable region is due to Han-Kobayashi but its characterization is
very complicated. It is also not known how tight the existing outer bounds are.
In this work, we show that the existing outer bounds can in fact be arbitrarily
loose in some parameter ranges, and by deriving new outer bounds, we show that
a simplified Han-Kobayashi type scheme can achieve to within a single bit the
capacity for all values of the channel parameters. We also show that the scheme
is asymptotically optimal at certain high SNR regimes. Using our results, we
provide a natural generalization of the point-to-point classical notion of
degrees of freedom to interference-limited scenarios.


title: Design and Analysis of the REESSE1+ Public Key Cryptosystem v2.21

abstract:
  In this paper, the authors give the definitions of a coprime sequence and a
lever function, and describe the five algorithms and six characteristics of a
prototypal public key cryptosystem which is used for encryption and signature,
and based on three new problems and one existent problem: the multivariate
permutation problem (MPP), the anomalous subset product problem (ASPP), the
transcendental logarithm problem (TLP), and the polynomial root finding problem
(PRFP). Prove by reduction that MPP, ASPP, and TLP are computationally at least
equivalent to the discrete logarithm problem (DLP) in the same prime field, and
meanwhile find some evidence which inclines people to believe that the new
problems are harder than DLP each, namely unsolvable in DLP subexponential
time. Demonstrate the correctness of the decryption and the verification,
deduce the probability of a plaintext solution being nonunique is nearly zero,
and analyze the exact securities of the cryptosystem against recovering a
plaintext from a ciphertext, extracting a private key from a public key or a
signature, and forging a signature through known signatures, public keys, and
messages on the assumption that IFP, DLP, and LSSP can be solved. Studies
manifest that the running times of effectual attack tasks are greater than or
equal to O(2^n) so far when n = 80, 96, 112, or 128 with lgM = 696, 864, 1030,
or 1216. As viewed from utility, it should be researched further how to
decrease the length of a modulus and to increase the speed of the decryption.


title: Hierarchical Unambiguity

abstract:
  We develop techniques to investigate relativized hierarchical unambiguous
computation. We apply our techniques to generalize known constructs involving
relativized unambiguity based complexity classes (UP and \mathcal{UP}) to new
constructs involving arbitrary higher levels of the relativized unambiguous
polynomial hierarchy (UPH). Our techniques are developed on constraints imposed
by hierarchical arrangement of unambiguous nondeterministic polynomial-time
Turing machines, and so they differ substantially, in applicability and in
nature, from standard methods (such as the switching lemma [Hastad,
Computational Limitations of Small-Depth Circuits, MIT Press, 1987]), which
play roles in carrying out similar generalizations.
  Aside from achieving these generalizations, we resolve a question posed by
Cai, Hemachandra, and Vyskoc [J. Cai, L. Hemachandra, and J. Vyskoc, Promises
and fault-tolerant database access, In K. Ambos-Spies, S. Homer, and U.
Schoening, editors, Complexity Theory, pages 101-146. Cambridge University
Press, 1993] on an issue related to nonadaptive Turing access to UP and
adaptive smart Turing access to \mathcal{UP}.