OpenRaiser/Intern-Atlas huggingface dataset:
Conditional Hardness for Approximate Coloring
Venue: arXiv cs.CC 2005
Year: 2005

We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. We derive conditional hardness for this problem for any constant $3 \le q < Q$. For $q\ge 4$, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For $q=3$, we base our hardness result on a certain `fish shaped' variant of his conjecture. We also prove that the problem almost coloring is hard for any constant $\eps>0$, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a $\eps$ fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least $\eps$. Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].
Selection in Scale-Free Small World
Venue: arXiv cs.LG 2005
Year: 2005

In this paper we compare the performance characteristics of our selection based learning algorithm for Web crawlers with the characteristics of the reinforcement learning algorithm. The task of the crawlers is to find new information on the Web. The selection algorithm, called weblog update, modifies the starting URL lists of our crawlers based on the found URLs containing new information. The reinforcement learning algorithm modifies the URL orderings of the crawlers based on the received reinforcements for submitted documents. We performed simulations based on data collected from the Web. The collected portion of the Web is typical and exhibits scale-free small world (SFSW) structure. We have found that on this SFSW, the weblog update algorithm performs better than the reinforcement learning algorithm. It finds the new information faster than the reinforcement learning algorithm and has better new information/all submitted documents ratio. We believe that the advantages of the selection algorithm over reinforcement learning algorithm is due to the small world property of the Web.
Self-Organization of the Neuron Collective of Optimal Complexity
Venue: arXiv cs.NE 2005
Year: 2005

The optimal complexity of neural networks is achieved when the self-organization principles is used to eliminate the contradictions existing in accordance with the K. Godel theorem about incompleteness of the systems based on axiomatics. The principle of S. Beer exterior addition the Heuristic Group Method of Data Handling by A. Ivakhnenko realized is used.
A Neural-Network Technique to Learn Concepts from Electroencephalograms
Venue: arXiv cs.NE 2005
Year: 2005

A new technique is presented developed to learn multi-class concepts from clinical electroencephalograms. A desired concept is represented as a neuronal computational model consisting of the input, hidden, and output neurons. In this model the hidden neurons learn independently to classify the electroencephalogram segments presented by spectral and statistical features. This technique has been applied to the electroencephalogram data recorded from 65 sleeping healthy newborns in order to learn a brain maturation concept of newborns aged between 35 and 51 weeks. The 39399 and 19670 segments from these data have been used for learning and testing the concept, respectively. As a result, the concept has correctly classified 80.1% of the testing segments or 87.7% of the 65 records.
The Modified Scheme is still vulnerable to the parallel Session Attack
Venue: arXiv cs.CR 2005
Year: 2005

In 2002, Chien–Jan–Tseng introduced an efficient remote user authentication scheme using smart cards. Further, in 2004, W. C. Ku and S. M. Chen proposed an efficient remote user authentication scheme using smart cards to solve the security problems of Chien et al.’s scheme. Recently, Hsu and Yoon et al. pointed out the security weakness of the Ku and Chen’s scheme Furthermore, Yoon et al. modified the password change phase of Ku and Chen’s scheme and they also proposed a new efficient remote user authentication scheme using smart cards. This paper analyzes that the modified scheme of Yoon et al. still vulnerable to parallel session attack.
The reverse greedy algorithm for the metric k-median problem
Venue: arXiv cs.DS 2005
Year: 2005

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the resulting total distance from the customers to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between ?(log n/ log log n) and O(log n).
Searching for image information content, its discovery, extraction, and representation
Venue: arXiv cs.CV 2005
Year: 2005

Image information content is known to be a complicated and controvercial problem. This paper posits a new image information content definition. Following the theory of Solomonoff-Kolmogorov-Chaitin's complexity, we define image information content as a set of descriptions of imafe data structures. Three levels of such description can be generally distinguished: 1)the global level, where the coarse structure of the entire scene is initially outlined; 2) the intermediate level, where structures of separate, non-overlapping image regions usually associated with individual scene objects are deliniated; and 3) the low-level description, where local image structures observed in a limited and restricted field of view are resolved. A technique for creating such image information content descriptors is developed. Its algorithm is presented and elucidated with some examples, which demonstrate the effectiveness of the proposed approach.
On the Wyner-Ziv problem for individual sequences
Venue: arXiv cs.IT 2005
Year: 2005

We consider a variation of the Wyner-Ziv problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best $M$-state encoder-decoder pair to that of the best block code of size $\ell$ for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of $(\log M)/\ell$, independently of the input sequence. Thus, in the limit of large $M$, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length $n$ of the input sequence grows without bound, we then consider the case where the number of states $M=M_n$ is allowed to grow concurrently with $n$. Our second result is then about the critical growth rate of $M_n$ such that the rate-distortion performance of $M_n$-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of $M_n$ is linear in $n$.
SWiM: A Simple Window Mover
Venue: arXiv cs.HC 2005
Year: 2005

As computers become more ubiquitous, traditional two-dimensional interfaces must be replaced with interfaces based on a three-dimensional metaphor. However, these interfaces must still be as simple and functional as their two-dimensional predecessors. This paper introduces SWiM, a new interface for moving application windows between various screens, such as wall displays, laptop monitors, and desktop displays, in a three-dimensional physical environment. SWiM was designed based on the results of initial "paper and pencil" user tests of three possible interfaces. The results of these tests led to a map-like interface where users select the destination display for their application from various icons. If the destination is a mobile display it is not displayed on the map. Instead users can select the screen's name from a list of all possible destination displays. User testing of SWiM was conducted to discover whether it is easy to learn and use. Users that were asked to use SWiM without any instructions found the interface as intuitive to use as users who were given a demonstration. The results show that SWiM combines simplicity and functionality to create an interface that is easy to learn and easy to use.
Interval Neutrosophic Sets and Logic: Theory and Applications in Computing
Venue: arXiv cs.LO 2005
Year: 2005

This book presents the advancements and applications of neutrosophics. Chapter 1 first introduces the interval neutrosophic sets which is an instance of neutrosophic sets. In this chapter, the definition of interval neutrosophic sets and set-theoretic operators are given and various properties of interval neutrosophic set are proved. Chapter 2 defines the interval neutrosophic logic based on interval neutrosophic sets including the syntax and semantics of first order interval neutrosophic propositional logic and first order interval neutrosophic predicate logic. The interval neutrosophic logic can reason and model fuzzy, incomplete and inconsistent information. In this chapter, we also design an interval neutrosophic inference system based on first order interval neutrosophic predicate logic. The interval neutrosophic inference system can be applied to decision making. Chapter 3 gives one application of interval neutrosophic sets and logic in the field of relational databases. Neutrosophic data model is the generalization of fuzzy data model and paraconsistent data model. Here, we generalize various set-theoretic and relation-theoretic operations of fuzzy data model to neutrosophic data model. Chapter 4 gives another application of interval neutrosophic logic. A soft semantic Web Services agent framework is proposed to faciliate the registration and discovery of high quality semantic Web Services agent. The intelligent inference engine module of soft Semantic Web Services agent is implemented using interval neutrosophic logic.
Collaborative Beamforming for Distributed Wireless Ad Hoc Sensor Networks
Venue: arXiv cs.IT 2005
Year: 2005

The performance of collaborative beamforming is analyzed using the theory of random arrays. The statistical average and distribution of the beampattern of randomly generated phased arrays is derived in the framework of wireless ad hoc sensor networks. Each sensor node is assumed to have a single isotropic antenna and nodes in the cluster collaboratively transmit the signal such that the signal in the target direction is coherently added in the far- eld region. It is shown that with N sensor nodes uniformly distributed over a disk, the directivity can approach N, provided that the nodes are located sparsely enough. The distribution of the maximum sidelobe peak is also studied. With the application to ad hoc networks in mind, two scenarios, closed-loop and open-loop, are considered. Associated with these scenarios, the effects of phase jitter and location estimation errors on the average beampattern are also analyzed.
State Space Computation and Analysis of Time Petri Nets
Venue: arXiv cs.LO 2005
Year: 2005

The theory of Petri Nets provides a general framework to specify the behaviors of real-time reactive systems and Time Petri Nets were introduced to take also temporal specifications into account. We present in this paper a forward zone-based algorithm to compute the state space of a bounded Time Petri Net: the method is different and more efficient than the classical State Class Graph. We prove the algorithm to be exact with respect to the reachability problem. Furthermore, we propose a translation of the computed state space into a Timed Automaton, proved to be timed bisimilar to the original Time Petri Net. As the method produce a single Timed Automaton, syntactical clocks reduction methods (Daws and Yovine for instance) may be applied to produce an automaton with fewer clocks. Then, our method allows to model-check TTPN by the use of efficient Timed Automata tools. To appear in Theory and Practice of Logic Programming (TPLP).
Logic Column 12: Logical Verification and Equational Verification
Venue: arXiv cs.LO 2005
Year: 2005

This article examines two approaches to verification, one based on using a logic for expressing properties of a system, and one based on showing the system equivalent to a simpler system that obviously has whatever property is of interest. Using examples such as process calculi and regular programs, the relationship between these two approaches is explored.
Beyond Hypertree Width: Decomposition Methods Without Decompositions
Venue: arXiv cs.CC 2005
Year: 2005

The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of work has focused on structural restrictions, which arise from restricting the interaction among constraint scopes. In this paper, we engage in a mathematical investigation of generalized hypertree width, a structural measure that has up to recently eluded study. We obtain a number of computational results, including a simple proof of the tractability of CSP instances having bounded generalized hypertree width.
Text Compression and Superfast Searching
Venue: arXiv cs.IR 2005
Year: 2005

In this paper, a new compression scheme for text is presented. The same is efficient in giving high compression ratios and enables super fast searching within the compressed text. Typical compression ratios of 70-80% and reducing the search time by 80-85% are the features of this paper. Till now, a trade-off between high ratios and searchability within compressed text has been seen. In this paper, we show that greater the compression, faster the search. This finds applicability in so many places where data as natural language text is present.
Handling equality constraints by adaptive relaxing rule for swarm algorithms
Venue: arXiv cs.NE 2005
Year: 2005

The adaptive constraints relaxing rule for swarm algorithms to handle with the problems with equality constraints is presented. The feasible space of such problems may be similiar to ridge function class, which is hard for applying swarm algorithms. To enter the solution space more easily, the relaxed quasi feasible space is introduced and shrinked adaptively. The experimental results on benchmark functions are compared with the performance of other algorithms, which show its efficiency.
SWAF: Swarm Algorithm Framework for Numerical Optimization
Venue: arXiv cs.NE 2005
Year: 2005

A swarm algorithm framework (SWAF), realized by agent-based modeling, is presented to solve numerical optimization problems. Each agent is a bare bones cognitive architecture, which learns knowledge by appropriately deploying a set of simple rules in fast and frugal heuristics. Two essential categories of rules, the generate-and-test and the problem-formulation rules, are implemented, and both of the macro rules by simple combination and subsymbolic deploying of multiple rules among them are also studied. Experimental results on benchmark problems are presented, and performance comparison between SWAF and other existing algorithms indicates that it is efficiently.
Summarization Techniques for Pattern Collections in Data Mining
Venue: arXiv cs.DB 2005
Year: 2005

Discovering patterns from data is an important task in data mining. There exist techniques to find large collections of many kinds of patterns from data very efficiently. A collection of patterns can be regarded as a summary of the data. A major difficulty with patterns is that pattern collections summarizing the data well are often very large. In this dissertation we describe methods for summarizing pattern collections in order to make them also more understandable. More specifically, we focus on the following themes: 1) Quality value simplifications. 2) Pattern orderings. 3) Pattern chains and antichains. 4) Change profiles. 5) Inverse pattern discovery.
Improving PARMA Trailing
Venue: arXiv cs.PL 2005
Year: 2005

Taylor introduced a variable binding scheme for logic variables in his PARMA system, that uses cycles of bindings rather than the linear chains of bindings used in the standard WAM representation. Both the HAL and dProlog languages make use of the PARMA representation in their Herbrand constraint solvers. Unfortunately, PARMA's trailing scheme is considerably more expensive in both time and space consumption. The aim of this paper is to present several techniques that lower the cost. First, we introduce a trailing analysis for HAL using the classic PARMA trailing scheme that detects and eliminates unnecessary trailings. The analysis, whose accuracy comes from HAL's determinism and mode declarations, has been integrated in the HAL compiler and is shown to produce space improvements as well as speed improvements. Second, we explain how to modify the classic PARMA trailing scheme to halve its trailing cost. This technique is illustrated and evaluated both in the context of dProlog and HAL. Finally, we explain the modifications needed by the trailing analysis in order to be combined with our modified PARMA trailing scheme. Empirical evidence shows that the combination is more effective than any of the techniques when used in isolation. To appear in Theory and Practice of Logic Programming.
Feasible Proofs of Matrix Properties with Csanky's Algorithm
Venue: arXiv cs.LO 2005
Year: 2005

We show that Csanky's fast parallel algorithm for computing the characteristic polynomial of a matrix can be formalized in the logical theory LAP, and can be proved correct in LAP from the principle of linear independence. LAP is a natural theory for reasoning about linear algebra introduced by Cook and Soltys. Further, we show that several principles of matrix algebra, such as linear independence or the Cayley-Hamilton Theorem, can be shown equivalent in the logical theory QLA. Applying the separation between complexity classes AC^0[2] contained in DET(GF(2)), we show that these principles are in fact not provable in QLA. In a nutshell, we show that linear independence is ``all there is'' to elementary linear algebra (from a proof complexity point of view), and furthermore, linear independence cannot be proved trivially (again, from a proof complexity point of view).
Approximate MAP Decoding on Tail-Biting Trellises
Venue: arXiv cs.IT 2005
Year: 2005

We propose two approximate algorithms for MAP decoding on tail-biting trellises. The algorithms work on a subset of nodes of the tail-biting trellis, judiciously selected. We report the results of simulations on an AWGN channel using the approximate algorithms on tail-biting trellises for the $(24,12)$ Extended Golay Code and a rate 1/2 convolutional code with memory 6.
Compressing Probability Distributions
Venue: arXiv cs.IT 2005
Year: 2005

We show how to store good approximations of probability distributions in small space.
Non prefix-free codes for constrained sequences
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we consider the use of variable length non prefix-free codes for coding constrained sequences of symbols. We suppose to have a Markov source where some state transitions are impossible, i.e. the stochastic matrix associated with the Markov chain has some null entries. We show that classic Kraft inequality is not a necessary condition, in general, for unique decodability under the above hypothesis and we propose a relaxed necessary inequality condition. This allows, in some cases, the use of non prefix-free codes that can give very good performance, both in terms of compression and computational efficiency. Some considerations are made on the relation between the proposed approach and other existing coding paradigms.
A Decision Feedback Based Scheme for Slepian-Wolf Coding of sources with Hidden Markov Correlation
Venue: arXiv cs.IT 2005
Year: 2005

We consider the problem of compression of two memoryless binary sources, the correlation between which is defined by a Hidden Markov Model (HMM). We propose a Decision Feedback (DF) based scheme which when used with low density parity check codes results in compression close to the Slepian Wolf limits.
The Workshop - Implementing Well Structured Enterprise Applications
Venue: arXiv cs.SE 2005
Year: 2005

We specify an abstraction layer to be used between an enterprise application and the utilized enterprise framework (like J2EE or .NET). This specification is called the Workshop. It provides an intuitive metaphor supporting the programmer in designing easy understandable code. We present an implementation of this specification. It is based upon the J2EE framework and is called the JWorkshop. As a proof of concept we implement a special certification authority called the Key Authority based upon the JWorkshop. The mentioned certification authority runs very successfully in a variety of different real world projects.
An MSE Based Ttransfer Chart to Analyze Iterative Decoding Schemes
Venue: arXiv cs.IT 2005
Year: 2005

An alternative to extrinsic information transfer (EXIT) charts called mean squared error (MSE) charts that use a measure related to the MSE instead of mutual information is proposed. Using the relationship between mutual information and minimum mean squared error (MMSE), a relationship between the rate of any code and the area under a plot of MSE versus signal to noise ratio (SNR) is obtained, when the log likelihood ratios (LLR) can be assumed to be from a Gaussian channel. Using this result, a theoretical justification is provided for designing concatenated codes by matching the EXIT charts of the inner and outer decoders, when the LLRs are Gaussian which is typically assumed for code design using EXIT charts. Finally, for the special case of AWGN channel it is shown that any capacity achieving code has an EXIT curve that is flat. This extends Ashikhmin et als results for erasure channels to the Gaussian channel.
A CDMA multiuser detection algorithm based on survey propagation
Venue: arXiv cs.IT 2005
Year: 2005

A computationally tractable CDMA multiuser detection algorithm is developed based on survey propagation.
Impersonation with the Echo Protocol
Venue: arXiv cs.CR 2005
Year: 2005

The Echo protocol tries to do secure location verification using physical limits imposed by the speeds of light and sound. While the protocol is able to guarantee that a certain object is within a certain region, it cannot ensure the authenticity of further messages from the object without using cryptography. This paper describes an impersonation attack against the protocol based on this weakness. It also describes a couple of approaches which can be used to defend against the attack.
Quantum Arthur-Merlin Games
Venue: arXiv cs.CC 2005
Year: 2005

This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.