waashk/dblp huggingface dataset:
arbitrage opportunities across sponsored search markets. we model and study arbitrage across sponsored search markets, created by search engines. we identify and focus on traffic arbitrage and click arbitrage by auctioneers. we derive and characterize equilibria of such arbitrage behaviors across multiple markets.
bincoloring. we introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly environment. the bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. each bin has size b@?n. the packing process is subject to the constraint that at any moment in time at most q@?n bins are partially filled. moreover, bins may only be closed if they are filled completely. we settle the computational complexity of the problem and design an approximation algorithm for a natural version which gives a solution whose value is at most one greater than the optimal one. we also investigate the existence of competitive online algorithms, which must pack each item without knowledge of any future items. we prove an upper bound of 3q-1 and a lower bound of 2q for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of 2q-1. moreover, we show that any deterministic algorithm has a competitive ratio @w(q) and that randomization does not improve this lower bound even when the adversary is oblivious.
new results for finding common neighborhoods in massive graphs in the data stream model. we consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. we give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. our results correct and improve those of buchsbaum, giancarlo, and westbrook [on finding common neighborhoods in massive graphs, theoretical computer science, 299 (1-3) 707-718 (2004)]
algorithms for finding the weight-constrained k longest paths in a tree and the length-constrained k maximum-sum segments of a sequence. in this work, we obtain the following new results: -given a tree t=(v,e) with a length function @?:e->r and a weight function w:e->r, a positive integer k, and an interval [l,u], the weight-constrainedklongest paths problem is to find the k longest paths among all paths in t with weights in the interval [l,u]. we show that the weight-constrainedklongest paths problem has a lower bound @w(vlogv+k) in the algebraic computation tree model and give an o(vlogv+k)-time algorithm for it. -given a sequence a=(a"1,a"2,...,a"n) of numbers and an interval [l,u], we define the sum and length of a segment a[i,j] to be a"i+a"i"+"1+...+a"j and j-i+1, respectively. the length-constrainedkmaximum-sum segments problem is to find the k maximum-sum segments among all segments of a with lengths in the interval [l,u]. we show that the length-constrainedkmaximum-sum segments problem can be solved in o(n+k) time.
pattern matching with pair correlation distance. in pattern matching with pair correlation distance problem, the goal is to find all occurrences of a pattern p of length m, in a text t of length n, where the distance between them is less than a threshold k. for each text location i, the distance is defined as the number of different kinds of mismatched pairs (&alpha;,&beta;), between p and t[i ...i + m]. we present an algorithm with running time of $o\left(min\{\left|\sigma_p\right|^2 n \log m,n \!\left({m \log m}\right)^\frac{2}{3}\}\right)\!$ for this problem. another interesting problem is the one-side pair correlation distance where it is desired to find all occurrences of p where the number of mismatched characters in p is less than k. for this problem, we present an algorithm with running time of $o\left(min\{\left|\sigma_p\right| n \log m,n\right.\left.\sqrt{m \log m}\}\right)$.
heuristic algorithms for hadamard matrices with two circulant cores. we design heuristic algorithms to construct hadamard matrices with two circulant cores. this hard combinatorial problem can be formulated in terms of objective functions of several binary variables, so that heuristic methodologies can be used. our algorithms are based on local and tabu search and they use information on the geometry of the objective function landscapes. in addition, we use the supplementary difference sets formalism to detect when solutions of a special structure exist. using these algorithms we have computed at least one hadamard matrix with two circulant cores of the sixteen orders 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116. in particular, the hadamard matrix with two circulant cores of order 116 is constructed here for the first time, indeed it was accidentally reported as known in an earlier paper.
efficient on-line repetition detection. a repetition is a nonempty string of the form x^q, where q>=2. given a string s character by character and the value of q, the on-line repetition detection problem is to detect and report the first repetition in s, if it exists, in an on-line manner. leung, peng and ting first studied the problem for q=2 and gave an o(mlog^2m) time algorithm (refer to [h.-f. leung, z. peng, h.-f. ting, an efficient algorithm for online square detection, theoretical computer science 363 (1) (2006) 69-75]), where m is the ending position of the first repetition in s. in this paper, we improve the above cited work by reducing the time complexity to o(mlog@b), where @b is the number of distinct characters in the first m characters of s. moreover, we also solve the problem for q>=3 with the same time complexity.
a new framework for the design and analysis of identity-based identification schemes. constructing an identification scheme is one of the fundamental problems in cryptography, and is very useful in practice. an identity-based identification (ibi) scheme allows a prover to identify himself to a public verifier who knows only the claimed identity of the prover and some public information. in this paper, we propose a new framework for both the design and analysis of ibi schemes. our approach works in an engineering way. we first identify an ibi scheme as the composition of two building blocks, and then show that, with different security properties of these building blocks, the corresponding ibi schemes can achieve security against impersonation under different levels of attacks, namely, passive attack (id-imp-pa), active attack (id-imp-aa) or concurrent attack (id-imp-ca). in particular, we show that an id-imp-pa secure ibi scheme can be built if there exists a trapdoor weak-one-more relation and an honest verifier zero-knowledge proof with special soundness, while an id-imp-aa and id-imp-ca secure ibi scheme can be built if there exists a trapdoor strong-one-more relation and a witness dualism proof with special soundness (wd-ss). this new framework can capture ibi construction techniques that are not captured by other known frameworks. it also helps to construct new and efficient schemes. we demonstrate this by proposing two new ibi schemes, one achieving id-imp-pa, and the other one achieving both id-imp-aa and id-imp-ca, and neither of them can be captured by existing frameworks.
modelling co-transcriptional cleavage in the synthesis of yeast pre-rrna. in this paper we present a quantified model of the synthesis of pre-rrnas in yeast. the chemical kinetics simulation software dizzy has been used as both the modelling and simulation framework of our study. the simulations have been used to investigate the mechanism of co-transcriptional cleavage which can occur during the synthesis of pre-rrnas. throughout the paper we emphasise the strong role of experimental data both in shaping the model and in guiding the analysis which is carried out. parameter estimation procedures have been used to fit the model to the data and we discuss the validation of the model against the available experimental data. simulation based on gillespie's algorithm is considered to be the reference method for our analysis and a comparison with other simulators is reported. finally, we define an extended model, that relaxes one of the assumptions of the initial model.
incremental discovery of the irredundant motif bases for all suffixes of a string in o(nlogn) time. compact bases formed by motifs called ''irredundant'' and capable of generating all other motifs in a sequence have been proposed in recent years and successfully tested in tasks of biosequence analysis and classification. given a sequence s of n characters drawn from an alphabet @s, the problem of extracting such a base from s had been previously solved in time o(n^2lognlog|@s|) and o(|@s|n^2log^2nloglogn), respectively, using the fft-based string searching by fischer and paterson. more recently, a solution on binary strings taking time o(n^2) without resorting to the fft was also proposed. in the present paper, we considered the problem of incrementally extracting the bases of all suffixes of a string. this problem was solved in a previous work in time o(n^3). a much faster incremental algorithm is described here, which takes time o(n^2logn) for binary strings. although this algorithm does not make use of the fft, its performance is comparable to the one exhibited by the previous fft-based algorithms involving the computation of only one base. the implicit representation of a single base requires o(n) space, whence for finite alphabets the proposed solution is within a logn factor from optimality.
reductions for monotone boolean circuits. the large class, say nlog, of boolean functions, including 0-1 sort and 0-1 merge, have an upper bound of o(nlogn) for their monotone circuit size, i.e., they have circuits with o(nlogn) and/or gates of fan-in two. suppose that we can use, besides such normal and/or gates, any number of more powerful ''f-gates'' which realize a monotone boolean function f with r(>=2) inputs and r^'(>=1) outputs. note that the cost of each and/or gate is one and we assume that the cost of each f-gate is r. now we define: a boolean function f in nlog is said to be f-easy if f can be constructed by a circuit with and/or/f gates whose total cost is o(nlogn). in this paper we show that 0-1 merge is not f-easy for an arbitrary monotone function f such that r^'@?r/logr.
bayesian inference for differential equations. nonlinear dynamic systems such as biochemical pathways can be represented in abstract form using a number of modelling formalisms. in particular differential equations provide a highly expressive mathematical framework with which to model dynamic systems, and a very natural way to model the dynamics of a biochemical pathway in a deterministic manner is through the use of nonlinear ordinary or time delay differential equations. however if, for example, we consider a biochemical pathway the constituent chemical species and hence the pathway structure are seldom fully characterised. in addition it is often impossible to obtain values of the rates of activation or decay which form the free parameters of the mathematical model. the system model in many cases is therefore not fully characterised either in terms of structure or the values which parameters take. this uncertainty must be accounted for in a systematic manner when the model is used in simulation or predictive mode to safeguard against reaching conclusions about system characteristics that are unwarranted, or in making predictions that are unjustifiably optimistic given the uncertainty about the model. the bayesian inferential methodology provides a coherent framework with which to characterise and propagate uncertainty in such mechanistic models and this paper provides an introduction to bayesian methodology as applied to system models represented as differential equations.
the complexity of equilibria: hardness results for economies via a correspondence with games. we give a reduction from any two-player game to a special case of the leontief exchange economy, with the property that the nash equilibria of the game and the equilibria of the market are in one-to-one correspondence. our reduction exposes a computational hurdle inherent in solving certain families of market equilibrium problems: finding an equilibrium for leontief economies is at least as hard as finding a nash equilibrium for two-player nonzero sum games, a problem recently proven to be ppad-complete. as a corollary of the one-to-one correspondence, we obtain a number of hardness results for questions related to the computation of market equilibria, using results already established for games [i. gilboa, e. zemel, nash and correlated equilibria: some complexity considerations, games and economic behavior 1 (1989) 80-93]. in particular, among other results, we show that it is np-hard to say whether a particular family of leontief exchange economies, that is guaranteed to have at least one equilibrium, has more than one equilibrium. perhaps more importantly, we also prove that it is np-hard to decide whether a leontief exchange economy has an equilibrium. this fact should be contrasted against the known ppad-completeness result of [c.h. papadimitriou, on the complexity of the parity argument and other inefficient proofs of existence, journal of computer and system sciences 48 (1994) 498-532], which holds when the problem satisfies some standard sufficient conditions that make it equivalent to the computational version of brouwer's fixed point theorem.
pipelined algorithms to detect cheating in long-term grid computations. this paper studies pipelined algorithms for protecting distributed grid computations from cheating participants, who wish to be rewarded for tasks they receive but don't perform. we present improved cheater detection algorithms that utilize natural delays that exist in long-term grid computations. in particular, we partition the sequence of grid tasks into two interleaved sequences of task rounds, and we show how to use those rounds to devise the first general-purpose scheme that can catch all cheaters, even when cheaters collude. the main idea of this algorithm might at first seem counter-intuitive-we have the participants check each other's work. a naive implementation of this approach would, of course, be susceptible to collusion attacks, but we show that by, adapting efficient solutions to the parallel processor diagnosis problem, we can tolerate collusions of lazy cheaters, even if the number of such cheaters is a fraction of the total number of participants. we also include a simple economic analysis of cheaters in grid computations and a parameterization of the main deterrent that can be used against them-the probability of being caught.
on the power of lookahead in on-line server routing problems. we study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what is the improvement that can be achieved in terms of the competitive ratio? we consider several on-line server routing problems in this setting, such as the on-line traveling salesman and the on-line traveling repairman problem. we show that the influence of lookahead can change considerably depending on the particular objective function and metric space considered.
succinct representations of planar maps. this paper addresses the problem of representing the connectivity information of geometric objects, using as little memory as possible. as opposed to raw compression issues, the focus here is on designing data structures that preserve the possibility of answering incidence queries in constant time. we propose, in particular, the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1.62 bits per triangle, or equivalently 3.24 bits per vertex for triangulations. these representations support adjacency queries between vertices and faces in constant time.
nanok: a calculus for the modeling and simulation of nano devices. we develop a process calculus-the nano@k calculus-for modeling, analyzing and predicting the properties of molecular devices. the nano@k calculus is equipped with a simple stochastic model, that we use to model and simulate the behavior of a molecular shuttle, a basic nano device currently used for building more complex systems.
on temporal logic constraint solving for analyzing numerical data time series. temporal logics and model-checking have proved successful in expressing biological properties of complex biochemical systems, and automatically verify their satisfaction, in both qualitative and quantitative models. in this article, we go beyond model-checking and present a constraint solving algorithm for quantifier-free first-order temporal logic formulae, with constraints over the reals. this algorithm computes the domain of the real valued variables occurring in a formula that makes it true in a model. we illustrate this approach for the automatic generation of a temporal logic specification from biological data time series. we provide a set of biologically relevant patterns of formulae, and apply them to numerical data time series of models of the cell cycle control and mapk signal transduction. we show in these examples that this approach infers automatically semi-qualitative, semi-quantitative information about concentration thresholds, amplitude of oscillations, stability properties, checkpoints and influences between species.
area-time tradeoffs for universal vlsi circuits. an area-universal vlsi circuit can be programmed to emulate every circuit of a given area, but at the cost of lower area-time performance. in particular, if a circuit with area-time bounds (a,t) is emulated by a universal circuit with bounds (a"u,t"u), we say that the universal circuit has blowup a"u/a and slowdown t"u/t. a central question in vlsi theory is to investigate the inherent costs and tradeoffs of universal circuit designs. prior to this work, universal designs were known for area-a circuits with o(1) blowup and o(loga) slowdown. universal designs for the family of area-a circuits containing o(a^1^+^@eloga) vertices, with o(a^@e) blowup and o(logloga) slowdown had also been developed. however, the existence of universal circuits with o(1) slowdown and relatively small blowup was an open question. in this paper, we settle this question by designing an area-universal circuit u"a^^^@e with o(1/@e) slowdown and o(a^@e) blowup, for any value of the parameter @e, with 4logloga/loga@?@e@?1. by varying @e, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. in particular, when @e is chosen to be a constant, our universal circuit yields o(1) slowdown.
algorithms for computing a parameterized st-orientation. st-orientations (st-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. several algorithms have been proposed in the past to compute an st-orientation of a biconnected graph. in this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final st-oriented graph, such as the length of the longest path. this work has many applications, including graph drawing and network routing, where the length of the longest path is vital in deciding certain features of the final solution. this work applies to other difficult problems as well, such as graph coloring and of course longest path. we present extended theoretical and experimental results which show that our technique is efficient and performs well in practice.
cavity detection and matching for binding site recognition. we developed a suite of methods for the problem of protein binding site recognition, based on a representation of the protein structures by a collection of spin-images. a procedure for cavity detection is coupled with a method previously developed for the recognition of similar regions in two proteins, and applied to the comparison of two protein's cavities, the all-to-all pairwise comparison of a set of cavities, and the recognition of multiple binding sites in one cavity. all the presented methods can be used to screen large collections of proteins. the detection of cavities in a given protein is often the preliminary step in protein binding site recognition, since binding sites usually lie in cavities. the comparison of two cavities identifies two similar regions in the two cavities, and hints at a common functional structure when one or both regions include a binding site. the all-to-all pairwise comparison of a set of cavities is clustered according to the measure of similarity of the cavities, obtaining a clustering that groups together cavities with the same binding sites, when their structures are similar enough. recognition of multiple binding sites in one cavity is performed by the comparison of a cavity, called background cavity, with a dataset of cavities, and clustering its residues that match the residues of other cavities in the data set. the four methods are benchmarked on different databases, and their effectiveness is discussed.
evolving blenx programs to simulate the evolution of biological networks. we present a formal approach to study the evolution of biological networks. we use the beta workbench and its blenx language to model and simulate networks in connection with evolutionary algorithms. mutations are done on the structure of blenx programs and networks are selected at any generation by using a fitness function. the feasibility of the approach is illustrated with a simple example.
synapses as stochastic concurrent systems. we present a stochastic model of the presynaptic terminal in the calyx of held synapse. this model exploits process calculi as a representation language and has a direct computational implementation that supports quantitative simulation trials of the behaviour of the synapse. to our knowledge, it represents the first model of synaptic activity based on process calculi. the model builds upon available data, the fitting of some parameters and developed working hypotheses. experiments about plasticity have been carried out regarding synaptic facilitation and potentiation. also, synaptic depression has been considered in a model exhibiting dynamical equilibrium. overall, the simulation results are coherent with the experimental findings appearing in the literature about the modeled reality. these results represent a quite detailed description of the presynaptic activity. this multidisciplinary work validates some aspects of the approach based on process calculi with respect to the new application domain, such as abstraction, expressiveness and compositionality.
the nearest polynomial with a zero in a given domain. for a real univariate polynomial f and a closed domain d@?c whose boundary c is represented by a piecewise rational function, we provide a rigorous method for finding a real univariate polynomial f@? such that f@? has a zero in d and @?f-f@?@?"~ is minimal. first, we prove that if a nearest polynomial exists, there is a nearest polynomial f@? such that the absolute value of every coefficient of f-f@? is @?f-f@?@?"~ with at most one exception. using this property and the representation of c, we reduce the problem to solving systems of algebraic equations, each of which consists of two equations with two variables.
schur aggregation for linear systems and determinants. we apply our recent preconditioning techniques to the solution of linear systems of equations and computing determinants. we combine these techniques with the sherman-morrison-woodbury formula, its new variations, aggregation, iterative refinement, and advanced algorithms that rapidly compute sums and products either error-free or with the desired high accuracy. our theoretical and experimental study shows the power of this approach.