waashk/dblp huggingface dataset:
quadratic forms on graphs. we introduce a new graph parameter, called the grothendieck constant of a graph g=(v,e), which is defined as the least constant k such that for every a:e→r,supf:v→s|v|-1 σ(u,v) ∈ e a(u,v) · ‹f(u),f(v)› ≤ k supf:v→(-1,+1) σ(u,v)∈ e a(u,v) · f(u)f(v).the classical grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑u,v∈ea(u,v)f(vover all f: v →-1,1, which arises in the study of correlation clustering and in the investigation of the spin glass model. we give upper and lower estimates for the integrality gap of this program. we show that the integrality gap is o(log θḡ)) where θ(ḡ) is the lovász theta function of the complement of g, which is always smaller than the chromatic number of g. this yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs g. we also show that the maximum possible integrality gap is always at least ω(log ω(g)), where ω(g) is the clique number of g. in particular it follows that the maximum possible integrality gap for the complete graph on n θ vertices with no loops is ⏷(log n ). more generally, the maximum possible integrality gap for any perfect graph with chromatic number n is ⏷(log n). the lower bound for the complete graph improves a result of kashin and szarek on gram matrices of uniformly bounded functions, and settles a problem of megretski and of charikar and wirth.
transformations on straight line programs-preliminary version we consider a program schema that models straight line intermediate level code. a complete set of equivalence preserving transformations on programs is found for the case in which programs are equivalent if and only if their output functions are identical. this result is extended to the case in which programs are deemed equivalent if their output functions can be shown equivalent under a fixed set of algebraic laws. it is also shown that in the no algebra case and in cases where certain types of algebraic identities are allowed the problem of finding optimal code under a reasonable cost function can be reduced to finding a desired sequence of topological and algebraic transformations on programs.
a characterization of span program size and improved lower bounds for monotone span programs. we give a characterization of span program size by a combinatorial-algebraic measure. the measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.in the monotone case our new methods yield nω(log n) lower bounds for the monotone span program complexity of explicit boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. we also identify a property of bipartite graphs that is sufficient for constructing boolean functions with large monotone span program complexity.
derandomization of auctions. we study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. prior to this work, the only auctions known to be approximately optimal in the worst case employed randomization. our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auctions. we give a fairly general derandomization technique for turning any randomized mechanism into an asymmetric deterministic one with approximately the same revenue. in doing so, we bypass the impossibility result for symmetric deterministic auctions and show that asymmetry is nearly as powerful as randomization for solving optimal mechanism design problems. our general construction involves solving an exponential-sized flow problem and thus is not polynomial-time computable. to complete the picture, we give an explicit polynomial-time construction for derandomizing a specific auction with good worst-case revenue. our results are based on toy problems that have a flavor similar to the hat problem from [3].
a linear time algorithm for computing the voronoi diagram of a convex polygon we present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. using this algorithm, we show that the voronoi diagram of n points in the plane can be computed in &thgr;(n) time when these points form the vertices of a convex polygon in, say, counterclockwise order. this settles an outstanding open problem in computational geometry. our techniques can also be used to obtain linear time algorithms for computing the farthest-point voronoi diagram and the medial axis of a convex polygon and for deleting a vertex from a general planar voronoi diagram.
approximating the cut-norm via grothendieck's inequality. the cut-norm $||a||_c$ of a real matrix $a=(a_{ij})_{i\in r,j\in s}$ is the maximum, over all $i \subset r$, $j \subset s$, of the quantity $|\sum_{i \in i, j\in j} a_{ij}|$. this concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. here we show that the problem of approximating the cut-norm of a given real matrix is max snp hard, and we provide an efficient approximation algorithm. this algorithm finds, for a given matrix $a=(a_{ij})_{i\in r,j\in s}$, two subsets $i \subset r$ and $j \subset s$, such that $|\sum_{i \in i, j\in j} a_{ij}| \geq \rho ||a||_c$, where $\rho>0$ is an absolute constant satisfying $\rho >0.56$. the algorithm combines semidefinite programming with a rounding technique based on grothendieck's inequality. we present three known proofs of grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. these proofs contain rounding techniques which go beyond the random hyperplane rounding of goemans and williamson [j. acm, 42 (1995), pp. 1115-1145], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.
testing subgraphs in directed graphs. let h be a fixed directed graph on h vertices, let g be a directed graph on n vertices and suppose that at least εn2 edges have to be deleted from it to make it h-free. we show that in this case g contains at least f(ε, h)nh copies of h. this is proved by establishing a directed version of szemerédi's regularity lemma, and implies that for every h there is a one-sided error property tester whose query complexity is bounded by a function of ε only for testing the property ph of being h-free.as is common with applications of the undirected regularity lemma, here too the function 1/f(ε,h) is an extremely fast growing function in ε. we therefore further prove a precise characterization of all the digraphs h, for which f(ε,h) has a polynomial dependency on ε. this implies a characterization of all the digraphs h, for which the property of being h-free has a one-sided error property tester whose query complexity is polynomial in 1/ε. we further show that the same characterization also applies to two-sided error property testers as well. a special case of this result settles an open problem raised by the first author in (alon, proceedings of the 42nd ieee focs, ieee, new york, 2001, pp. 434-441). interestingly, it turns out that if ph has a polynomial query complexity, then there is a two-sided ε-tester for ph that samples only o(1/ε) vertices, whereas any one-sided tester for ph makes at least (1/ε)d/2 queries, where d is the average degree of h. we also show that the complexity of deciding if for a given directed graph h, ph has a polynomial query complexity, is np-complete, marking an interesting distinction from the case of undirected graphs.for some special cases of directed graphs h, we describe very efficient one-sided error property-testers for testing ph. as a consequence we conclude that when h is an undirected bipartite graph, we can give a one-sided error property tester with query complexity o((1/ε)h/2), improving the previously known upper bound o((1/ε)h2). the proofs combine combinatorial, graph theoretic and probabilistic arguments with results from additive number theory.
node-disjoint paths on the mesh and a new trade-off in vlsi layout. a number of basic models for vlsi layout are based on the construction of node-disjoint paths between terminals on a multilayer grid. in this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. building on work of cutler and shiloach [ networks, 8 (1978), pp. 253--278], aggarwal et al. [ proc. 26th ieee symposium on foundations of computer science , portland, or, 1985; algorithmica, 6 (1991), pp. 241--255], and aggarwal, klawe, and shor [ algorithmica}, 6 (1991), pp. 129--151], we prove an upper-bound trade-off between these two quantities in a general multilayer grid model. as a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart.
every monotone graph property is testable. a graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract family of all monotone graph properties was also extensively studied. our main result in this paper is that any monotone graph property can be tested with one-sided error, and with query complexity depending only on ε. this result unifies several previous results in the area of property testing, and also implies the testability of well-studied graph properties that were previously not known to be testable. at the heart of the proof is an application of a variant of szemerédi's regularity lemma. the main ideas behind this application may be useful in characterizing all testable graph properties, and in generally studying graph property testing.as a byproduct of our techniques we also obtain additional results in graph theory and property testing, which are of independent interest. one of these results is that the query complexity of testing testable graph properties with one-sided error may be arbitrarily large. another result, which significantly extends previous results in extremal graph-theory, is that for any monotone graph property p, any graph that is ε -far from satisfying p, contains a subgraph of size depending on ε only, which does not satisfy p. finally, we prove the following compactness statement: if a graph g is ε-far from satisfying a (possibly infinite) set of graph properties p, then it is at least δ p ε-far from satisfying one of the properties.
random sampling and approximation of max-csp problems. we present a new efficient sampling method for approximating r-dimensional maximum constraint satisfaction problems, max-rcsp, on n variables up to an additive error &egr;nr. we prove a newgeneral paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of &egr;nr. our method gives for the first time a polynomial in &egr;&mdash;1 bound on the sample size necessary to carry out the above approximation. moreover, this bound is independent in the exponent on the dimension r. the above method gives a completely uniform sampling technique for all the max-rcsp problems, and improves the best known sample bounds for the low dimensional problems, like max-cut. the method of solution depends on a new result on t he cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. this method could be also of independent interest.
when trees collide: an approximation algorithm for the generalized steiner problem on networks we give the first approximation algorithm for the {\em generalized network steiner tree problem}, a problem in network design. an instance consists of a network with link-costs and, for each pair ${i,j}$ of nodes, an edge-connectivity requirement. the goal is to find a minimum-cost network using the available links and satisfying the requirements. our algorithm outputs a solution whose cost is within $ 2 \log r $ of optimal, where $r$ is the highest requirement value. in the course of proving the performance guarantee, we prove a combinatorial min-max approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. as a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.
dual integer linear programs and the relationship between their optima we consider dual pairs of packing and covering integer linear programs. best possible bounds are found between their optimal values. tight inequalities are obtained relating the integral optima and the optimal rational solutions.
optimal static range reporting in one dimension. we consider static one dimensional range searching problems. these problems are to build static data structures for an integer set s \subseteq u, where u = \{0,1,\dots,2^w-1\}, which support various queries for integer intervals of u. for the query of reporting all integers in s contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. this result holds in the unit cost ram model with word size w and a standard instruction set. we also present a linear space data structure for approximate range counting. a range counting query for an interval returns the number of integers in s contained within the interval. for any constant &egr;>0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+&egr; of the correct answer.
a polynomial quantum algorithm for approximating the jones polynomial. the jones polynomial, discovered in 1984 [18], is an important knot invariant in topology. among its many connections to various mathematical and physical areas, it is known (due to witten [32]) to be intimately connected to topological quantum field theory (tqft). the works of freedman, kitaev, larsen and wang [13, 14] provide an efficient simulation of tqft by a quantum computer, and vice versa. these results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the jones polynomial at the fifth root of unity, e2π i/5, and moreover, that this problem is bqp-complete. unfortunately, this important algorithm was never explicitly formulated. moreover, the results in [13, 14] are heavily based on tqft, which makes the algorithm essentially inaccessible to computer scientists.we provide an explicit and simple polynomial quantum algorithm to approximate the jones polynomial of an n strands braid with m crossings at any primitive root of unity e2π i/k, where the running time of the algorithm is polynomial in m,n and k. our algorithm is based, rather than on tqft, on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the markov trace for the temperly lieb algebra). by the results of [14], our algorithm solves a bqp complete problem.the algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. candidates of particular interest are the approximations of other downwards self-reducible p-hard problems, most notably, the potts model.
deterministic sorting in o(nlog log n) time and linear space. we present a fast deterministic algorithm for integer sorting in linear space. our algorithm sorts n integers in the range {0, 1, 2, &1dots;, m&mdash;1} in linear space in o(n log log n) time. this improves our previous result [8] which sorts in o(n log log n log log log n) time and linear space. this also improves previous best deterministic sorting algorithm [3, 11] which sorts in o(nlog log n) time but uses o(m&egr;) space. our results can also be compared with thorup's previous result [16] which sorts in o(nlog log n) time and linear space but uses randomization.
time-adaptive algorithms for synchronization. we consider concurrent systems in which there is an unknown upper bound on memory access time. such a model is inherently different from the asynchronous model, where no such bound exists, and also from timing-based models, where such a bound exists and is known a priori. the appeal of our model lies in the fact that while it abstracts from implementation details, it is a better approximation of real concurrent systems than the asynchronous model. furthermore, it is stronger than the asynchronous model, enabling us to design algorithms for problems that are unsolvable in the asynchronous model.two basic synchronization problems, consensus and mutual exclusion, are investigated in a shared-memory environment that supports atomic read/write registers. we show that $\theta(\delta\frac{\log \delta}{\log\log \delta})$ is an upper and lower bound on the time complexity of consensus, where $\delta$ is the (unknown) upper bound on memory access time. for the mutual exclusion problem, we design an efficient algorithm that takes advantage of the fact that some upper bound on memory access time exists. the solutions for both problems are even more efficient in the absence of contention, in which case their time complexity is a constant.
adiabatic quantum state generation and statistical zero knowledge. the design of new quantum algorithms has proven to be an extremely difficult task. this paper considers a different approach to the problem, by studying the problem of 'quantum state generation'.we first show that any problem in statistical zero knowledge (including eg. discrete log, quadratic residuosity and gap closest vector in a lattice) can be reduced to an instance of the quantum state generation problem. having shown the generality of the state generation problem, we set the foundations for a new paradigm for quantum state generation. we define 'adiabatic state generation' (asg), which is based on hamiltonians instead of unitary gates. we develop tools for asg including a very general method for implementing hamiltonians (the sparse hamiltonian lemma), and ways to guarantee non negligible spectral gaps (the jagged adiabatic path lemma). we also prove that asg is equivalent in power to state generation in the standard quantum model. after setting the foundations for asg, we show how to apply our techniques to generate interesting superpositions related to markov chains.the asg approach to quantum algorithms provides intriguing links between quantum computation and many different areas: the analysis of spectral gaps and groundstates of hamiltonians in physics, rapidly mixing markov chains, statistical zero knowledge, and quantum random walks. we hope that these links will bring new insights and methods into quantum algorithms.
covert two-party computation. we introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. like standard secure two-party computation, covert two-party computation allows alice and bob, with secret inputs xa and xb respectively, to compute a function f(xa,xb) without leaking any additional information about their inputs. in addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. this allows the construction of protocols that return f(xa,xb) only when it equals a certain value of interest (such as "yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xa,xb) is not a value of interest. since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. we introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the decisional diffie-hellman assumption in the "honest but curious" model. using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the random oracle model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. we remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.
visibly pushdown languages. we propose the class of visibly pushdown languages as embeddings of context-free languages that is rich enough to model program analysis questions and yet is tractable and robust like the class of regular languages. in our definition, the input symbol determines when the pushdown automaton can push or pop, and thus the stack depth at every position. we show that the resulting class vpl of languages is closed under union, intersection, complementation, renaming, concatenation, and kleene-*, and problems such as inclusion that are undecidable for context-free languages are exptime-complete for visibly pushdown automata. our framework explains, unifies, and generalizes many of the decision procedures in the program analysis literature, and allows algorithmic verification of recursive programs with respect to many context-free properties including access control properties via stack inspection and correctness of procedures with respect to pre and post conditions. we demonstrate that the class vpl is robust by giving two alternative characterizations: a logical characterization using the monadic second order (mso) theory over words augmented with a binary matching predicate, and a correspondence to regular tree languages. we also consider visibly pushdown languages of infinite words and show that the closure properties, mso-characterization and the characterization in terms of regular trees carry over. the main difference with respect to the case of finite words turns out to be determinizability: nondeterministic büchi visibly pushdown automata are strictly more expressive than deterministic muller visibly pushdown automata.