waashk/dblp huggingface dataset:
on the convergence of newton's method for monotone systems of polynomial equations. monotone systems of polynomial equations (mspes) are systems of fixed-point equations x1 = f1(x1, ..., xn), ..., xn = fn(x1, ..., xn) where each fi is a polynomial with positive real coefficients. the question of computing the least non-negative solution of a given mspe x = f(x) arises naturally in the analysis of stochastic context-free grammars, recursive markov chains, and probabilistic pushdown automata. while the kleene sequence f(0), f(f(0)), ... always converges to the least solution mu.f, if it exists, the number of iterations needed to compute the first i bits of mu.f may grow exponentially in i.etessami and yannakakis have recently adapted newton's iterative method to mspes and proved that the newton sequence converges at least as fast as the kleene sequence and exponentially faster in many cases.they conjecture that, given an mspe of size m, the number of newton iterations needed to obtain i accurate bits of mu.f grows polynomially in i and m. in this paper we show that the number of iterations grows linearly in i for strongly connected mspes and may grow exponentially in m for general mspes.
zero-knowledge from secure multiparty computation. we present a general construction of a zero-knowledge proof for an np relation r(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. the latter protocol is only required to be secure against a small number of "honest but curious" players. as an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. in particular, if verifying r on a witness of length m can be done by a circuit c of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols. approaching the witness length. if c has constant depth over ∧,∨,⊕, - gates of unbounded fan-in, we get a zero-knowledge protocol with communication complexity m·poly(k)·polylog(s), where k is a security parameter. such a protocol can be implemented in either the standard interactive model or, following a trusted setup, in a non-interactive model. "constant-rate" zero-knowledge. for an arbitrary circuit c of size s and a bounded fan-in, we geta zero-knowledge protocol with communication complexity o(s)+poly(k). thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. this improves over the o(ks) complexity of the best previous protocols.
node- and edge-deletion np-complete problems if &pgr; is a graph property, the general node(edge) deletion problem can be stated as follows: find the minimum number of nodes(edges), whose deletion results in a subgraph satisfying property &pgr;. in this paper we show that if &pgr; belongs to a rather broad class of properties (the class of properties that are hereditary on induced subgraphs) then the node-deletion problem is np-complete, and the same is true for several restrictions of it. for the same class of properties, requiring the remaining graph to be connected does not change the np-complete status of the problem; moreover for a certain subclass, finding any "reasonable" approximation is also np-complete. edge-deletion problems seem to be less amenable to such generalizations. we show however that for several common properties (e.g. planar, outer-planar, line-graph, transitive digraph) the edge-deletion problem is np-complete.
randomly coloring planar graphs with fewer colors than the maximum degree. we study markov chains for randomly sampling k-colorings of a graph with maximum degree δ. our main result is a polynomial upper bound on the mixing time of the single-site update chain knownas the glauber dynamics for planar graphs when k=ω(δ/logδ). our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graphis at most δ1-ε, for fixed ε > 0. the main challenge when k ≤ δ + 1 is the possibility of "frozen" vertices, that is, vertices for which only one coloris possible, conditioned on the colors of its neighbors. indeed, when δ = o(1), even a typical coloring canhave a constant fraction of the vertices frozen.our proofs rely on recent advances in techniquesfor bounding mixing time using "local uniformity" properties.
issues of correctness in database concurrency control by locking our aim in this paper is to show that there is a mathematically inherent reason why existing systems enforce d-serializability (rather than just because of its simplicity): it is because they are based on locking. our main result is a characterization of the power of locking which states that if a locking policy is safe then it must allow only d-serializable schedules. furthermore any such schedule can be produced by some safe locking policy. the rest of the paper is organized as follows. in section 2 we formalize our concepts and describe the model. in section 3 we characterize d-serializability in semantic terms. in section 4 we examine when a set of transactions can be let to run safely by themselves without locking or any intervention from the scheduler. section 5 is concerned with locking policies and in section 6 we discuss some implications of our results.
an approximation algorithm for max-min fair allocation of indivisible goods. in this paper we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. the approximation ratio of our algorithm is ω1√k log3 k. as a part of our algorithm, we design an iterative method for rounding a fractional matching on a tree which might be of independent interest.
circuit lower bounds for merlin-arthur classes. we show that for each $k>0$, $\mathsf{ma}/1$ ($\mathsf{ma}$ with 1 bit of advice) does not have circuits of size $n^k$. this implies the first superlinear circuit lower bounds for the promise versions of the classes $\mathsf{ma}$, $\mathsf{am}$, and $\mathsf{zpp}_{\parallel}^{\mathsf{np}}$. we extend our main result in several ways. for each $k$, we give an explicit language in $(\mathsf{ma}\cap\mathsf{coma})/1$ which does not have circuits of size $n^k$. we also adapt our lower bound to the average-case setting; i.e., we show that $\mathsf{ma}/1$ cannot be solved on more than $1/2+1/n^k$ fraction of inputs of length $n$ by circuits of size $n^k$. furthermore, we prove that $\mathsf{ma}$ does not have arithmetic circuits of size $n^k$ for any $k$. as a corollary to our main result, we obtain that derandomization of $\mathsf{ma}/o(1)$ implies the existence of pseudorandom generators computable using $o(1)$ bits of advice.
tensor-based hardness of the shortest vector problem to within almost polynomial factors. we show that unless np ⊆ rtime (2poly(log n)), for any ε > 0 there is no polynomial-time algorithm approximating the shortest vector problem (svp) on n-dimensional lattices inthe lp norm (1 ≤q p<∞) to within a factor of 2(log n)1-ε. this improves the previous best factor of 2(logn)1/2-ε under the same complexity assumption due to khot. under the stronger assumption np ࣰ rsubexp, we obtain a hardness factor of nc/log log n for some c > 0. our proof starts with khot's svp instances from that are hard to approximate to within some constant. to boost the hardness factor we simply apply the standard tensor product oflattices. the main novel part is in the analysis, where we show that khot's lattices behave nicely under tensorization. at the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de shalit and parzanchevski.
on the impossibility of a quantum sieve algorithm for graph isomorphism. it is known that any quantum algorithm for graph isomorphism thatworks within the framework of the hidden subgroup problem (hsp) must performhighly entangled measurements across ω(n log n) coset states. one ofthe only known models for how such a measurement could be carried outefficiently is kuperberg's algorithm for the hsp in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. this "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial. in this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. specifically, we consider the natural reduction of graph isomorphism to the hsp over the the wreath product sn ࣀ z2. using a recently proved bound on the irreducible characters of sn, we show that no algorithm in this family can solve graph isomorphism in less than eω(√n) time, no matter what adaptive rule it uses to select and combine quantum states. in particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time eo(√(n log n)).
graph entropy and quantum sorting problems. let p = (x, < p) be a partial order on a set of n elements x = x1, x2,..., xn. define the quantum sorting problem qsortp as: given n distinct numbers x1, x2,..., xn consistent with p, sort them by a quantum decision tree using comparisons of the form "xi: xj". let qε(p) be the minimum number of queries used by any quantum decision tree for solving qsortp with error less than ε (where 0 < ε < 1/10 is fixed). it was proved by hoyer, neerbek and shi (algorithmica 34 (2002), 429--448) that, when p0 is the empty partial order, qε(p0) ≥ ω (n log n), i. e., the classical information lower bound holds for quantum decision trees when the input permutations are unrestricted.in this paper we show that the classical information lower bound holds, up to an additive linear term, for quantum decision trees for any partial order p. precisely, we prove qε(p) ≥ c log2 e(p)-c'n where c,c' > 0 are constants and e(p) is the number of linear orderings consistent with p. our proof builds on an interesting connection between sorting and korner's graph entropy that was first noted and developed by kahn and kim (jcss 51(1995), 390--399).
eisenberg-gale markets: algorithms and structural properties. we define a new class of markets, the eisenberg-gale markets. this class contains fisher's linear market, markets from the resource allocation framework of kelly kelly, as well as numerous interesting new markets.we obtain combinatorial, strongly polynomial algorithms for severalmarkets in this class. our algorithms have a simple description as ascending price auctions. our algorithms lead to insights into the efficiency, fairness, rationality of solutions, and competition monotonicity of these markets. a classification of eisenberg-gale markets w.r.t. these properties reveals a surprisingly rich set of possibilities.
on computing the minima of quadratic forms (preliminary report) the following problem was recently raised by c. william gear [1]: let f(x1,x2,...,xn) &equil; &sgr;i&le;j a'ijxixj + &sgr;i bixi +c be a quadratic form in n variables. we wish to compute the point x&rarr;(0) &equil; (x1(0),...,xn(0)), at which f achieves its minimum, by a series of adaptive functional evaluations. it is clear that, by evaluating f(x&rarr;) at 1/2(n+1)(n+2)+1 points, we can determine the coefficients a'ij,bi,c and thereby find the point x&rarr;(0). gear's question is, &ldquo;how many evaluations are necessary?&rdquo; in this paper, we shall prove that o(n2) evaluations are necessary in the worst case for any such algorithm.
on the submodularity of influence in social networks. we prove and extend a conjecture of kempe, kleinberg, and tardos (kkt) on the spread of influence in social networks. a social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. a simple way to model the diffusion of ideas, innovative behavior, or "word-of-mouth" effects on such a graph is to consider an increasing process of "infected" (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. such a model was introduced by kkt in [7,8] where the authors also impose several natural assumptions: the threshold values are (uniformly) random to account for our lack of knowledge of the true values; and the activation functions are monotone and submodular, i.e. have "diminishing returns." the monotonicity condition indicates that a node is more likely to become active if more of its neighbors are active, while the submodularity condition, indicates that the marginal effect of each neighbor is decreasing when the set of active neighbors increases. for an initial set of active nodes s, let σ(s) denote the expected number of active nodes at termination. here we prove a conjecture of kkt: we show that the function σ(s) is submodular under the assumptions above. we prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination. in other words, our results demonstrate that "local" submodularity is preserved "globally" under diffusion processes. this is of natural computational interest, as many optimization problems have good approximation algorithms for submodular functions. in particular, our results coupled with an argument in [7] imply that a greedy algorithm gives an (1-1/e-ε)-approximation algorithm for maximizing σ(s) among all sets s of a given size. this result has important practical implications for many social network analysis problems, notably viral marketing.
on the average behavior of set merging algorithms (extended abstract) in this paper we study the expected running time of a variety of algorithms that perform set merging. the set merging problem (for example, see ahu [1]) is concerned with using suitable data structures to represent partition of a set s &equil; { 1,2, .... ,n} so that a sequence of instructions of the form &ldquo;x &xgr; y&rdquo;, meaning &ldquo;find the subset containing x; find the subset containing y; merge the two subsets if they are different.&rdquo; may be carried out efficiently. several alternative data structures for solving this problem are known, and their worse-case complexity fairly well understood [3], [4], [5], [8]. in contrast, the average behavior of even the most basic of these schemes remains an open problem [6]. it is the purpose of the present paper to determine the average behavior for several of the set merging algorithms commonly known.
a 3-query pcp over integers. a classic result due to haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field fq where each equation depends on exactly 3 variables and at least a fraction (1-ε) of the equations can be satisfied, it is np-hard to satisfy even a fraction (1/q+ε) of the equations. in this work, we prove the analog of håstad's result for equations over the integers (as well as the reals). formally, we prove that for every ε,δ > 0, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is np-hard to distinguish between the following two cases: (i) there is an assignment of integer values to the variables that satisfies at least a fraction (1-ε) of the equations, and (ii) no assignmenteven of real values to the variables satisfies more than a fraction δ of the equations.
some complexity questions related to distributive computing (preliminary report) let m &equil; {0, 1, 2, ..., m&mdash;1} , n &equil; {0, 1, 2,..., n&mdash;1} , and f:m &times; n &rarr; {0, 1} a boolean-valued function. we will be interested in the following problem and its related questions. let i &egr; m, j &egr; n be integers known only to two persons p1 and p2, respectively. for p1 and p2 to determine cooperatively the value f(i, j), they send information to each other alternately, one bit at a time, according to some algorithm. the quantity of interest, which measures the information exchange necessary for computing f, is the minimum number of bits exchanged in any algorithm. for example, if f(i, j) &equil; (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from p1 to p2 will enable p2 to determine f(i, j), and this is clearly the best possible. the above problem is a variation of a model of abelson [1] concerning information transfer in distributive computions.
degree-constrained network flows. a d-furcated flow is a network flow whose support graph has maximum out degree d. take a single-sink multi-commodity flow problem on any network and with any set of routing demands. then we show that the existence of feasible fractional flow with node congestion one implies the existence of a d-furcated flow with congestion at most 1+1/(d-1), for d ≥ 2. this result is tight, and sothe congestion gap for d-furcated flows is bounded andexactly equal to 1+ 1/(d-1). for the case d=1 (confluent flows), it is known that the congestion gap is unbounded, namely θ(log n). thus, allowing single-sink multicommodity network flows to increase their maximum out degree from one to two virtually eliminates this previously observed congestion gap. as a corollary we obtain a factor 1 + 1/(d-1)-approximation algorithm for the problem of finding a minimum congestion d-furcated flow; we also prove that this problem is max snp-hard. using known techniques these results also extend to degree-constrained unsplittable routing,where each individual demand must be routed along a unique path.
efficient dynamic programming using quadrangle inequalities dynamic programming is one of several widely used problem-solving techniques in computer science and operation research. in applying this technique, one always seeks to find speed-up by taking advantage of special properties of the problem at hand. however, in the current state of art, ad hoc approaches for speeding up seem to be characteristic; few general criteria are known. in this paper we give a quadrangle inequality condition for rendering speed-up. this condition is easily checked, and can be applied to several apparently different problems. for example, it follows immediately from our general condition that the construction of optimal binary search trees may be speeded up from o(n3) steps to o(n2), a result that was first obtained by knuth using a different and rather complicated argument.
vertex cuts, random walks, and dimension reduction in series-parallel graphs. we consider questions about vertex cuts in graphs, random walks in metric spaces, and dimension reduction in l1 and l2; these topics are intimately connected because they can each be reduced to the existence ofvarious families of real-valued lipschitz maps on certain metric spaces. we view these issues through the lens of shortest-path metricson series-parallel graphs, and we discussthe implications for a variety of well-known open problems. our main results follow. every n-point series-parallel metric embeds into l1dom with o(√ log n) distortion, matchinga lower bound of newman and rabinovich. our embeddings yield an o(√log n) approximation algorithm for vertex sparsestcut in such graphs, as well as an o(√log k) approximate max-flow/min-vertex-cut theorem for series-parallel instances withk terminals, improving over the o(log n) and o(log k) boundsfor general graphs. every n-point series-parallel metric embeds withdistortion d into l1d with d = n1/ω(d2),matching the dimension reduction lower bound of brinkman andcharikar. there exists a constant c > 0 such that if (x,d) is aseries-parallel metric then for every stationary, reversible markovchain ztt=0∞ on x, we have for all t ≥ 0, e[d(zt,z0)2] ≤ ct ·, e[d(z0,z1)2]. more generally, we show thatseries-parallel metrics have markov type 2. this generalizesa result of naor, peres, schramm, and sheffield for trees.
on the parallel computation for the knapsack problem we are interested in the complexity of solving the knapsack problem with n input real numbers on a parallel computer with real arithmetic and branching operations. a processor-time tradeoff constraint is derived; in particular, it is shown that an exponential number of processors have to be used if the problem is to be solved in time t &le; @@@@n/2.
interval completion with few edges. we present an algorithm with runtime o(k(2k)n3 * m) for the following np-complete problem: given an arbitrary graph g on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to g? this resolves the long-standing open question, first posed by kaplan, shamir and tarjan, of whether this problem could be solved in time f(k) * n(o(1)).the problem has applications in physical mapping of dna and in profile minimization for sparse matrix computations. for the first application, our results show tractability for the case of a small number k of false negative errors, and for the second, a small number k of zero elements in the envelope. our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph, and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. the presented result is surprising, as it was not believed that a bounded search tree algorithm would suffice to answer the open question affirmatively.
the entropic limitations on vlsi computations (extended abstract) in this paper we will explore the limitations imposed by entropic constraints, both in generality and for specific problems. we list below the main questions that we will address. (1) in the binary number system, addition is easy while multiplication is hard for vlsi. is there an &ldquo;ideal&rdquo; number representation, in which all arithmetic operations have efficient vlsi implementations? (2) can one build multipliers for binary numbers, which achieve both small area and fast average computation time? (3) thompson's technique applies only to multiple output functions. how can one prove area-time bounds for single output functions? (4) what other ways are there for deriving entropic constraints from consideration of data movement? answers to these questions will be discussed in the ensuing sections.
tight bounds for asynchronous randomized consensus. a distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. however, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes. this work proves that the total step complexity of randomized consensus is θ(n2) in an asynchronous shared memory systemusing multi-writer multi-reader registers. the bound is achieved by improving both the lower and the upper bounds for this problem. in addition to improving upon the best previously known result bya factor of log2 n, the lower bound features agreatly streamlined proof. both goals are achieved through restricting attention to a set of layered executions andusing an isoperimetric inequality for analyzing their behavior. the matching algorithm decreases the expected total step complexity by a log n factor, by leveraging themulti-writing capability of the shared registers. its correctness proof is facilitated by viewing each execution of the algorithmas a stochastic process and applying kolmogorov's inequality.