共查询到20条相似文献,搜索用时 31 毫秒
1.
Coupling and self-stabilization 总被引:1,自引:0,他引:1
A randomized self-stabilizing algorithm
is an algorithm that, whatever the initial configuration is, reaches a set
of М legal configurations} in finite time with probability 1. The proof of convergence towards
is generally done by exhibiting a potential function
, which measures the “vertical” distance of any configuration to
, such that
decreases with non-null probability at each step of
. We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance
between any pair of configurations, such that
decreases in expectation at each step of
. In contrast with classical methods, our coupling method does not require the knowledge of
. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different
measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as
examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. 相似文献
2.
3.
ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT 总被引:1,自引:1,他引:0
Shuchi Chawla Robert Krauthgamer Ravi Kumar Yuval Rabani D. Sivakumar 《Computational Complexity》2006,15(2):94-114
4.
Emanuele Viola 《Computational Complexity》2005,13(3-4):147-188
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function
computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant
such that every circuit of size
fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a
computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies
under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function
(i.e. there is a constant
such that every circuit of size
fails to compute f on some input) for every positive constant
there is no black-box construction of a
computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes. 相似文献
5.
A graph G with n vertices and maximum degree
cannot be given weak sense of direction using less than
colours. It is known that n colours are always sufficient, and it was conjectured that just
are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring
more colours than
. In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that
colours are necessary, where d
G
is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000. 相似文献
6.
7.
Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional
to binary decision diagram) that each variable is tested at most once during the computation. The function EARn is the following Boolean function defined for n × n Boolean matrices: EARn(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EARn has size at least
and we present a construction of such diagrams of size approximately
. 相似文献
8.
Every Linear Threshold Function has a Low-Weight Approximator 总被引:1,自引:1,他引:0
Rocco A. Servedio 《Computational Complexity》2007,16(2):180-209
9.
Given a k-uniform hypergraph, the Maximum k -Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within
a factor of
unless P = NP. This improves the previous hardness of approximation factor of
by Trevisan. This result extends to the problem of k-Dimensional-Matching. 相似文献
10.
11.
12.
Eric Allender Anna Bernasconi Carsten Damm Joachim von zur Gathen Michael Saks Igor Shparlinski 《Computational Complexity》2003,12(1-2):23-47
We study various combinatorial complexity measures of
Boolean functions related to some natural arithmetic problems about
binary polynomials, that is, polynomials over
.
In particular, we consider
the Boolean function deciding whether a given polynomial over
is squarefree. We obtain an exponential lower bound on the size of a
decision tree for this function, and derive an asymptotic formula, having
a linear main term, for its average sensitivity. This allows us to estimate
other complexity characteristics such as the formula size, the average decision
tree depth and the degrees of exact and approximative polynomial
representations of this function. Finally, using a different method, we
show that testing squarefreeness and irreducibility of polynomials over
cannot be done in
for any odd prime p. Similar results are
obtained for deciding coprimality of two polynomials over
as well. 相似文献
13.
On Defining Integers And Proving Arithmetic Circuit Lower Bounds 总被引:1,自引:1,他引:0
Peter Bürgisser 《Computational Complexity》2009,18(1):81-103
14.
The condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies
conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification
of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following
hierarchy
where
includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition
, we have:
After having established the complete hierarchy, the paper concentrates on the two last items:
. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition
(such that
) is d +1.
In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following
properties. Let f be the number of actual crashes, I the input vector and
the condition the protocol is instantiated with. The protocol terminates in two rounds when
and
, and in at most d +1 rounds when
and
. (It also terminates in one round when
and
.) Moreover, whether I belongs or not to C, no process requires more than min
rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when
(for
and
).
This paper is based on the DISC’03 and DISC’04 conference versions MRR03,MRR04
A. Mostefaoui is currently Associate Professor at the Computer Science Department of the University of Rennes, France. He received his
Engineer Degree in Computer Science in 1990 from the University of Algiers, and a Ph.D. in Computer Science in 1994 from the
University of Rennes, France. His research interests include fault-tolerance and synchronization in distributed systems, group
communication, data consistency and distributed checkpointing. Achour Mostefaoui has published more than 70 scientific publications
and served as a reviewer for more than 20 major journals and conferences. Moreover, Achour Mostéfaoui is heading the software
engineer degree of the University of Rennes
S. Rajsbaum received a degree in Computer Engineering from the National Autonomous University of Mexico (UNAM) in 1985, and a PhD in
the Computer Science from the Technion, Israel, in 1991. Since then he has been a member of the Institute of Mathematics at
UNAM, where he is now a Full Professor with Tenure. He has been a regular visiting scientist at the Laboratory for Computer
Science of MIT. Also, he was a member of the Cambridge Research Laboratory of HP from 2000 to 2002. He was chair of the program
committee for Latin American Theoretical Informatics LATIN2002, and for ACM Principles of Distributed Computing PODC03, and
member of the Program Committee of various international conferences such as ADHOC, DISC, ICDCS, IPDPS, LADC, PODC, and SIROCCO.
His research interests are in the theory of distributed computing, especially issues related to coordination, complexity and
computability, and fault-tolerance. He has also published in graph theory and algorithms. Overall, he has published over fifty
papers in journals and international conferences. He runs the Distributed Computing Column of SIGACT News, the newsletter
of the ACM Special Interest Group on Algorithms and Computation Theory. He has been editor of several special journal issues,
such as the Special 20th PODC Anniversary Special Issue of Distributed Computing Journal (with H. Attiya) and of Computer
Networks journal special issue on algorithms.
M. Raynalhas been a professor of computer science since 1981. At IRISA (CNRS-INRIA-University joint computing research laboratory located
in Rennes), he founded a research group on Distributed Algorithms in 1983. His research interests include distributed algorithms,
distributed computing systems, networks and dependability. His main interest lies in the fundamental principles that underly
the design and the construction of distributed computing systems. He has been Principal Investigator of a number of research
grants in these areas, and has been invited by many universities all over the world to give lectures on distributed algorithms
and distributed computing. He belongs to the editorial board of several international journals. Professor Michel Raynal has
published more than 90 papers in journals (JACM, Acta Informatica, Distributed Computing, Comm. of the ACM, Information and
Computation, Journal of Computer and System Sciences, JPDC, IEEE Transactions on Computers, IEEE Transactions on SE, IEEE
Transactions on KDE, IEEE Transactions on TPDS, IEEE Computer, IEEE Software, IPL, PPL, Theoretical Computer Science, Real-Time
Systems Journal, The Computer Journal, etc.); and more than 190 papers in conferences (ACM STOC, ACM PODC, ACM SPAA, IEEE
ICDCS, IEEE DSN, DISC, IEEE IPDPS, Europar, FST&TCS, IEEE SRDS, etc.). He has also written seven books devoted to parallelism,
distributed algorithms and systems (MIT Press and Wiley). Michel Raynal has served in program committees for more than 70
international conferences (including ACM PODC, DISC, ICDCS, IPDPS, DSN, LADC, SRDS, SIROCCO, etc.) and chaired the program
committee of more than 15 international conferences (including DISC -twice-, ICDCS, SIROCCO and ISORC). He served as the chair
of the steering committee leading the DISC symposium series in 2002-2004. Michel Raynal received the IEEE ICDCS best paper
Award three times in a row: 1999, 2000 and 2001. He is a general co-chair of the IEEE ICDCS conference that will be held in
Lisbon in 2006. 相似文献
– | For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t. |
– | For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t. |
– | For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t. |
– | d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system. |
15.
16.
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in
and
bit operations; here
denotes the largest entry in absolute value and the exponent adjustment by +o(1) captures additional factors
for positive real constants C1, C2, C3. The bit complexity
results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n3.2+o(1) and O(n2.697263) ring additions, subtractions and multiplications.To B. David Saunders on the occasion of his 60th birthday 相似文献
17.
Leszek Gąsieniec Erez Kantor Dariusz R. Kowalski David Peleg Chang Su 《Distributed Computing》2008,21(2):117-127
The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy.
The radio network is modelled as an undirected graph G = (V, E) where |V| = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting
in rounds. Moreover, if we allow each node to transmit at most k times, the lower bound on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in rounds. The paper concludes with a number of open problems in the area.
The research of L. Gąsieniec, D.R. Kowalski and C. Su supported in part by the Royal Society grant Algorithmic and Combinatorial Aspects of Radio Communication, IJP - 2006/R2.
The research of E. Kantor and D. Peleg supported in part by grants from the Minerva Foundation and the Israel Ministry of
Science. 相似文献
18.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion
, where
is a compact set of matrices, is asymptotically stable if and only if
can be extended to a set
of nonnegative matrices B with
or
. Similar results are derived for differential inclusions. 相似文献
19.
Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting
cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are
emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important
issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language (
-
) presented in this paper addresses this issue dealing with crash failures of agents.
-
provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open
MAS. We present a formal semantics for
-
and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies
a set of well defined knowledge-level programming requirements. To illustrate the language features we show how
-
can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net
one. 相似文献
20.
R. F. Streater 《Open Systems & Information Dynamics》2004,11(4):359-375
Let H0 be a selfadjoint operator such that Tr
is of trace class for some
, and let
denote the set of ε-bounded forms, i.e.,
for some
0 $$" align="middle" border="0">
. Let χ := Span
. Let
denote the underlying set of the quantum information manifold of states of the form
. We show that if Tr
,
Presented at the 36th Symposium on Mathematical Physics, ‘Open Systems & Quantum Information’, Toruń, Poland, June 9-12, 2004. 相似文献
1. | the map Φ,
| |
2. | The Orlicz space defined by Φ is the tangent space of at ρ0; its affine structure is defined by the (+1)-connection of Amari | |
3. | The subset of a ‘hood of ρ0, consisting of p-nearby states (those obeying for some 1$$" align="middle" border="0"> ) admits a flat affine connection known as the (-1) connection, and the span of this set is part of the cotangent space of | |
4. | These dual structures extend to the completions in the Luxemburg norms. |