Search

Your search keyword '"Inria Bordeaux"' showing total 10 results
Start Over Author "Inria Bordeaux" Journal theoretical computer science
10 results on '"Inria Bordeaux"'

1. Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security

Author

Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I., Lithe and fast algorithmic number theory (LFANT), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Università degli studi di Catania = University of Catania (Unict), Exact Computing (ECO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Institute IMDEA Software [Madrid], The work of the first and third authors was supported by the French ANR SANGRIA project (ANR-21-CE39-0006). The work of the second author was in part support by the Programma ricerca di ateneo UNICT 2020-22 linea 2. The work ofthe third author was supported by the French PEPR Cybersecurité SecureCompute project (ANR-22-PECY-0003). The work of fifth author was supported by ERC (ERC-2020-COG)., ANR-21-CE39-0006,SANGRIA,Calcul réparti sécurisé : Cryptographie, Combinatoire, Calcul Formel(2021), ANR-22-PECY-0003,SecureCompute,Secure computations(2022), and European Project: 101001283,H2020-EU.1.1. - EXCELLENT SCIENCE - European Research Council (ERC),ERC-2020-COG,PICOCRYPT(2021)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], General Computer Science, Digital Signatures, Multi-Party Computation, EC-DSA, Threshold Cryptography, Provable Security, Class Groups, Theoretical Computer Science
Abstract

International audience; Due to their use in crypto-currencies, threshold ECDSA signatures have received much attention in recent years. Though efficient solutions now exist both for the two party, and the full threshold scenario, there is still much room for improvement, be it in terms of protocol functionality, strengthening security or further optimising efficiency. In the past few months, a range of protocols have been published, allowing for a non interactive-and hence extremely efficient-signing protocol; providing new features, such as identifiable aborts (parties can be held accountable if they cause the protocol to fail), fairness in the honest majority setting (all parties receive output or nobody does) and other properties. In some cases, security is proven in the strong simulation based model. We combine ideas from the aforementioned articles with the suggestion of Castagnos et al. (PKC 2020) to use the class group based CL framework so as to drastically reduce bandwidth consumption. Building upon this latter protocol we present a new, maliciously secure, full threshold ECDSA protocol that achieves additional features without sacrificing efficiency. Our most basic protocol boasts a non interactive signature algorithm and identifiable aborts. We also propose a more advanced variant that achieves adaptive security (for the n-out-of-n case) and proactive security. Our resulting constructions improve upon state of the art Paillier's based realizations achieving similar goals by up to a 10 factor in bandwidth consumption.

Published
2023
Full Text
View/download PDF

2. A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency

Author

Castagnos, Guilhem, Laguillaumie, Fabien, Tucker, Ida, Lithe and fast algorithmic number theory (LFANT), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Exact Computing (ECO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Institute IMDEA Software [Madrid], SCUM (ref. RTI2018-102043-B-I00), Spanish Government, CRYPTOEPIC (ref. EUR2019-103816), Spanish Government, SECURITAS (ref. RED2018-102321-T), Spanish Government, BLOQUES (ref. S2018/TCS-4339), Madrid Regional Government, ANR-21-CE39-0006,SANGRIA,Calcul réparti sécurisé : Cryptographie, Combinatoire, Calcul Formel(2021), and European Project: 101001283,H2020-EU.1.1. - EXCELLENT SCIENCE - European Research Council (ERC),ERC-2020-COG,PICOCRYPT(2021)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], General Computer Science, Functional encryption for inner products, Cryptography based on class groups of an imaginary quadratic field, Public key cryptography, Projective hash functions, Security proofs, Theoretical Computer Science
Abstract

International audience; Inner product functional encryption (IPFE) is a primitive which produces, from a master secret key, decryption keys sk k associated to vectors k over some specified base ring. Decrypting an encryption of vector m with sk k only reveals . Benhamouda et al. [BBL17] provided a generic construction for CCA-secure IPFE from projective hash functions (PHFs), unfortunately their security reduction suffers an exponential loss. Their only instantiation capable of decrypting inner products of large sizes, which relies on the decisional composite residuosity (DCR) assumption, is impractical due to the large size of ciphertexts, decryption keys, and the prohibitive speed of the scheme. Our core contribution is a new approach to proving CCA security. Our constructions maintain the genericity of [BBL17], while our security proof relaxes the requirements on the underlying PHFs and gains in reduction tightness. We instantiate these constructions from the DCR assumption, an assumption in class groups (HSM CL) and the decision Diffie Hellman (DDH) assumption. Our CCA-secure constructions from DCR and HSM CL are the first such schemes to efficiently decrypt inner products of large size, improving by multiple orders of magnitude upon the work of [BBL17]. A single-core C implementation of these schemes shows that, for a 112 bit security, and 100−dimensional vectors, their DCR-based scheme takes 1h20min to encrypt, and over 5min to decrypt, whereas our slowest scheme takes 5.2s to encrypt and 0.5s to decrypt. Similarly a ciphertext for their scheme is of 283MB; those of our HSM CL-based scheme are of 30kB.

Published
2022
Full Text
View/download PDF

3. Half-turn symmetric FPLs with rare couplings and tilings of hexagons

Author

Philippe Duchon, Jean-Christophe Aval, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Coupling, General Computer Science, Substitution tiling, 010102 general mathematics, Plane partition, tilings of hexagons, 0102 computer and information sciences, Expression (computer science), 01 natural sciences, Bijective proof, Theoretical Computer Science, Combinatorics, Loop (topology), Fully packed loop configurations, 010201 computation theory & mathematics, alternating sign matrices, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Turn (geometry), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Symmetry (geometry), Mathematics
Abstract

14 p.; International audience; In this work, we put to light a formula that relies the number of fully packed loop configurations (FPLs) associated to a given coupling pi to the number of half-turn symmetric FPLs (HTFPLs) of even size whose coupling is a punctured version of the coupling pi. When the coupling pi is the coupling with all arches parallel pi0 (the ''rarest'' one), this formula states the equality of the number of corresponding HTFPLs to the number of cyclically-symmetric plane partition of the same size. We provide a bijective proof of this fact. In the case of HTFPLs odd size, and although there is no similar expression, we study the number of HTFPLs whose coupling is a slit version of pi_0, and put to light new puzzling enumerative coincidence involving countings of tilings of hexagons and various symmetry classes of FPLs.

Published
2013
Full Text
View/download PDF

4. Synchronous black hole search in directed graphs

Author

Cristina M. Pinotti, Adrian Kosowski, Alfredo Navarra, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Dipartimento di Matematica e Informatica [Perugia] (DMI), Università degli Studi di Perugia (UNIPG), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Perugia = University of Perugia (UNIPG)

Subjects
Synchronous scheduler, General Computer Science, Graph searching problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Graph algorithms, Mobile agents in graphs, Graph searching problem, Black hole search problem, Theoretical Computer Science, Computer Science::Robotics, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Mobile agents in graphs, Black hole search problem, Graph algorithms, Communication complexity, Complement graph, Mathematics, Directed graph, Feedback arc set, 010201 computation theory & mathematics, Asynchronous communication, Distributed system, Graph (abstract data type), Robot, 020201 artificial intelligence & image processing, Computer Science(all)
Abstract

The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that G is a directed graph, the robots are associated with unique identifiers, they know the number of nodes n of G (or at least an upper bound on n), and they know the number of edges @D leading to the black holes. Each node is associated with a whiteboard where robots can read and write information in a mutual exclusive way. A recently posed question [J. Czyzowicz, S. Dobrev, R. Kralovic, S. Miklik, D. Pardubska, Black hole search in directed graphs, in: Proc. of 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO, LNCS, vol. 5869, 2009, pp. 182-194.] is whether some number of robots, expressed as a function of parameter @D only, is sufficient to detect black holes in directed graphs of arbitrarily large order n. We give a positive answer to this question for the synchronous case, i.e., when the robots share a common clock, showing that O(@D@?2^@D) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2^@D robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for @D=2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.

Published
2011
Full Text
View/download PDF

5. Remembering without memory: Tree exploration by asynchronous oblivious robots

Author

Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, Distributed Computing Research Group [Ottawa], University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Partially supported by NSERC Discovery grant. Andrzej Pelc is also partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow., and Alexander A. Shvartsman, Pascal Felber

Subjects
Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Constructive, Theoretical Computer Science, Combinatorics, Computer Science::Robotics, oblivious, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, asynchronous, Discrete mathematics, Degree (graph theory), Swarm behaviour, robot, Mobile robot, Binary logarithm, tree, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Asynchronous communication, Robot, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract

International audience; In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is {\sc Asynch} where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of {\em exploration}: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.

Published
2010
Full Text
View/download PDF

6. Fast radio broadcasting with advice

Author

David Ilcinkas, Andrzej Pelc, Dariusz R. Kowalski, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Liverpool], University of Liverpool, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow. Andrzej Pelc was partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais., and Alexander A. Shvartsman, Pascal Felber

Subjects
Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Theoretical Computer Science, Broadcasting (networking), Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Advice, Deterministic broadcasting, Computer Science::Information Theory, Distributed algorithm, business.industry, Radio network, Ask price, 010201 computation theory & mathematics, Order (business), Broadcast communication network, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Constant (mathematics), Radio broadcasting, Algorithm, Advice (complexity), Computer Science(all), Computer network
Abstract

International audience; We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with {\em advice}. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: $O(n)$ bits of advice are sufficient but $o(n)$ bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.

Published
2010
Full Text
View/download PDF

7. A randomized algorithm for the joining protocol in dynamic distributed networks

Author

Colin Cooper, Ralf Klasing, Tomasz Radzik, Department of Computer Science (DCS), King‘s College London, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Dynamic network analysis, General Computer Science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Joining protocol, Peer to peer networks, Overlay network, Self repairing networks, 0102 computer and information sciences, 02 engineering and technology, Security token, 01 natural sciences, Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Connectivity, Mathematics, Random graph, Randomized algorithm, Dynamic network, Random graph process, Neighbourhood (graph theory), 020206 networking & telecommunications, Vertex (geometry), 010201 computation theory & mathematics, Random walks, Computer Science(all), MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself.One model we consider is a network constructed in this fashion, in which vertices join but never leave. If t is the size of the network, then the diameter of the network is O(logt) for all t, with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t1/2+δ. With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.

Published
2008
Full Text
View/download PDF

8. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

Author

Ralf Klasing, Juraj Hromkovič, Guido Proietti, Dirk Bongartz, Sebastian Seibert, Hans-Joachim Böckenhauer, Walter Unger, Klasing, Ralf, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
General Computer Science, Spanning subgraph, Vertex connectivity, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, Minimum-cost biconnected spanning subgraph, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Graph algorithms, ComputingMilieux_MISCELLANEOUS, Minimum degree spanning tree, Mathematics, Discrete mathematics, Triangle inequality, Graph augmentation, Approximation algorithm, Approximation algorithms, Graph, Metric Graphs, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Graph factorization, Inapproximability, Computer Science(all)
Abstract

In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, for both the edge and the vertex connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval [1, 1 + e], for an arbitrary small e > 0. This result implies the first explicit lower bound on the approximability of the general version (i.e., for arbitrary graphs) of the problem. On the other hand, if the input graph satisfies the sharpened β-triangle inequality, then a (2/3 + 1/3 ċ β/1-β)-approximation algorithm is designed. This ratio tends to 1 with β tending to ½, and it improves the previous known bound of 3/2, holding for graphs satisfying the triangle inequality, as soon as β < 5/7Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of G by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened β-triangle inequality with β < 2/3, then this ratio can be improved to β/1-β.

Published
2004
Full Text
View/download PDF

9. Locating and repairing faults in a network with mobile agents

Author

Ralf Klasing, Tomasz Radzik, Colin Cooper, Department of Computer Science (DCS), King‘s College London, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Traverse, Brooks–Iyengar algorithm, General Computer Science, Deterministic algorithm, Computer science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Theoretical Computer Science, Software, Graph exploration, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, 021103 operations research, Forcing (recursion theory), business.industry, Distributed computing, Software agent, 010201 computation theory & mathematics, Robot, 020201 artificial intelligence & image processing, Mobile agents, business, Algorithm, Computer Science(all)
Abstract

We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronised steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Θ(n/k+D), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O(n/k+Dlogf/loglogf) steps, where f=min{n/k,n/D}, assuming that the number of faulty nodes is at most k/2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k/2 faults forcing the algorithm to work for Ω(n/k+Dlogf/loglogf) steps.

Full Text
View/download PDF

10. Proving weak properties of rewriting

Author

Hélène Kirchner, Isabelle Gnaedig, Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Completeness, Evaluation strategy, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.3: Deduction and Theorem Proving/I.2.3.1: Deduction (e.g., natural, rule-based), Rewriting, Theoretical computer science, General Computer Science, Computation, 0102 computer and information sciences, 02 engineering and technology, ACM: I.: Computing Methodologies/I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION/I.1.3: Languages and Systems/I.1.3.4: Substitution mechanisms, 01 natural sciences, Constructive, Theoretical Computer Science, Induction, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs/F.3.1.5: Specification techniques, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.3: Deduction and Theorem Proving/I.2.3.2: Inference engines, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification/D.2.4.3: Formal methods, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems, 0202 electrical engineering, electronic engineering, information engineering, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification/D.2.4.2: Correctness proofs, Narrowing, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs/F.3.1.3: Mechanical verification, Abstraction (linguistics), Mathematics, Backtracking, Weak termination, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.2: Automatic Programming/I.2.2.4: Program verification, ACM: D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.1: Formal Definitions and Theory, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs/F.3.1.2: Logics of programs, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.3: Deduction and Theorem Proving/I.2.3.4: Mathematical induction, 010201 computation theory & mathematics, Confluence, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.4: Software/Program Verification/D.2.4.8: Validation, 020201 artificial intelligence & image processing, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.2: Automatic Programming/I.2.2.0: Automatic analysis of algorithms, ACM: I.: Computing Methodologies/I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION/I.1.3: Languages and Systems/I.1.3.0: Evaluation strategies, Completeness (statistics), Abstraction
Abstract

International audience; In rule-based programming, properties of programs, such as termination, are in general considered in their strong acceptance i.e., on every computation branch. But in practice, they may hold in their weak acceptance only i.e., on at least one computation branch. Moreover, weak properties are often enough to ensure that programs give the expected result. There are very few results to handle weak properties of rewriting. We address here two of them: termination and reducibility to a constructor form, in a unified framework allowing us to prove them inductively. Proof trees are developed, which simulate rewriting trees by narrowing and abstracting subterms. Our technique is constructive in the sense that proof trees can be used to infer an evaluation strategy for any given input: the right computation branch is developed without using a costly breadth-first strategy nor backtracking.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results