waashk/dblp huggingface dataset:
enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions. rabi and sherman [m. rabi, a. sherman, an observation on associative one-way functions in complexity theory, information processing letters 64 (5) (1997) 239-244; m. rabi, a. sherman, associative one-way functions: a new paradigm for secret-key agreement and digital signatures, tech. rep. cs-tr-3183/umiacs-tr-93-124, department of computer science, university of maryland, college park, md, 1993] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. in this paper we improve the sufficient condition to pnp. we look at the four attributes used in rabi and sherman's seminal work on algebraic properties of one-way functions (see [m. rabi, a. sherman, an observation on associative one-way functions in complexity theory, information processing letters 64 (5) (1997) 239-244; m. rabi, a. sherman, associative one-way functions: a new paradigm for secret-key agreement and digital signatures, tech. rep. cs-tr-3183/umiacs-tr-93-124, department of computer science, university of maryland, college park, md, 1993]) and subsequent papers-strongness (of noninvertibility), totality, commutativity, and associativity-and for each attribute, we allow it to be required to hold, required to fail, or ''don't care''. in this categorization there are 3^4=81 potential types of one-way functions. we prove that each of these 81 feature-laden types stands or falls together with the existence of (plain) one-way functions.
approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length. given a forest f=(v,e) and a positive integer d, we consider the problem of finding a minimum number of new edges e^' such that in the augmented graph h=(v,e@?e^') any pair of vertices can be connected by two vertex-disjoint paths of length @?d. we show that this problem and some of its variants are np-hard, and we present approximation algorithms with worst-case bounds 6 and 4. these algorithms can be implemented in o(|v|log|v|) time.
convergence of the diffusion method for weighted torus graphs using fourier analysis. this paper studies the diffusion method for the load balancing problem in the case of weighted torus graphs. closed form formulae for the optimum values of the edge weights are determined using local fourier analysis. it is shown that an extrapolated version of diffusion can become twice as fast for the stretched torus graphs.
generalising submodularity and horn clauses: tractable optimization problems defined by tournament pair multimorphisms. the submodular function minimization problem (sfm) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. the most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. in this paper we demonstrate that this general form of sfm is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. these tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a tournament pair multimorphism. this larger tractable class also includes the problem of satisfying a set of horn clauses (horn-sat), as well as various extensions of this problem to larger finite domains.
a near optimal scheduler for on-demand data broadcasts. on-demand data broadcasting is a new and important technique for information dissemination. in this paper, we design and analyse a novel online scheduler balance for scheduling on-demand data broadcasts. balance has competitive ratio 6@dlog@d+o(@d^5^/^6), which improves significantly the previous best upper bound of @d+@d+2. we also prove that any online scheduler for the problem cannot have competitive ratio smaller than @d2ln@d-1. it follows that balance is optimal within a constant factor.
optimizing deletion cost for secure multicast key management. multicast and broadcast are efficient ways to deliver messages to a group of recipients in a network. due to the growing security concerns in various applications, messages are often encrypted with a secret group key. the key tree model which has been widely adopted maintains a set of keys in a tree structure so that in case of group member change, the group key can be updated in a secure and efficient way. in this paper, we focus on the updating cost incurred by member deletions. to implement a sequence of member deletions in any key tree, a certain number of encrypted messages need to be broadcast to accomplish the updates. our goal is to identify the best key tree which can minimize the worst-case deletion cost (i.e., the amortized cost over n member deletions). we prove that there is an optimal tree in which each internal node has at most five children and each internal node with at least one non-leaf child has exactly three children. based on these characterizations, we present a dynamic programming algorithm that computes an optimal key tree in o(n^2) time.
the complexity of uniform nash equilibria and related regular subgraph problems. we investigate the complexity of finding nash equilibria in which the strategy of each player is uniform on its support set. we show that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an np-complete problem. our proof is graph-theoretical. motivated by this result, we also give np-completeness results for the problems of finding regular induced subgraphs of large size or regularity, which can be of independent interest.
seeing the trees and their branches in the network is hard. phylogenetic networks are a restricted class of directed acyclic graphs that model evolutionary histories in the presence of reticulate evolutionary events, such as horizontal gene transfer, hybrid speciation, and recombination. characterizing a phylogenetic network as a collection of trees and their branches has long been the basis for several methods of reconstructing and evaluating phylogenetic networks. further, these characterizations have been used to understand molecular sequence evolution on phylogenetic networks. in this paper, we address theoretical questions with regard to phylogenetic networks, their characterizations, and sequence evolution on them. in particular, we prove that the problem of deciding whether a given tree is contained inside a network is np-complete. further, we prove that the problem of deciding whether a branch of a given tree is also a branch of a given network is polynomially equivalent to that of deciding whether the evolution of a molecular character (site) on a network is governed by the infinite site model. exploiting this equivalence, we establish the np-completeness of both problems, and provide a parameterized algorithm that runs in time o(2^k^/^2n^2), where n is the total number of nodes and k is the number of recombination nodes in the network, which significantly improves upon the trivial brute-force o(2^kn) time algorithm for the problem. this reduction in time is significant, particularly when analyzing recombination hotspots.
analysis of set-up time models: a metric perspective. we consider model based estimates for set-up time. the general setting we are interested in is the following: given a disk and a sequence of read/write requests to certain locations, we would like to know the total time of transitions (set-up time) when these requests are served in an orderly fashion. the problem becomes nontrivial when we have, as is typically the case, only the counts of requests to each location rather then the whole input, and we can only hope to estimate the required time. models that estimate set-up time have been suggested and heavily used as far back as the sixties. however, not much theory exists to enable a qualitative understanding of such models. to this end we introduce several properties such as (i) super-additivity which means that the set-up time estimate decreases as the input data is refined (ii) monotonicity which means that more activity produces more set-up time, (iii) dominance which means that one model always produces higher estimates than a second model and (iv) approximation guarantees for the estimate with respect to the worst possible time, by which we can study different models. we provide criteria for super-additivity and monotonicity to hold for popular models such as the partial markov model (pmm). the criteria show that the estimate produced by these models will be monotone for any reasonable system. we also show that the independent reference model (irm) based estimate functions as a worst case estimate in the sense that the estimate is guaranteed to be at least half of the actual set-up time. we also show that it dominates the pmm based estimates. using our criteria we prove that pmm based estimates are always super additive when applied to the special metrics that correspond to seek times of disk drives. to establish our theoretical results we use the theory of finite metric spaces, and en route show a result of independent interest in that theory, which is a strengthening of a theorem of j.b. kelly [j.b. kelly, hypermetric spaces and metric transforms, in: o. shisha (ed.), inequalities iii, 1972, pp. 149-158] about the properties of metrics that are formed by concave functions on the line.
how many runs can a string contain? given a string x=x[1..n], a repetition of period p in x is a substring u^r=x[i+1..i+rp], p=|u|, r>=2, where neither u=x[i+1..i+p] nor x[i+1..i+(r+1)p+1] is a repetition. the maximum number of repetitions in any string x is well known to be @q(nlogn). a run or maximal periodicity of period p in x is a substring u^rt=x[i+1..i+rp+|t|] of x, where u^r is a repetition, t a proper prefix of u, and no repetition of period p begins at position i of x or ends at position i+rp+|t|+1. in 2000 kolpakov and kucherov showed that the maximum number @r(n) of runs in any string x[1..n] is o(n), but their proof was nonconstructive and provided no specific constant of proportionality. at the same time, they presented experimental data to prompt the conjecture: @r(n)
a randomized competitive algorithm for evaluating priced and/or trees. recently, charikar et al. investigated the problem of evaluating and/or trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. for an and/or tree t they presented a @m(t)-competitive deterministic polynomial time algorithm, where @m(t) is the number of leaves that must be read, in the worst case, in order to determine the value of t. furthermore, they proved that @m(t) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. the power of randomization in this context has remained as an open question. here, we take a step towards solving this problem by presenting a 56@m(t)-competitive randomized polynomial time algorithm. this contrasts with the best known lower bound @m(t)/2.
self-deployment of mobile sensors on a ring. mobile sensors can self-deploy in a purely decentralized and distributed fashion, so as to reach in a finite time a state of static equilibrium in which they uniformly cover the environment. we consider the self-deployment problem in a ring (e.g., a circular rim); in particular we investigate under what conditions the problem is solvable by a collection of identical sensors without a global coordinate system, however capable of determining the location (in their local coordinate system) of the other sensors within a fixed distance (called visibility radius). a self-deployment is exact if within finite time the distance between any two consecutive sensors along the ring is the same, d; it is @e-approximate if within finite time the distance between two consecutive sensors is between d-@e and d+@e. we prove that exact self-deployment is impossible if the sensors do not share a common orientation of the ring. this impossibility result holds even if the sensors have unlimited memory of the past, their visibility radius is unlimited, and all their actions, when active, are instantaneous. we thus consider the problem in an oriented ring. we prove that if the sensors know the desired final distance d, then exact self-deployment is possible. if the desired final distance d is not known, we prove that @e-approximate self-deployment is possible for any chosen @e>0. the proofs of these results are constructive. in each case we present a simple protocol that allows the sensors to achieve the claimed level of self-deployment. these positive results hold even if sensors are oblivious (i.e., have no memory of past actions and computations), asynchronous (i.e., a sensor becomes active at unpredictable times and the duration of its actions is unpredictable), and have limited visibility radius. our protocols can be employed, without modifications, on the perimeter of any convex region.
efficient sensor network design for continuous monitoring of moving objects. we study the problem of localizing and tracking multiple moving targets in wireless sensor networks, from a network design perspective i.e. towards estimating the least possible number of sensors to be deployed, their positions and operation characteristics needed to perform the tracking task. to avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. under this model, we abstract the tracking network design problem by a combinatorial problem of covering a universe of elements by at least three sets (to ensure that each point in the network area is covered at any time by at least three sensors, and thus being localized). we then design and analyze an efficient approximate method for sensor placement and operation, that with high probability and in polynomial expected time achieves a @q(logn) approximation ratio to the optimal solution. our network design solution can be combined with alternative collaborative processing methods, to suitably fit different tracking scenarios.
integration of a security type system into a program logic. type systems and program logics are often thought to be at opposing ends of the spectrum of formal software analyses. in this paper we show that a flow-sensitive type system ensuring non-interference in a simple while-language can be expressed through specialised rules of a program logic. in our framework, the structure of non-interference proofs resembles the corresponding derivations in a state-of-the-art security type system, meaning that the algorithmic version of the type system can be used as a proof procedure for the logic. we argue that this is important for obtaining uniform proof certificates in a proof-carrying code framework. we discuss in which cases the interleaving of approximative and precise reasoning allows us to deal with delimited information release. finally, we present ideas on how our results can be extended to encompass features of realistic programming languages such as java.
memoryless search algorithms in a network with faulty advice. in this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t of a network, without prior knowledge of its exact location. each node of the network has a database that will answer queries of the form ''how do i find t?'' by responding with the first edge on a shortest path to t. it may happen that some nodes, called liars, give bad advice. we investigate a simple memoryless algorithm which follows the advice with some fixed probability q>1/2 and otherwise chooses a random edge. if the degree of each node and number of liars k are bounded, we show that the expected number of edges traversed by the agent before finding t is bounded from above by o(d+r^k), where d is the distance between the initial and target nodes and r=q1-q. we also show that this expected number of steps can be significantly improved for particular topologies such as the complete graph and the torus.
security types for dynamic web data. we describe a type system for the xd@p calculus of gardner and maffeis. an xd@p-network is a network of locations, where each location consists of both a data tree (which contains scripts and pointers to nodes in trees at different locations) and a process, for modeling process interaction, process migration and interaction between processes and data. our type system is based on types for locations, data and processes, expressing security levels. a tree can store data of different security level, independently from the security level of the enclosing location. the access and mobility rights of a process depend on the security level of the ''source'' location of the process itself, i.e. of the location where the process was in the initial network or where the process was created by the activation of a script. the type system enjoys type preservation under reduction (subject reduction). in consequence of subject reduction we prove the following security properties. in a well-typed xd@p-network, a process p whose source location is of level h can copy data of security level at most h and update data of security level less than h. moreover, the process p can only communicate data and go to locations of security level equal or less than h.
spatial-behavioral types for concurrency and resource control in distributed systems. we develop a notion of spatial-behavioral typing suitable to discipline concurrent interactions and resource usage in distributed object systems. our type structure reflects a resource sensitive model, where a parallel composition type operator expresses resource independence, a sequential composition type operator expresses resource synchronization, and a type modality expresses resource ownership. we model the intended computational systems using a concurrent object calculus. soundness of our type system is established using a logical relations technique, building on a interpretation of types as properties expressible in a spatial logic.
adaptive initialization algorithm for ad hoc radio networks with carrier sensing. we propose an algorithm for coordinating access to a shared broadcast channel in an ad hoc network of unknown size n. we reduce the runtime necessary to self-organize access to the channel over the previous algorithm of cai, lu and wang. the runtime of that algorithm is o(n). the goal of our work is to improve the constant factor in this estimation. apart from the experimental evidence of algorithm quality, we provide a rigorous probabilistic analysis of its behavior.
using bisimulation proof techniques for the analysis of distributed abstract machines. we illustrate the use of recently developed proof techniques for weak bisimulation by analysing a generic framework for the definition of distributed abstract machines based on a message-passing implementation. we first define this framework, and then focus on the algorithm which is used to route messages asynchronously to their destination. a first version of this algorithm can be analysed using the standard bisimulation up to expansion proof technique. we show that in a second, optimised version, rather complex behaviours appear, for which more sophisticated techniques, relying on termination arguments, are necessary to establish behavioural equivalence.
minimizing interference of a wireless ad-hoc network in a plane. we consider interference minimization in wireless ad-hoc networks. this is formulated as assigning a suitable transmission radius to each of the given points in the plane, so as to minimize the maximum number of transmission ranges overlapping any point. using ideas from computational geometry and @e-net theory, we attain an o(@d) bound for the maximum interference where @d is the interference of a uniform-radius ad-hoc network. this generalizes a result given in [p. von rickenbach, s. schmid, r. wattenhofer, a. zollinger, a robust interference model for wireless ad-hoc networks, in: proc. 5th international workshop on algorithms for wireless, mobile, ad hoc and sensor networks (wman), denver, colorado, usa, april 2005] for the special case of highway model (i.e., one-dimensional problem) to the two-dimensional case. we show how a distributed algorithm can achieve a slightly weaker bound. we also give a method based on quad-tree decomposition and bucketing that has another provable interference bound in terms of the ratio of the minimum distance to the radius of a uniform-radius ad-hoc network.
a timed semantics of orc. orc is a kernel language for structured concurrent programming. orc provides three powerful combinators that define the structure of a concurrent computation. these combinators support sequential and concurrent execution, and concurrent execution with blocking and termination. orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication. our previous work on the semantics of orc focused on its asynchronous behavior. the inclusion of time or the effect of delay on a computation had not been modeled. in this paper, we define an operational semantics of orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. we develop a number of identities among orc expressions and define an equality relation that is a congruence. we also present a denotational semantics in which the meaning of an orc program is a set of traces, and show that the two semantics are equivalent.
scheduling to maximize participation. we study a problem of scheduling client requests to servers. each client has a particular latency requirement at each server and may choose either to be assigned to some server in order to get serviced provided that her latency requirement is met, or not to participate in the assignment at all. from a global perspective, in order to optimize the performance of such a system, one would aim to maximize the number of clients that participate in the assignment. however, clients may behave selfishly in the sense that, each of them simply aims to participate in an assignment and get serviced by some server where her latency requirement is met with no regard to overall system performance. we model this selfish behavior as a strategic game, show how to compute pure nash equilibria efficiently, and assess the impact of selfishness on system performance. we also show that the problem of optimizing performance is computationally hard to solve, even in a coordinated way, and present efficient approximation and online algorithms.