waashk/dblp huggingface dataset:
short fail-stop signature scheme based on factorization and discrete logarithm assumptions. fail-stop signature (fss) schemes protect a signer against a forger with unlimited computational power by enabling the signer to provide a proof of forgery, if it occurs. a decade after its invention, there have been several fss schemes proposed in the literature. nonetheless, the notion of short fss scheme has not been addressed yet. furthermore, the short size in signature schemes has been done mainly with the use of pairings. in this paper, we propose a construction of short fss scheme based on factorization and discrete logarithm assumption. however, in contrast to the known notion in the literature, our signature scheme does not incorporate any pairing operations. nonetheless, our scheme is the shortest fss scheme compared to all existing schemes in the literature that are based on the same assumption. the efficiency of our scheme is comparable to the best known fss scheme, that is based on the discrete logarithm assumption.
robust random number generation for peer-to-peer systems. we consider the problem of designing an efficient and robust distributed random number generator for peer-to-peer systems that is easy to implement and works even if all communication channels are public. a robust random number generator is crucial for avoiding adversarial join-leave attacks on peer-to-peer overlay networks. we show that our new generator together with a light-weight rule recently proposed in [b. awerbuch, c. scheideler, towards a scalable and robust dht, in: proc. of the 18th acm symp. on parallel algorithms and architectures, spaa, 2006. see also http://www14.in.tum.de/personen/scheideler] for keeping peers well distributed can keep various structured overlay networks in a robust state even under a constant fraction of adversarial peers.
on the bipanpositionable bipanconnectedness of hypercubes. a bipartite graph g is bipanconnected if, for any two distinct vertices x and y of g, it contains an [x,y]-path of length l for each integer l satisfying dg(x,y)&le;/&le;|v(g)|-1 and 2|(l-dg(x,y)), where dg(x,y) denotes the distance between vertices x and y in g and v(g) denotes the vertex set of g. we say a bipartite graph g is bipanpositionably bipanconnected if, for any two distinct vertices x and y of g and for any vertex z&isin;v(g)-{x,y}, it contains a path pl,k of length l such that x is the beginning vertex of pl,k, z is the (k+1)-th vertex of pl,k, and y is the ending vertex of pl,k for each integer l satisfying dg(x,z)+dg(y,z)&le;/&le;|v(g)|-1 and 2|(l-dg(x,z)-dg(y,z)) and for each integer k satisfying dg(x,z)&le;k&le;l-dg(y,z) and 2|(k-dg(x,z)). in this paper, we prove that an n-cube is bipanpositionably bipanconnected if n&ge;4. as a consequence, many properties of hypercubes, such as bipancyclicity, bipanconnectedness, bipanpositionable hamiltonicity, etc., follow directly from our result.
approximately optimal trees for group key management with batch updates. we investigate the group key management problem for broadcasting applications. previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. one model for batch rekeying is to assume that every user has probability p of being replaced by a new user during a batch period with the total number of users unchanged. under this model, it was recently shown that an optimal key tree can be constructed in linear time when p is a constant and in o(n^4) time when p->0. in this paper, we investigate more efficient algorithms for the case p->0, i.e., when membership changes are sparse. we design an o(n) heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. simulation results show that its performance is even better in practice. we also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1+@e for any fixed @e>0 and n, as p->0. finally, we give another approximation algorithm for any p@?(0,0.693) which is shown to be quite good by our simulations.
improving the average delay of sorting. in previous work we have introduced an average case measure for the time complexity of boolean circuits. instead of fixed circuit depth, for each input we take the minimal number of time steps necessary to perform the computation for that particular input using gates that forward their output values as soon as possible. this measure is called delay. based on it, the complexity of a whole class of functions that can be described as prefix computations has been analysed in detail. here we consider the problem to sort large integers that are given in binary notation. contrary to a word comparator sorting circuitc where a basic computational element, a comparator, is charged with a single time step to compare two elements, in a bit comparator circuitc^' a comparison of two binary numbers has to be implemented by a boolean subcircuit cm called comparator module that is built from boolean gates of bounded fanin. thus, compared to c, the depth of c^' will be larger by a factor up to the depth of cm. our goal is to minimize the average delay of bit comparator sorting circuits. the worst-case delay can be estimated by the depth of the circuit. for this worst-case measure two topologically quite different designs seem to be appropriate for the comparator modules: a tree-like one if the inputs are long numbers, otherwise a linear array working in a pipelined fashion. inserting these into a word comparator circuit we get bit level sorting circuits for binary numbers of length m, for which the depth is either increased by a multiplicative factor of order logm or by an additive term of order m. we show that these obvious solutions can be improved significantly by constructing efficient sorting and merging circuits for the bit model that only suffer a constant factor time loss on the average if the inputs are uniformly distributed. this is done by designing suitable hybrid architectures of tree compaction and pipelining. these results can also be extended to classes of nonuniform distributions if we put a bound on the complexity of the distributions themselves.
data aggregation in sensor networks: balancing communication and delay costs. in a sensor network the sensors, or nodes, obtain data and have to communicate these data to a central node. because sensors are battery powered they are highly energy constrained. data aggregation can be used to combine data of several sensors into a single message, thus reducing sensor communication costs at the expense of message delays. thus, the main problem of data aggregation is to balance the communication and delay costs. in this paper we study the data aggregation problem as a bicriteria optimization problem; the objectives we consider are to minimize maximum energy consumption of a sensor and a function of the maximum latency costs of a message. we consider distributed algorithms under a synchronous time model, under an asynchronous time model, and under an almost synchronous time model, where sensor clocks are synchronized up to a small drift. we use competitive analysis to assess the quality of the algorithms.
drawing slicing graphs with face areas. we consider orthogonal drawings of a plane graph g with specified face areas. for a natural number k, a k-gonal drawing of g is an orthogonal drawing such that the boundary of g is drawn as a rectangle and each inner face is drawn as a polygon with at most k corners whose area is equal to the specified value. in this paper, we show that every slicing graph g with a slicing tree t and a set of specified face areas admits a 10-gonal drawing d such that the boundary of each slicing subgraph that appears in t is also drawn as a polygon with at most 10 corners. such a drawing d can be found in linear time.
a generalization of thue freeness for partial words. this paper approaches the combinatorial problem of thue freeness for partial words. partial words are sequences over a finite alphabet that may contain a number of ''holes''. first, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. we find similar results for overlap-free partial words.
the antimagicness of the cartesian product of graphs. an antimagic labeling of a graph with m edges and n vertices is a bijection from the set of edges to the set {1,2,3,...,m} such that all the nvertex-sums are pairwise distinct, where the vertex-sum of a vertex v is the sum of labels of all edges incident with v. a graph is called antimagic if it has an antimagic labeling. the antimagicness of the cartesian product of graphs in several special cases has been studied [tao-ming wang, toroidal grids are anti-magic, in: proc. 11th annual international computing and combinatorics conference, coocoon'2005, in: lncs, vol. 3595, springer, 2005, pp. 671-679, yongxi cheng, a new class of antimagic cartesian product graphs, discrete mathematics 308 (24) (2008) 6441-6448]. in this paper, we develop new construction methods that are applied to more general cases. we prove that the cartesian product of paths is antimagic, if one of them has at least three edges. this (almost) answers the open problems in [yongxi cheng, lattice grids and prisms are antimagic, theoretical computer science 374 (2007) 66-73]. we also prove that the cartesian product of an antimagic regular graph and a connected graph is antimagic, which extends the results of the latter of the two references, where several special cases are studied.
graph searching with advice. fraigniaud et al. [l. blin, p. fraigniaud, n. nisse, s. vial, distributing chasing of network intruders, in: 13th colloquium on structural information and communication complexity, sirocco, in: lncs, vol. 4056, springer-verlag, 2006, pp. 70-84] introduced a new measure of difficulty for a distributed task in a network. the smallest number of bits of advice of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. in this variant of the problem, all searchers are initially placed at a particular node of the network. the aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. we show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is @q(nlogn), where n is the number of nodes of the network. more precisely, we first provide a labelling of the vertices of any graph g, using a total of o(nlogn) bits, and a protocol using this labelling that enables the optimal number of searchers to clear g in a monotone connected distributed way. then, we show that this number of bits of advice is optimal: any distributed protocol requires @w(nlogn) bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.
computational prediction of nucleic acid secondary structure: methods, applications, and challenges. rna molecules are crucial in different levels of cellular function, ranging from translation and regulating genes to coding for proteins. additionally, nucleic acids (rna and dna molecules) are designed for novel applications in biotechnology. understanding the structure of a molecule is important in inferring its function, and computational methods for structure prediction have captured the interest of many researchers. some functions of rna molecules in cells, such as gene regulation, result from the binding of one rna molecule to another, so-called target rna molecule. this has led to recent interest in prediction of the secondary structure formed from interacting molecules. in this paper, we provide a brief overview of methods, applications, and challenges in computational prediction of nucleic acid secondary structure, both for single strands and for interacting strands.
copower functors. we give a common generalization of two earlier constructions in [h.p. gumm, t. schroder, monoid-labeled transition systems, electronic notes in theoretical computer science 44 (1) (2001) 184-203], that yielded coalgebraic type functors for weighted, resp. fuzzy transition systems. transition labels for these systems were drawn from a commutative monoid m or a complete semilattice l, with the transition structure interacting with the algebraic structure on the labels. here, we show that those earlier signature functors are in fact instances of a more general construction, provided by the so-called copower functor. exemplary, we instantiate this functor in categories given by varieties v of algebras. in particular, for the variety s of all semigroups, or the variety m of all (not necessarily commutative) monoids, and with m any monoid, we find that the resulting copower functors m"s[-] (resp m"m[-]) weakly preserve pullbacks if and only if m is equidivisible (resp. conical and equidivisible). finally, we show that copower functors are universal in the sense that every faithful set-functor can be seen as an instance of an appropriate copower functor.
executability of scenarios in petri nets. in this paper, we show that it can be tested in polynomial time as to whether a scenario is an execution of a petri net. this holds for a wide variety of petri net classes, ranging from elementary nets to general inhibitor nets. scenarios are given by causal structures expressing causal dependencies and concurrency among events. in the case of elementary nets and of place/transition nets, such causal structures are partial orders among transition occurrences. for several extended petri net classes, the extension of partial orders to stratified order structures is considered. the algorithms are based on the representation of the non-sequential behavior of petri nets by so-called token flow functions and a characterization of petri net executions called token flow property. this property allows nontrivial transformations into flow optimization problems, which can be solved in polynomial time. the paper is a revised, consolidated and extended version of the conference papers [g. juhas, r. lorenz, j. desel, can i execute my scenario in your net?, in: g. ciardo, p. darondeau (eds.), icatpn, in: lecture notes in computer science, springer, 2005, pp. 289-308; r. lorenz, s. mauser, r. bergenthum, testing the executability of scenarios in general inhibitor nets, in: acsd, ieee computer society, 2007, pp. 167-176] and includes parts of the habilitation thesis [r. lorenz, szenario-basierte verifikation und synthese von perinetzen: theorie und anwendungen, habilitation, 2006].
treewidth and logical definability of graph products. in this paper we describe an algorithm that, given a tree-decomposition of a graph g and a tree-decomposition of a graph h, provides a tree-decomposition of the cartesian product of g and h. using this algorithm, we derive upper bounds on the treewidth (resp. on the pathwidth) of the cartesian product of two graphs, expressed in terms of the treewidth (resp. pathwidth) and the size of the factor graphs. in the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and that the cartesian product by a finite set of connected graphs preserves ms"1-definability and ms"2-definability. we also prove that the cartesian product of two ms"2-definable classes of connected graphs is ms"2-definable.
computational expressiveness of genetic systems. we introduce genetic systems, a formalism inspired by genetic regulatory networks and suitable for modeling the interactions between the genes and the proteins, acting as regulatory products. the generation of new objects, representing proteins, is driven by genetic gates: a new object is produced when all the activator objects are available in the system, and no inhibitor object is available. activators are not consumed by the application of such an evolution rule. objects disappear because of degradation: each object is equipped with a lifetime, and the object decays when such a lifetime expires. we investigate the computational expressiveness of genetic systems: we show that they are turing equivalent by providing encodings of random access machines in genetic systems.
on the pseudo-achromatic number problem. we study the parameterized complexity of the pseudo-achromatic number problem: given an undirected graph and a parameter k, determine if the graph can be partitioned into k groups such that every two groups are connected by at least one edge. this problem has been extensively studied in graph theory and combinatorial optimization. we show that the problem has a kernel of at most (k-2)(k+1) vertices that is constructable in time o(mn), where n and m are the number of vertices and edges, respectively, in the graph, and k is the parameter. this directly implies that the problem is fixed-parameter tractable. we also study generalizations of the problem and show that they are parameterized intractable.
membrane computing with transport and embedded proteins. in this paper, we look at the expressive power of p systems with proteins embedded on the membranes. the rules governing the evolution of the embedded proteins are inspired from brane calculi. we use some basic operations of brane calculi, namely, exo, endo, bud, mate, pino, wrap in the formalism of membrane computing. we also use rules allowing the movement of proteins, to pass through membranes and attach to and detach from the membranes. combining the two kinds of operations, namely, brane calculi operations as well as protein movement operations, we have obtained some universality results of p systems. we have also identified some decidable sub-classes of p systems by restricting the use of the protein movement rules.
on existence of reporter strands in dna-based graph structures. through self-assembly of branched junction molecules many different dna structures (graphs) can be assembled. we show that every multigraph can be assembled by dna such that there is a single strand that traces each edge in the graph at least once. this strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. this boundary component traverses every edge at least once, and it defines a circular path in the graph that ''preserves the graph structure'' and traverses each edge.
linear-size log-depth negation-limited inverter for k-tonic binary sequences. in negation-limited complexity, one considers circuits with a limited number of not gates, being motivated by the gap in our understanding of monotone versus general circuit complexity. in this context, the study of inverters, i.e., circuits with inputs x"1,...,x"n and outputs @?x"1,...,@?x"n, is fundamental since an inverter with r nots can be used to convert a general circuit to one with only r nots. beals, nishino, and tanaka [r. beals, t. nishino, k. tanaka, on the complexity of negation-limited boolean networks, siam journal on computing 27 (5) (1998) 1334-1347. a preliminary version appears in: proceedings of stoc95: the 27th annual acm symposium on theory of computing, 1995, pp. 585-595] gave a construction of an n-inverter with size o(nlogn), depth o(logn), and @?log"2(n+1)@? nots. a zero-one sequence x"1,...,x"n is k-tonic if the number of i's such that x"i
two semi-online scheduling problems on two uniform machines. this paper considers two semi-online scheduling problems, one with known optimal value and the other with known total sum, on two uniform machines with a machine speed ratio of s&ge;1. for the first problem, we provide an optimal algorithm for s&isin;[1+&radic;3/2, 1+&radic;21/4], and improved algorithms or/and lower bounds for s&isin;[1+&radic;21/4, &radic;3], over which the optimal algorithm is unknown. as a result, the largest gap between the competitive ratio and the lower bound decreases to 0.02192. for the second problem, we also present algorithms and lower bounds for s&ge;1. the largest gap between the competitive ratio and the lower bound is 0.01762, and the length of the interval over which the optimal algorithm is unknown is 0.47382. our algorithms and lower bounds for these two problems provide insights into their differences, which are unusual from the viewpoint of the known results on these two semi-online scheduling problems in the literature.
path finding in the tile assembly model. swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. the canonical problems for such biologically-inspired systems are shape assembly and path finding. in this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. as in related work, our systems function in the presence of obstacles and can be made fault-tolerant. the path-finding systems use @q(1) distinct components and find minimal-length paths in time linear in the length of the path.
optimal conclusive sets for comparator networks. a set of input vectors s is conclusive for a certain functionality if, for every comparator network, correct functionality for all input vectors is implied by correct functionality for all vectors in s. we consider four functionalities of comparator networks: sorting, merging, sorting of bitonic vectors, and halving. for each of these functionalities, we present two conclusive sets of minimal cardinality. the members of the first set are restricted to be binary, while the members of the second set are unrestricted. for all the above functionalities, except halving, the unrestricted conclusive set is much smaller than the binary one.