ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection (1991)
    Springer
    Distributed computing 5 (1991), S. 67-71 
    Details
    ISSN: 1432-0452
    Keywords: Emulation ; Radio networks ; Collision detection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by $$O\left( {\left( {D + \log \frac{n}{\varepsilon }} \right)\log \Delta } \right)$$ rounds of the multi-hop network and succeeds with probability ≥1−ε. (n is the number of processors,D the diameter and Δ the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains ≦ε. A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02259748
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the complexity of computation in the presence of link failures: the case of a ring (1991)
    Springer
    Distributed computing 5 (1991), S. 121-131 
    Details
    ISSN: 1432-0452
    Keywords: Link failures ; Ring configuration ; Message complexity ; Lower bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We investigate the message complexity of distributed computations on rings of asynchronous processors. In such computations, each processor has an initial local value and the task is to compute some predetermined function of all local values. Our work deviates from previous works concerning the complexity of ring computations in that we consider the effect oflink failures. A link is said to fail if some message sent through it never reaches its destination. We show that the message complexity of any function, which is “sensitive to all its inputs”, is Θ (n logn) whenn, the number of processors, is a-priori known; and is Θ(n 2 ) whenn is not known. Interestingly, these tight bounds do not depend on whether the identity of a leader is a-priori known before the computation starts. These results stand in sharp contrast to the situation in asynchronous rings with no link failures, where the message complexity is affected by the a-priori knowledge of a leader but is not affected by the knowledge ofn.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02252955
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    An improved parallel algorithm for integer GCD (1990)
    Springer
    Algorithmica 5 (1990), S. 1-10 
    Details
    ISSN: 1432-0541
    Keywords: Greatest common divisor ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a simple parallel algorithm for computing the greatest common divisor (gcd) of twon-bit integers in the Common version of the CRCW model of computation. The run-time of the algorithm in terms of bit operations isO(n/logn), usingn 1+ɛ processors, where ɛ is any positive constant. This improves on the algorithm of Kannan, Miller, and Rudolph, the only sublinear algorithm known previously, both in run time and in number of processors; they requireO(n log logn/logn),n 2 log2 n, respectively, in the same CRCW model. We give an alternative implementation of our algorithm in the CREW model. Its run-time isO(n log logn/logn), usingn 1+ɛ processors. Both implementations can be modified to yield the extended gcd, within the same complexity bounds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840374
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Definitions and properties of zero-knowledge proof systems (1994)
    Springer
    Journal of cryptology 7 (1994), S. 1-32 
    Details
    ISSN: 1432-1378
    Keywords: Zero-knowledge ; Computational complexity ; Computational indistinguishability ; Cryptographic composition of protocols
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2]. We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00195207
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    On-line/off-line digital signatures (1996)
    Springer
    Journal of cryptology 9 (1996), S. 35-67 
    Details
    ISSN: 1432-1378
    Keywords: Digital signatures ; Integer factorization ; RSA ; DES ; One-time signature schemes ; Error-correcting codes ; Chosen message attack
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A new type of signature scheme is proposed. It consists of two phases. The first phase is performed off-line, before the message to be signed is even known. The second phase is performed on-line, once the message to be signed is known, and is supposed to be very fast. A method for constructing such on-line/off-line signature schemes is presented. The method uses one-time signature schemes, which are very fast, for the on-line signing. An ordinary signature scheme is used for the off-line stage. In a practical implementation of our scheme, we use a variant of Rabin's signature scheme (based on factoring) and DES. In the on-line phase all we use is a moderate amount of DES computation and a single modular multiplication. We stress that the costly modular exponentiation operation is performed off-line. This implementation is ideally suited for electronic wallets or smart cards.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02254791
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    How to construct constant-round zero-knowledge proof systems for NP (1996)
    Springer
    Journal of cryptology 9 (1996), S. 167-189 
    Details
    ISSN: 1432-1378
    Keywords: Zero-knowledge proofs ; NP ; Claw-free functions ; Commitment schemes ; Coin flipping protocols ; Parallel composition of proof systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Constant-round zero-knowledge proof systems for every language in $$\mathcal{N}\mathcal{P}$$ are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Blum integers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00208001
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A Sublinear Bipartiteness Tester for Bounded Degree Graphs (1999)
    Springer
    Combinatorica 19 (1999), S. 335-373 
    Details
    ISSN: 1439-6912
    Keywords: AMS Subject Classification (1991) Classes:  68Q25, 68R10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v''. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004930050060
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Testing Monotonicity (2000)
    Springer
    Combinatorica 20 (2000), S. 301-337 
    Details
    ISSN: 1439-6912
    Keywords: AMS Subject Classification (1991) Classes:  68Q25, 68R05, 68Q05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004930070011
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Bounds on tradeoffs between randomness and communication complexity (1993)
    Springer
    Computational complexity 3 (1993), S. 141-167 
    Details
    ISSN: 1420-8954
    Keywords: Communication Complexity ; Randomized Computation ; Complexity-Randomness tradeoff ; Lower bounds ; protocols ; 68Q22
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The power of randomness in improving the efficiency (or even possibility) of computations has been demonstrated in numerous contexts. A fundamental question ishow much randomness is required for these improvements, or how does the improvement grow as a function of the amount of randomness allowed. This quantitative question, restricted to the context of communication complexity, is the focus of our paper. We prove general lower bounds on the amount of randomness used in randomized protocols for computing a functionf, the input of which is split between two parties. The bounds depend on the number of bits communicated and the deterministic communication complexity off. Four models for communication complexity are considered: the random input of the parties may be public or private, and the communication may be one-way or two-way. (Unbounded advantage is allowed.) The bounds are shown to be tight; i.e., we demonstrate functions and protocols for these functions which meet the above bounds up to a constant factor. We do this for all the models, for all values of the deterministic communication complexity, and for all possible quantities of bits communicated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01200118
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Randomness in interactive proofs (1993)
    Springer
    Computational complexity 3 (1993), S. 319-354 
    Details
    ISSN: 1420-8954
    Keywords: Interactive proof systems ; Arthur-Merlin games ; randomness ; sampling methods ; expander graphs ; pairwise independence ; 68Q99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a randomness-efficient technique for decreasing the error probability. Given an AM proof system forL which achieves error probability 1/3 at the cost of Arthur sendingl(n) random bits per round, and given a polynomialk=k(n), we show how to construct an AM proof system forL which, in the same number of rounds as the original proof system, achieves error 2 −k(n) at the cost of Arthur sending onlyO(l+k) random bits per round. Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary functionf:{0,1} l → [0,1]. The method evaluates the function onO(∈−2 log γ−1) sample points generated using onlyO(l + log γ−1) coin tosses to get an estimate which with probability at least 1-δ is within ∈ of the average value of the function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01275487
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...