arXiv
(422.153 recursos)
This is one of the most extensive subject based repositories in the world in the field of physics, mathematics, astronomy, computer sciences and quantitative biology. This is the principal site with almost 20 mirror versions around the globe. The site is supported by an extensive collection of information and background documentation. An RSS feed is available for anyone interested in keeping up-to-date with newly added materials.
Mostrando recursos 1 - 20 de 9.277
1.
Dancing links - Knuth, Donald E.
The author presents two tricks to accelerate depth-first search algorithms
for a class of combinatorial puzzle problems, such as tiling a tray by a fixed
set of polyominoes. The first trick is to implement each assumption of the
search with reversible local operations on doubly linked lists. By this trick,
every step of the search affects the data incrementally.
The second trick is to add a ghost square that represents the identity of
each polyomino. Thus puts the rule that each polyomino be used once on the same
footing as the rule that each square be covered once. The coding simplifies to
a more abstract form which...
2.
On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner - Goldwasser, Shafi
Madhu Sudan's work spans many areas of computer science theory including
computational complexity theory, the design of efficient algorithms,
algorithmic coding theory, and the theory of program checking and correcting.
Two results of Sudan stand out in the impact they have had on the mathematics
of computation. The first work shows a probabilistic characterization of the
class NP -- those sets for which short and easily checkable proofs of
membership exist, and demonstrates consequences of this characterization to
classifying the complexity of approximation problems. The second work shows a
polynomial time algorithm for list decoding the Reed Solomon error correcting
codes.
This short note will be devoted to...
3.
A Digital Signature with Threshold Generation and Verification - lal, Sunder; Kumar, Manoj
This paper proposes a signature scheme where the signatures are generated by
the cooperation of a number of people from a given group of senders and the
signatures are verified by a certain number of people from the group of
recipients. Shamir's threshold scheme and Schnorr's signature scheme are used
to realize the proposed scheme.
4.
A Directed -Threshold Multi-Signature Scheme - lal, Sunder; Kumar, Manoj
In this paper, we propose a Directed Threshold Multi-Signature Scheme. In
this threshold signature scheme, any malicious set of signers cannot
impersonate any other set of signers to forge the signatures. In case of
forgery, it is possible to trace the signing set. This threshold signature
scheme is applicable when the message is sensitive to the signature receiver;
and the signatures are generated by the cooperation of a number of people from
a given group of senders.
5.
A Directed Threshold - Signature Scheme - Lal, Sunder; Kumar, Manoj
Directed signature is the solution of such problems when the signed message
contains information sensitive to the signature receiver. Generally, in many
application of directed signature, the signer is generally a single person. But
when the message is on behalf of an organization, a valid sensitive message may
require the approval of several people. Threshold signature schemes are used to
solve these problems. This paper presents a threshold directed signature
scheme.
6.
Basic properties for sand automata - Cervelle, Julien; Formenti, Enrico; Masson, Benoit
We prove several results about the relations between injectivity and
surjectivity for sand automata. Moreover, we begin the exploration of the
dynamical behavior of sand automata proving that the property of nilpotency is
undecidable. We believe that the proof technique used for this last result
might reveal useful for many other results in this context.
7.
A Trace Logic for Local Security Properties - Corin, Ricardo; Durante, Antonio; Etalle, Sandro; Hartel, Pieter
We propose a new simple \emph{trace} logic that can be used to specify
\emph{local security properties}, i.e. security properties that refer to a
single participant of the protocol specification. Our technique allows a
protocol designer to provide a formal specification of the desired security
properties, and integrate it naturally into the design process of cryptographic
protocols. Furthermore, the logic can be used for formal verification. We
illustrate the utility of our technique by exposing new attacks on the well
studied protocol TMN.
8.
Efficient Algorithms for Large-Scale Topology Discovery - Donnet, Benoit; Raoult, Philippe; Friedman, Timur; Crovella, Mark
There is a growing interest in discovery of internet topology at the
interface level. A new generation of highly distributed measurement systems is
currently being deployed. Unfortunately, the research community has not
examined the problem of how to perform such measurements efficiently and in a
network-friendly manner. In this paper we make two contributions toward that
end. First, we show that standard topology discovery methods (e.g., skitter)
are quite inefficient, repeatedly probing the same interfaces. This is a
concern, because when scaled up, such methods will generate so much traffic
that they will begin to resemble DDoS attacks. We measure two kinds of
redundancy in probing (intra- and inter-monitor)...
9.
Bounded Input Bounded Predefined Control Bounded Output - Flikop, Ziny
The paper is an attempt to generalize a methodology, which is similar to the
bounded-input bounded-output method currently widely used for the system
stability studies. The presented earlier methodology allows decomposition of
input space into bounded subspaces and defining for each subspace its bounding
surface. It also defines a corresponding predefined control, which maps any
point of a bounded input into a desired bounded output subspace. This
methodology was improved by providing a mechanism for the fast defining a
bounded surface. This paper presents enhanced bounded-input
bounded-predefined-control bounded-output approach, which provides adaptability
feature to the control and allows transferring of a controlled system along a
suboptimal trajectory.
10.
Intelligent search strategies based on adaptive Constraint Handling Rules - Wolf, Armin
The most advanced implementation of adaptive constraint processing with
Constraint Handling Rules (CHR) allows the application of intelligent search
strategies to solve Constraint Satisfaction Problems (CSP). This presentation
compares an improved version of conflict-directed backjumping and two variants
of dynamic backtracking with respect to chronological backtracking on some of
the AIM instances which are a benchmark set of random 3-SAT problems. A CHR
implementation of a Boolean constraint solver combined with these different
search strategies in Java is thus being compared with a CHR implementation of
the same Boolean constraint solver combined with chronological backtracking in
SICStus Prolog. This comparison shows that the addition of ``intelligence'' to
the search process...
11.
Analysis of 802.11b MAC: A QoS, Fairness, and Performance Perspective - Sharma, Srikant
Wireless LANs have achieved a tremendous amount of growth in recent years.
Among various wireless LAN technologies, the IEEE 802.11b based wireless LAN
technology can be cited as the most prominent technology today. Despite being
widely deployed, 802.11b cannot be termed as a well matured technology.
Although 802.11b is adequate for basic connectivity and packet switching, It is
evident that there is ample scope for its improvement in areas like quality of
service, fairness, performance, security, etc. In this survey report, we
identify and argue that the Medium Access Controller for 802.11b networks is
the prime area for these improvements. To enunciate our claims we highlight
some of the...
12.
Programmable Ethernet Switches and Their Applications - Sharma, Srikant; Chiueh, Tzi-cker
Modern Ethernet switches support many advanced features beyond route learning
and packet forwarding such as VLAN tagging, IGMP snooping, rate limiting, and
status monitoring, which can be controlled through a programmatic interface.
Traditionally, these features are mostly used to statically configure a
network. This paper proposes to apply them as dynamic control mechanisms to
maximize physical network link resources, to minimize failure recovery time, to
enforce QoS requirements, and to support link-layer multicast without
broadcasting. With these advanced programmable control mechanisms, standard
Ethernet switches can be used as effective building blocks for
metropolitan-area Ethernet networks (MEN), storage-area networks (SAN), and
computation cluster interconnects. We demonstrate the usefulness of this new
level...
13.
Modules and Logic Programming - Fouquere, Christophe; Mogbil, Virgile
We study conditions for a concurrent construction of proof-nets in the
framework developed by Andreoli in recent papers. We define specific
correctness criteria for that purpose. We first study closed modules (i.e.
validity of the execution of a logic program), then extend the criterion to
open modules (i.e. validity during the execution) distinguishing criteria for
acyclicity and connectability in order to allow incremental verification.
14.
Security of public key cryptosystems based on Chebyshev Polynomials - Bergamo, Pina; D'Arco, Paolo; De Santis, Alfredo; Kocarev, Ljupco
Chebyshev polynomials have been recently proposed for designing public-key
systems. Indeed, they enjoy some nice chaotic properties, which seem to be
suitable for use in Cryptography. Moreover, they satisfy a semi-group property,
which makes possible implementing a trapdoor mechanism. In this paper we study
a public key cryptosystem based on such polynomials, which provides both
encryption and digital signature. The cryptosystem works on real numbers and is
quite efficient. Unfortunately, from our analysis it comes up that it is not
secure. We describe an attack which permits to recover the corresponding
plaintext from a given ciphertext. The same attack can be applied to produce
forgeries if the cryptosystem is...
15.
Logic Column 10: Specifying Confidentiality - Pucella, Riccardo
This article illustrates the use of a logical specification language to
capture various forms of confidentiality properties used in the security
literature.
16.
On Invariance and Convergence in Time Complexity theory - Moscu, Mircea Alexandru Popescu
This article introduces three invariance principles under which P is
different from NP. In the second part a theorem of convergence is proven. This
theorem states that for any language L there exists an infinite sequence of
languages from O(n) that converges to L.
17.
A Note on Bulk Quantum Turing Machine - Matsui, Tetsushi
Recently, among experiments for realization of quantum computers, NMR quantum
computers have achieved the most impressive succession. There is a model of the
NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing
Machine. It assumes, however, an unnatural assumption with quantum mechanics.
We, then, define a more natural and quantum mechanically realizable modified
bulk quantum Turing Machine, and show its computational ability by comparing
complexity classes with quantum Turing Machine's counter part.
18.
Impact of IT on Higher education Through Continuing Education - Shajeemohan, B. S.
Information Technology is emerging to be the technology of 21st century. The
paradigm shift from industrial society to information society had already
become a reality! It is indeed high time to think about integrating IT in all
facets of education -- may it be in secondary level, or be it in reskilling the
employed ones. This paper discusses various issues in incorporating IT in
various levels of education, and the need to think about a task force to
counter the so-called slow down and recession in IT industry. The opportunities
for aspiring IT professionals were also discussed. The importance of reskilling
as a continuing education programme to make...
19.
Usage Policy-based CPU Sharing in VOs - Dumitrescu, Catalin; Foster, Ian
Resource sharing within Grid collaborations usually implies specific sharing
mechanisms at participating sites. Challenging policy issues can arise within
virtual organizations (VOs) that integrate participants and resources spanning
multiple physical institutions. Resource owners may wish to grant to one or
more VOs the right to use certain resources subject to local policy and service
level agreements, and each VO may then wish to use those resources subject to
VO policy. Thus, we must address the question of what usage policies (UPs)
should be considered for resource sharing in VOs. As a first step in addressing
this question, we develop and evaluate different UP scenarios within a
specialized context that...
20.
Utilizing Reconfigurable Hardware Processors via Grid Services - Nathan, Darran; Clemens, Ralf
Computational grids typically consist of nodes utilizing ordinary processors
such as the Intel Pentium. Field Programmable Gate Arrays (FPGAs) are able to
perform certain compute-intensive tasks very well due to their inherent
parallel architecture, often resulting in orders of magnitude speedups. This
paper explores how FPGAs can be transparently exposed for remote use via grid
services, by integrating the Proteus Software Platform with the Globus Toolkit
3.0.
1.
