waashk/dblp huggingface dataset:
on the complexity of bilinear forms with commutativity we consider the problem of computing a set of bilinear forms in the case when the indeterminates commute. we develop lower bound techniques which seem to be more powerful than those already known in the literature for the commutative case. an unexpected result is the fact that duality theory does not hold in the commutative case; we prove that the multiplication of 2 &times; n by n &times; 2 matrices requires at least [27n/8] multiplications while it is possible to multiply 2 &times; 2 by 2 &times; n matrices using only 3n + 2 multiplications. we also settle the question of whether commutativity can reduce the number of multiplications by 1/2 by showing that this can never happen. on the other hand, we show that, over algebraically closed fields, the complexity of computing a pair of bilinear forms is the same whether or not commutativity is allowed. we feel that, in general, commutativity will have little effect whenever the constant set is an algebraically closed field.
time-space tradeoffs for some algebraic problems we study the time-space relationship of several algebraic problems such as matrix multiplication and matrix inversion. several results relating the algebraic properties of a set of functions to the structure of the graph of any straight-line program, that computes this set, are shown. some of our results are the following. multiplying m &times; n by n &times; p matrices with space s requires at least time t &ge; &ohgr;(mnp/s). inverting an n &times; n matrix with space s requires at least time t &ge; &ohgr;(n4/s).
a new greedy approach for facility location problems. we present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. we use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k-median and facility location problems. we also prove a lower bound of 1+2/e on the approximability of the k-median problem. at the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.
equitable cost allocations via primal-dual-type algorithms. perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. however, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. we present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to her application. our class includes the dutta-ray egalitarian method as a special case. it also includes a new cost sharing method, which we call the opportunity egalitarian method.
improved approximation schemes for scheduling unrelated parallel machines. we consider the problem of schedulingn independent jobs onm unrelated parallel machines where each job has to be processed by exactly one machine, processing jobj on machinei requiresp ijtime units, and the objective is to minimize the makespan, i.e., the maximum job completion time. focusing on the case whenm is fixed, we present for both preemptive and nonpreemptive variants of the problem fully polynomial approximation schemes whose running times depend only linearly onn. we also study an extension of the problem where processing jobj on machinei incurs a cost ofc ij , and thus there are two optimization criteria: makespan and cost. we show that, for any fixedm, there is a fully polynomial approximation scheme that, given valuest andc, computes for any fixed e &gt; 0 a schedule in0( n) time with makespan at most (1 + e) t and cost at most (1 + e) c, if there exists a schedule of makespant and costc.
on strip packing with rotations. we present an asymptotic fully polynomial time approximation scheme for two-dimensional strip packing with rotations. in this problem, a set of rectangles need to be packed into a rectangle (strip) of fixed width and minimum height, and these rectangles can be rotated by 90°. additionally, we present a simple asymptotic polynomial time approximation scheme, and give an improved algorithm for two-dimensional bin packing with rotations.
an optimal multi-writer snapshot algorithm. an m-component, n-process snapshot object is an abstraction of shared memory that consists of m words and allows up to n processes to concurrently execute the following two types of operations: write(i,v), which writes v into the ith word, and scan(), which returns the current values of all m locations [1, 3]. the snapshot problem is to design algorithms for the write and scan operations that meet two challenging requirements: (1) operations appear to be atomic, and (2) operations are wait-freefor any (m-component, n-process) snapshot algorithm, which runs on hardware that supports only word-sized objects, ω(1) and ω(m) are trivial lower bounds on the time complexity of write(i,v) and scan(), respectively. but, are these bounds tight?for a restricted version of the snapshot problem, known in the literature as the single-writer snapshot problem, riany, shavit and touitou [18] showed that the answer is yes: they designed an algorithm with o(1) and o(m) running times for the write(i,v) and scan() operations, respectively. (the single-writer snapshot problem assumes that (i) the number m of words of the snapshot object is equal to the number n of processes, and (ii) only the ith process may write into the ith snapshot word.this paper shows that the same (optimal) running times of o(1) for write(i,v) and o(m) for scan() are achievable for the general problem, known in the literature as the multiwriter snapshot problem. our algorithm requires hardware support for the cas (compare&swap) operation (in comparison, riany, shavit and touitou's algorithm requires hardware support for cas, fetch&inc, and fetch&dec operations).
cell-probe lower bounds for the partial match problem. given a database of n points in {0, 1)d, the partial match problem is: in response to a query x in {0,1,*}d, is there a database point y such that for every i whenever xi ≠ *, we have xi = yi. in this paper we show randomized lower bounds in the cell-probe model for this well-studied problem (analysis of associative retrieval algorithms, ph.d. thesis, stanford university, 1974; the art of computer programming; sorting and searching, addison-wesley, reading, ma, 1973; siam j. comput. 5(1) (1976) 19; j. comput. system sci. 57(1) (1998) 37; proceedings of the 31st annual acm symposium on theory of computing, 1999; proceedings of the 29th international colloquium on algorithms, logic, and programming, 1999).our lower bounds follow from a near-optimal asymmetric communication complexity lower bound for this problem. specifically, we show that either alice has to send ω(d/log n) bits or bob has to send ω(n1-o(1)) bits. when applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n,d) where each cell is of size poly(log n,d), then ω(d/log2 n) probes are needed. this is an exponential improvement over the previously known lower bounds for this problem obtained by miltersen et al. (1998) and borodin et al. (1999).our lower bound also leads to new and improved lower bounds for related problems including a lower bound for the l∞ c-nearest neighbor problem for c < 3 and an improved communication complexity lower bound for the exact nearest neighbor problem.
online server allocation in a server farm via benefit task systems. a web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. ideally, the allocation to a site should always suffice to handle its load. however, due to a limited number of servers and the overhead incurred in changing the allocation of a server from one site to another, the system may become overloaded. the problem faced by the web hosting service provider is how to allocate the available servers in the most profitable way. adding to the complexity of this problem is the fact that future loads of the sites are either unknown or known only for the very near future.in this paper we model this server allocation problem, and consider both its offline and online versions. we give a polynomial time algorithm for computing the optimal offline allocation. in the online setting, we show almost optimal algorithms (both deterministic and randomized) for any positive lookahead. the quality of the solution improves as the lookahead increases. we also consider several special cases of practical interest. finally, we present some experimental results using actual trace data that show that one of our online algorithm performs very close to optimal.interestingly, the online server allocation problem can be cast as a more general benefit task system that we define. our results extend to this task system, which captures also the benefit maximization variants of the k-server problem and the metrical task system problem. it follows that the benefit maximization variants of these problems are more tractable than their cost minimization variants.
two applications of information complexity. we show the following new lower bounds in two concrete complexity models:<ol>(1) in the two-party communication complexity model, we show that the tribes function on n inputs[6] has two-sided error randomized complexity ω(n), while its nondeterminstic complexity and co-nondeterministic complexity are both θ(√n). this separation between randomized and nondeterministic complexity is the best possible and it settles an open problem in kushilevitz and nisan[17], which was also posed by beame and lawry[5].(2) in the boolean decision tree model, we show that the recursive majority-of-three function on 3h inputs has randomized complexity ω((7/3)h). the deterministic complexity of this function is θ(3h), and the nondeterministic complexity is θ(2h). our lower bound on the randomized complexity is a substantial improvement over any lower bound for this problem that can be obtained via the techniques of saks and wigderson [23], heiman and wigderson[14], and heiman, newman, and wigderson[13]. recursive majority is an important function for which a class of natural algorithms known as directional algorithms does not achieve the best randomized decision tree upper bound.</ol.these lower bounds are obtained using generalizations of information complexity, which quantifies the minimum amount of information that will have to be revealed about the inputs by every correct algorithm in a given model of computation.
a polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. we present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.
universal approximations for tsp, steiner tree, and set cover. we introduce a notion of universality in the context of optimization problems with partial information. universality is a framework for dealing with uncertainty by guaranteeing a certain quality of goodness for all possible completions of the partial information set. universal variants of optimization problems can be defined that are both natural and well-motivated. we consider universal versions of three classical problems: tsp, steiner tree and set cover.we present a polynomial-time algorithm to find a universal tour on a given metric space over n vertices such that for any subset of the vertices, the sub-tour induced by the subset is within o(log4n/log log n) of an optimal tour for the subset. similarly, we show that given a metric space over n vertices and a root vertex, we can find a universal spanning tree such that for any subset of vertices containing the root, the sub-tree induced by the subset is within o(log4n/log log n) of an optimal steiner tree for the subset. our algorithms rely on a new notion of sparse partitions, that may be of independent interest. for the special case of doubling metrics, which includes both constant-dimensional euclidean and growth-restricted metrics, our algorithms achieve an o(log n) upper bound. we complement our results for the universal steiner tree problem with a lower bound of ω(log n/log log n) that holds even for n vertices on the plane. we also show that a slight generalization of the universal steiner tree problem is conp-hard and present nearly tight upper and lower bounds for a universal version of set cover.
two heads are better than two tapes. we show that a turing machine with two single-head one-dimensional tapes cannot recognize the set.
free groups and regular expressions group events are defined as regular events recognized by partial group automata. canonical forms are introduced for the class of regular expressions denoting group events. algorithms are presented to find a canonical form from a recognizing automaton, to find a recognizing automaton from a canonical form, and to find a canonical form from a regular expression denoting a simple group event. furthermore an algorithm is presented that decides whether or not two canonical forms denote the same event.
approximation algorithms for combinatorial problems simple, polynomial-time, heuristic algorithms for finding approximate solutions to various polynomial complete optimization problems are analyzed with respect to their worst case behavior, measured by the ratio of the worst solution value that can be chosen by the algorithm to the optimal value. for certain problems, such as a simple form of the knapsack problem and an optimization problem based on satisfiability testing, there are algorithms for which this ratio is bounded by a constant, independent of the problem size. for a number of set covering problems, simple algorithms yield worst case ratios which can grow with the log of the problem size. and for the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as 0(n&egr;), where n is the problem size and &egr;> 0 depends on the algorithm.
complete problems for deterministic polynomial time the results of cook and karp ([k], [c]) aroused considerable interest for at least two reasons. first, the answer to a long-standing open question which had seemed peculiar to automata theory&mdash;whether deterministic and nondeterministic polynomial-time-bounded turing machines are equivalent in power&mdash;was seen to be exactly equivalent to determining whether any of several familiar combinatorial problems can be solved by polynomial-time algorithms. second, the existence of complete problems for np1 made it possible to replace an entire class of questions by a question about a single representative.thus all of these combinatorial and automata-theoretic problems were essentially restatements of a single problem, such as: can satisfiability of a propositional formula be decided in polynomial time. the main purpose of this paper is to introduce several problems which are complete for p, the class of languages recognizable in deterministic polynomial time. any such language has the property that if it is recognizable in space logk(&bull;), then every language in p is so recognizable. thus a problem complete for p will serve to differentiate those sets in p which are not recognizable in logarithmic space from those which are, providing such differentiation is possible. a problem of this type was first presented by cook in [c2], concerning solvable path systems.
turing machines and the spectra of first-order formulas with equality in this paper we show that these similarities are not accidental - that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and non-deterministic time-or space-bounded turing machines.
independence results in computer science? (preliminary version) although there has been considerable additional work discussing limitations of formal proof techniques for computer science ([yo-73&77], [har-76], [har&ho-77], [haj-77&79], [go-79]), these papers show only very general consequences of incompleteness: the stated results hold for all sufficiently powerful formal systems for computer science. only the work of o'donnell and of lipton directly addresses the question of just how powerful formal axioms for computer science should be, and these two authors make rather radically different suggestions. we investigate this latter question: how powerful should a set of axioms be if it is to be adequate for computer science? in particular, in this paper we investigate the adequacy of the system of [li-78] as a formal system for computer science.
fast programs for initial segments and polynomial time computation in weak models of arithmetic (preliminary abstract) in this paper we study two alternative approaches for investigating whether np complete sets have fast algorithms. one is to ask whether there are long initial segments on which such sets are easily decidable by relatively short programs. the other approach is to ask whether there are weak fragments of arithmetic for which it is consistent to believe that p &equil; np. we show, perhaps surprisingly, that the two questions are equivalent: it is consistent to believe that p &equil; np in certain models of weak arithmetic theories iff it is true (in the standard model of computation) that there are infinitely many initial segments on which satisfiability is polynomially decidable by programs that are much shorter than the length of the initial segment.
derandomizing polynomial identity tests means proving circuit lower bounds. we show that derandomizing polynomial identity testing is essentially equivalent to proving arithmetic circuit lower bounds for nexp. more precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) nexp ⊄ p/poly or (ii) permanent is not computable by polynomial-size arithmetic circuits. we also prove a (partial) converse: if permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic circuit of polynomially bounded degree computes an identically zero polynomial.since polynomial identity testing is a corp problem, we obtain the following corollary: if rp = p (or even corp ⊆ ∩ε > 0 ntime(2nε), infinitely often), then nexp is not computable by polynomial-size arithmetic circuits. thus establishing that rp = corp or bpp = p would require proving superpolynomial lower bounds for boolean or arithmetic circuits. we also show that any derandomization of rnc would yield new circuit lower bounds for a language in nexp.we also prove unconditionally that nexprp does not have polynomial-size boolean or arithmetic circuits. finally, we show that nexp ⊄ p/poly if both bpp = p and low-degree testing is in p; here low-degree testing is the problem of checking whether a given boolean circuit computes a function that is close to some low-degree polynomial over a finite field.
entropy and sorting we reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks. (1) given a partial order p, find (adaptively) a sequence of comparisons (questions of the form, &ldquo;is x < y?&rdquo;) which sorts (i.e. finds an unknown linear extension of) p using o(log(e(p))) comparisons in worst case (where e(p) is the number of linear extensions of p). (2) compute (on line) answers to any comparison algorithm for sorting a partial order p which force the algorithm to use &ohgr;(log(e(p))) comparisons. (3) given a partial order p of size n, estimate e(p) to within a factor exponential in n. (we give upper and lower bounds which differ by the factor nn/n!.) our approach, based on entropy of the comparability graph of p and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions.
every poset has a good comparison we show that any finite partially ordered set p contains a pair of elements x and y such that the proportion of linear extensions of p in which x lies below y is between 3/11 and 8/11. a consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. precisely: if x is a totally ordered set about which we are given some partial information, and if e(x) is the number of total orderings of x compatible with this partial information, then it is possible to sort x using no more than c log2e(x) comparisons (c@@@@2.17).
concurrent general composition of secure protocols in the timing model. in the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). %the joint computation should be such that even in the stand-alone case, it has been shown that every efficient function can be securely computed. however, in the setting of concurrent composition, broad impossibility results have been proven for the case where there is no honest majority (or trusted setup).in this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). we show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).
boosting in the presence of noise. boosting algorithms are procedures that ''boost'' low-accuracy weak learning algorithms to achieve arbitrarily high accuracy. over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. in this paper we study boosting in the presence of random classification noise, giving both positive and negative results. we show that a modified version of a boosting algorithm due to mansour and mcallester (j. comput. system sci. 64(1) (2002) 103) can achieve accuracy arbitrarily close to the noise rate. we also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). finally, we consider a variant of the standard scenario for boosting in which the ''weak learner'' satisfies a slightly stronger condition than the usual weak learning guarantee. we give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise.
a polynomial reduction from multivariate to bivariate integral polynomial factorization given an arbitrary but fixed integer r -&-ge; 3. we show that testing r-variate polynomials with integer coefficients for irreducibility is m-reducible in polynomial time of the total degree and the largest coefficient length to testing bivariate polynomials for irreducibility. factoring r-variate polynomials into irreducibles is polynomial time turing-reducible to completely factoring bivariate polynomials.