OpenRaiser/Intern-Atlas huggingface dataset:
Mathematical foundations of modern cryptography: computational complexity perspective
Venue: arXiv cs.CR 2002
Year: 2002

Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.
Additive models in high dimensions
Venue: arXiv cs.DS 2002
Year: 2002

We discuss some aspects of approximating functions on high-dimensional data sets with additive functions or ANOVA decompositions, that is, sums of functions depending on fewer variables each. It is seen that under appropriate smoothness conditions, the errors of the ANOVA decompositions are of order $O(n^{m/2})$ for approximations using sums of functions of up to $m$ variables under some mild restrictions on the (possibly dependent) predictor variables. Several simulated examples illustrate this behaviour.
Predicting the expected behavior of agents that learn about agents: the CLRI framework
Venue: arXiv cs.MA 2003
Year: 2003

We describe a framework and equations used to model and predict the behavior of multi-agent systems (MASs) with learning agents. A difference equation is used for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agent's learning abilities, such as its change rate, learning rate and retention rate, as well as relevant aspects of the MAS such as the impact that agents have on each other. We validate the framework with experimental results using reinforcement learning agents in a market system, as well as with other experimental results gathered from the AI literature. Finally, we use PAC-theory to show how to calculate bounds on the values of the learning parameters.
Interactive Constrained Association Rule Mining
Venue: arXiv cs.DB 2003
Year: 2003

We investigate ways to support interactive mining sessions, in the setting of association rule mining. In such sessions, users specify conditions (queries) on the associations to be generated. Our approach is a combination of the integration of querying conditions inside the mining phase, and the incremental querying of already generated associations. We present several concrete algorithms and compare their performance.
A theory of experiment
Venue: arXiv cs.AI 2003
Year: 2003

This article aims at clarifying the language and practice of scientific experiment, mainly by hooking observability on calculability.
A Connection-Centric Survey of Recommender Systems Research
Venue: arXiv cs.IR 2003
Year: 2003

Recommender systems attempt to reduce information overload and retain customers by selecting a subset of items from a universal set based on user preferences. While research in recommender systems grew out of information retrieval and filtering, the topic has steadily advanced into a legitimate and challenging research area of its own. Recommender systems have traditionally been studied from a content-based filtering vs. collaborative design perspective. Recommendations, however, are not delivered within a vacuum, but rather cast within an informal community of users and social context. Therefore, ultimately all recommender systems make connections among people and thus should be surveyed from such a perspective. This viewpoint is under-emphasized in the recommender systems literature. We therefore take a connection-oriented viewpoint toward recommender systems research. We posit that recommendation has an inherently social element and is ultimately intended to connect people either directly as a result of explicit user modeling or indirectly through the discovery of relationships implicit in extant data. Thus, recommender systems are characterized by how they model users to bring people together: explicitly or implicitly. Finally, user modeling and the connection-centric viewpoint raise broadening and social issues--such as evaluation, targeting, and privacy and trust--which we also briefly address.
The DLV System for Knowledge Representation and Reasoning
Venue: arXiv cs.AI 2003
Year: 2003

This paper presents the DLV system, which is widely considered the state-of-the-art implementation of disjunctive logic programming, and addresses several aspects. As for problem solving, we provide a formal definition of its kernel language, function-free disjunctive logic programs (also known as disjunctive datalog), extended by weak constraints, which are a powerful tool to express optimization problems. We then illustrate the usage of DLV as a tool for knowledge representation and reasoning, describing a new declarative programming methodology which allows one to encode complex problems (up to $Δ^P_3$-complete problems) in a declarative fashion. On the foundational side, we provide a detailed analysis of the computational complexity of the language of DLV, and by deriving new complexity results we chart a complete picture of the complexity of this language and important fragments thereof. Furthermore, we illustrate the general architecture of the DLV system which has been influenced by these results. As for applications, we overview application front-ends which have been developed on top of DLV to solve specific knowledge representation tasks, and we briefly describe the main international projects investigating the potential of the system for industrial exploitation. Finally, we report about thorough experimentation and benchmarking, which has been carried out to assess the efficiency of the system. The experimental results confirm the solidity of DLV and highlight its potential for emerging application areas like knowledge management and information integration.
Monadic Datalog and the Expressive Power of Languages for Web Information Extraction
Venue: arXiv cs.DB 2003
Year: 2003

Research on information extraction from Web pages (wrapping) has seen much activity recently (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping. In this paper, we first study monadic datalog over trees as a wrapping language. We show that this simple language is equivalent to monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and propose MSO as a yardstick for evaluating and comparing wrappers. Along the way, several other results on the complexity of query evaluation and query containment for monadic datalog over trees are established, and a simple normal form for this language is presented. Using the above results, we subsequently study the kernel fragment Elog$^-$ of the Elog wrapping language used in the Lixto system (a visual wrapper generator). Curiously, Elog$^-$ exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified.
Solution Bounds for a Hypothetical Polynomial Time Aproximation Algorithm for the TSP
Venue: arXiv cs.CC 2003
Year: 2003

Bounds for the optimal tour length for a hypothetical TSP algorithm are derived.
Least squares fitting of circles and lines
Venue: arXiv cs.CV 2003
Year: 2003

We study theoretical and computational aspects of the least squares fit (LSF) of circles and circular arcs. First we discuss the existence and uniqueness of LSF and various parametrization schemes. Then we evaluate several popular circle fitting algorithms and propose a new one that surpasses the existing methods in reliability. We also discuss and compare direct (algebraic) circle fits.
Near Quadratic Matrix Multiplication Modulo Composites
Venue: arXiv cs.CC 2003
Year: 2003

We show how one can use non-prime-power, composite moduli for computing representations of the product of two $n\times n$ matrices using only $n^{2+o(1)}$ multiplications.
Modelling Delay Jitter in Voice over IP
Venue: arXiv cs.PF 2003
Year: 2003

It has been suggested in voice over IP that an appropriate choice of the distribution used in modeling the delay jitters, can improve the play-out algorithm. In this paper, we propose a tool using which, one can determine, at a given instance, which distribution model best explains the jitter distribution. This is done using Expectation Maximization, to choose amongst possible distribution models which include, the i.i.d exponential distribution, the gamma distribution etc.
Temporal plannability by variance of the episode length
Venue: arXiv cs.AI 2003
Year: 2003

Optimization of decision problems in stochastic environments is usually concerned with maximizing the probability of achieving the goal and minimizing the expected episode length. For interacting agents in time-critical applications, learning of the possibility of scheduling of subtasks (events) or the full task is an additional relevant issue. Besides, there exist highly stochastic problems where the actual trajectories show great variety from episode to episode, but completing the task takes almost the same amount of time. The identification of sub-problems of this nature may promote e.g., planning, scheduling and segmenting Markov decision processes. In this work, formulae for the average duration as well as the standard deviation of the duration of events are derived. The emerging Bellman-type equation is a simple extension of Sobel's work (1982). Methods of dynamic programming as well as methods of reinforcement learning can be applied for our extension. Computer demonstration on a toy problem serve to highlight the principle.
Formal Concept Analysis and Resolution in Algebraic Domains
Venue: arXiv cs.LO 2003
Year: 2003

We relate two formerly independent areas: Formal concept analysis and logic of domains. We will establish a correspondene between contextual attribute logic on formal contexts resp. concept lattices and a clausal logic on coherent algebraic cpos. We show how to identify the notion of formal concept in the domain theoretic setting. In particular, we show that a special instance of the resolution rule from the domain logic coincides with the concept closure operator from formal concept analysis. The results shed light on the use of contexts and domains for knowledge representation and reasoning purposes.
A Script Language for Data Integration in Database
Venue: arXiv cs.DB 2003
Year: 2003

A Script Language in this paper is designed to transform the original data into the target data by the computing formula. The Script Language can be translated into the corresponding SQL Language, and the computation is finally implemented by the first type of dynamic SQL. The Script Language has the operations of insert, update, delete, union, intersect, and minus for the table in the database.The Script Language is edited by a text file and you can easily modify the computing formula in the text file to deal with the situations when the computing formula have been changed. So you only need modify the text of the script language, but needn't change the programs that have complied.
Homomorphic public-key cryptosystems and encrypting boolean circuits
Venue: arXiv cs.CR 2003
Year: 2003

In this paper homomorphic cryptosystems are designed for the first time over any finite group. Applying Barrington's construction we produce for any boolean circuit of the logarithmic depth its encrypted simulation of a polynomial size over an appropriate finitely generated group.
Subclassing errors, OOP, and practically checkable rules to prevent them
Venue: arXiv cs.PL 2003
Year: 2003

This paper considers an example of Object-Oriented Programming (OOP) leading to subtle errors that break separation of interface and implementations. A comprehensive principle that guards against such errors is undecidable. The paper introduces a set of mechanically verifiable rules that prevent these insidious problems. Although the rules seem restrictive, they are powerful and expressive, as we show on several familiar examples. The rules contradict both the spirit and the letter of the OOP. The present examples as well as available theoretical and experimental results pose a question if OOP is conducive to software development at all.
Approximate analysis of search algorithms with "physical" methods
Venue: arXiv cs.CC 2003
Year: 2003

An overview of some methods of statistical physics applied to the analysis of algorithms for optimization problems (satisfiability of Boolean constraints, vertex cover of graphs, decoding, ...) with distributions of random inputs is proposed. Two types of algorithms are analyzed: complete procedures with backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local search procedures (gradient descent, random walksat, ...). The study of complete algorithms makes use of physical concepts such as phase transitions, dynamical renormalization flow, growth processes, ... As for local search procedures, the connection between computational complexity and the structure of the cost function landscape is questioned, with emphasis on the notion of metastability.
When Crossings Count - Approximating the Minimum Spanning Tree
Venue: arXiv cs.CG 2003
Year: 2003

In the first part of the paper, we present an (1+μ)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings between the spanning tree and the lines. The expected running time is O((n/μ^5) alpha^3(n) log^5 n), where μ> 0 is a prescribed constant. In the second part of our paper, we show how to embed such a crossing metric, into high-dimensions, so that the distances are preserved. As a result, we can deploy a large collection of subquadratic approximations algorithms \cite im-anntr-98,giv-rahdg-99 for problems involving points with the crossing metric as a distance function. Applications include matching, clustering, nearest-neighbor, and furthest-neighbor.
Fair Solution to the Reader-Writer-Problem with Semaphores only
Venue: arXiv cs.DC 2003
Year: 2003

The reader-writer-problem is a standard problem in concurrent programming. A resource is shared by several processes which need either inclusive reading or exclusive writing access. The known solutions to this problem typically involve a number of global counters and queues. Here a very simple algorithm is presented which needs only two semaphores for synchronisation and no other global objects. The approach yields a fair solution without starving.
On the Notion of Cognition
Venue: arXiv cs.AI 2003
Year: 2003

We discuss philosophical issues concerning the notion of cognition basing ourselves in experimental results in cognitive sciences, especially in computer simulations of cognitive systems. There have been debates on the "proper" approach for studying cognition, but we have realized that all approaches can be in theory equivalent. Different approaches model different properties of cognitive systems from different perspectives, so we can only learn from all of them. We also integrate ideas from several perspectives for enhancing the notion of cognition, such that it can contain other definitions of cognition as special cases. This allows us to propose a simple classification of different types of cognition.
Fast Parallel I/O on Cluster Computers
Venue: arXiv cs.DC 2003
Year: 2003

Today's cluster computers suffer from slow I/O, which slows down I/O-intensive applications. We show that fast disk I/O can be achieved by operating a parallel file system over fast networks such as Myrinet or Gigabit Ethernet. In this paper, we demonstrate how the ParaStation3 communication system helps speed-up the performance of parallel I/O on clusters using the open source parallel virtual file system (PVFS) as testbed and production system. We will describe the set-up of PVFS on the Alpha-Linux-Cluster-Engine (ALiCE) located at Wuppertal University, Germany. Benchmarks on ALiCE achieve write-performances of up to 1 GB/s from a 32-processor compute-partition to a 32-processor PVFS I/O-partition, outperforming known benchmark results for PVFS on the same network by more than a factor of 2. Read-performance from buffer-cache reaches up to 2.2 GB/s. Our benchmarks are giant, I/O-intensive eigenmode problems from lattice quantum chromodynamics, demonstrating stability and performance of PVFS over Parastation in large-scale production runs.
The missing links in the BGP-based AS connectivity maps
Venue: arXiv cs.NI 2003
Year: 2003

A number of recent studies of the Internet topology at the autonomous systems level (AS graph) are based on the BGP-based AS connectivity maps (original maps). The so-called extended maps use additional data sources and contain more complete pictures of the AS graph. In this paper, we compare an original map, an extended map and a synthetic map generated by the Barabasi-Albert model. We examine the recently reported rich-club phenomenon, alternative routing paths and attack tolerance. We point out that the majority of the missing links of the original maps are the connecting links between rich nodes (nodes with large numbers of links) of the extended maps. We show that the missing links are relevant because links between rich nodes can be crucial for the network structure.
Towards Modelling The Internet Topology - The Interactive Growth Model
Venue: arXiv cs.NI 2003
Year: 2003

The Internet topology at the Autonomous Systems level (AS graph) has a power--law degree distribution and a tier structure. In this paper, we introduce the Interactive Growth (IG) model based on the joint growth of new nodes and new links. This simple and dynamic model compares favorable with other Internet power--law topology generators because it not only closely resembles the degree distribution of the AS graph, but also accurately matches the hierarchical structure, which is measured by the recently reported rich-club phenomenon.
Quantum Computation and Lattice Problems
Venue: arXiv cs.DS 2003
Year: 2003

We present the first explicit connection between quantum computation and lattice problems. Namely, we show a solution to the Unique Shortest Vector Problem (SVP) under the assumption that there exists an algorithm that solves the hidden subgroup problem on the dihedral group by coset sampling. Moreover, we solve the hidden subgroup problem on the dihedral group by using an average case subset sum routine. By combining the two results, we get a quantum reduction from $Θ(n^{2.5})$-unique-SVP to the average case subset sum problem.
A Method for Clustering Web Attacks Using Edit Distance
Venue: arXiv cs.IR 2003
Year: 2003

Cluster analysis often serves as the initial step in the process of data classification. In this paper, the problem of clustering different length input data is considered. The edit distance as the minimum number of elementary edit operations needed to transform one vector into another is used. A heuristic for clustering unequal length vectors, analogue to the well known k-means algorithm is described and analyzed. This heuristic determines cluster centroids expanding shorter vectors to the lengths of the longest ones in each cluster in a specific way. It is shown that the time and space complexities of the heuristic are linear in the number of input vectors. Experimental results on real data originating from a system for classification of Web attacks are given.
A Physics-Free Introduction to the Quantum Computation Model
Venue: arXiv cs.CC 2003
Year: 2003

This article defines and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) deterministic and probabilistic circuits, without recourse to any physical concepts or principles. It is intended as a primer for theoretical computer scientists who do not know--and perhaps do not care to know--any physics.
Quasiconvex Analysis of Backtracking Algorithms
Venue: arXiv cs.DS 2003
Year: 2003

We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.
Model Checking for a Class of Weighted Automata
Venue: arXiv cs.LO 2003
Year: 2003

A large number of different model checking approaches has been proposed during the last decade. The different approaches are applicable to different model types including untimed, timed, probabilistic and stochastic models. This paper presents a new framework for model checking techniques which includes some of the known approaches, but enlarges the class of models for which model checking can be applied to the general class of weighted automata. The approach allows an easy adaption of model checking to models which have not been considered yet for this purpose. Examples for those new model types for which model checking can be applied are max/plus or min/plus automata which are well established models to describe different forms of dynamic systems and optimization problems. In this context, model checking can be used to verify temporal or quantitative properties of a system. The paper first presents briefly our class of weighted automata, as a very general model type. Then Valued Computational Tree Logic (CTL$) is introduced as a natural extension of the well known branching time logic CTL. Afterwards, algorithms to check a weighted automaton according to a CTL$ formula are presented. As a last result, a bisimulation is presented for weighted automata and for CTL$.
Computational Geometry Column 44
Venue: arXiv cs.CG 2003
Year: 2003

The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.