waashk/dblp huggingface dataset:
finding small balanced separators. let g be an n-vertex graph that has a vertex separator of size k that partitions the graph into connected components of size smaller than α n, for some fixed 2/3 ≤ α < 1. such a separator is called an α-separator. finding an α-separator of size at most k is np-hard. moreover, under reasonable complexity theoretic assumptions, it is shown that this problem is not polynomially solvable even when k=o(log n). in this paper, we give a randomized algorithm that finds an α-separator of size k in the given graph, unless the graph contains an (α+ε)-separator of size strictly less than k, in which case our algorithm finds one such separator. for fixed ε, the running time of our algorithm is no(1)2o(k), which is polynomial for k = o(log n). for bounded degree graphs (as well as for the case of finding balanced edge separators), we present a deterministic algorithm with similar running time.our algorithm involves (among other things) a new concept that we call (ε,k)-samples. this is related to the notion of detection sets for network failures, introduced by kleinberg [focs 2000]. our proofs adapt and simplify techniques that were introduced by kleinberg. as a by-product, our proof improves the known bounds on the size of detection sets. we also show applications of (ε,k)-samples to problems in approximation algorithms and rigorous analysis of heuristics.
on the integrality ratio of semidefinite relaxations of max cut. max cut is the problem of partitioning the vertices of a graph into two sets, maximizing the number of edges joining these sets. this problem is np-hard. goemans and williamson proposed an algorithm that first uses a semidefinite programming relaxation of max cut to embed the vertices of the graph on the surface of an n dimensional sphere, and then uses a random hyperplane to cut the sphere in two, giving a cut of the graph. they show that the expected number of edges in the random cut is at least &agr; \cdot sdp, where &agr; \simeq 0.87856 and sdp is the value of the semidefinite program.this manuscript shows the following results:1. the integrality ratio of the semidefinite program is &agr;. the previously known bound on the integrality ratio was roughly 0.8845.2. in the presence of the so called &ldquo;triangle constraints&rdquo;, the integrality ratio is no better than roughly 0.891. the previously known bound was above 0.95.
hardness of approximate two-level logic minimization and pac learning with membership queries. producing a small dnf expression consistent with given data is a classical problem in computer science that occurs in a number of forms and has numerous applications. we consider two standard variants of this problem. the first one is two-level logic minimization or finding a minimal dnf formula consistent with a given complete truth table (tt-mindnf. this problem was formulated by quine in 1952 and has been since one of the key problems in logic design. it was proved np-complete by masek in 1979. the best known polynomial approximation algorithm is based on a reduction to the set-cover problem and produces a dnf formula of size o(d ∙ opt), where d is the number of variables. we prove that tt-mindnf is np-hard to approximate within dγ for some constant γ > 0, establishing the first inapproximability result for the problem.the other dnf minimization problem we consider is pac learning of dnf expressions when the learning algorithm must output a dnf expression as its hypothesis (referred to as proper learning). we prove that dnf expressions are np-hard to pac learn properly even when the learner has access to membership queries, thereby answering a long-standing open question due to valiant [40]. finally, we show that inapproximability of tt-mindnf implies hardness results for restricted proper learning of dnf expressions with membership queries even when learning with respect to the uniform distribution only.
a decidable propositional probabilistic dynamic logic a propositional version of feldman and harel's pr (dl) is defined, and shown to be decidable. the logic allows propositional-level formulas involving probabilistic programs, and contains full real-number theory for dealing with probabilities. the decidability proof introduces model schemes, which seem to be the most basic structures relating programs and probabilities.
fault tolerance of minimal path routings in a network we prove the conjectured 2t-1 pound on the diameter of a surviving quote graph from which t edges are removed, under the assumption that a minimal path routing is used we also prove the related conjecture for node failure, and combine the results into a more general theorem.
a probabilistic dynamic logic a logic, pr(dl), is presented, which enables reasoning about probabilistic programs or, alternatively, reasoning probabilistically about conventional programs. the syntax of pr(dl) derives from pratt's first-order dynamic logic and the semantics extends kozen's semantics of probabilistic programs. an axiom system for pr(dl) is presented and shown to be complete relative to an extension of first-order analysis. for discrete probabilities it is shown that first-order analysis actually suffices. examples are presented, both of the expressive power of pr(dl), and of a proof in the axiom system.
optimal algorithms for byzantine agreement we exhibit randomized byzantine agreement (ba) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. our ba algorithms do not require trusted parties, preprocessing, or non-constructive arguments. given private communication lines, we show that n processors can reach ba in expected constant time in a syncronous network if any < n/3 faults occur in an asynchronous network if any < n/4 faults occur for both synchronous and asynchronous networks whose lines do not guarantee private communication, we may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries. (thus, in this setting, we tolerate up to n/3 faults even in an asynchronous network.)
optimal online scheduling of parallel jobs with dependencies. we study the following general online scheduling problem. parallel jobs arrive dynamically according to the dependencies between them. each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. we present optimal online algorithms for prams, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested by any job. our work shows that for efficient online scheduling it is necessary to use virtualization, i.e., to schedule parallel jobs on fewer processors than requested while preserving the work. assume that the largest number of processors requested by a job is lambda(n), where 0 > lambda > 1 and n is the number of processors of - a machine. with virtualization, our algorithm for prams has a competitive __________ ratio of 2 + /4lamba + 1 - 1 . our lower bound shows that this ratio _______________ 2lambda is optimal. as lambda goes from 0 to 1, the ratio changes from 2 to 2 + phi, where phi ~ 0.168 is the golden ratio. for hypercubes and ~ one-dimensional meshes we present theta (log n ) -competitive algorithms ______ (log log n) as well as matching lower bounds. without virtualization, no online scheduling algorithm can achieve a competitive ratio smaller than n for lambda = 1. for lambda > 1, the lower bound is 1 + 1 and our _____ 1 - y algorithm for prams achieves this competitive ratio. we prove that tree constraints are complete for the scheduling problem, i.e., any algorithm that solves the scheduling problem if the dependency graph is a tree can be converted to solve the general problem equally efficiently. this shows that the structure of a dependency graph is not as important for online scheduling as it is for offline scheduling, although even simple dependencies make the problem much harder than scheduling independent jobs.
clique-width minimization is np-hard. clique-width is a graph parameter that measures in a certain sense the complexity of a graph. hard graph problems (e.g., problems expressible in monadic second order logic with second-order quantification on vertex sets, that includes np-hard problems) can be solved efficiently for graphs of small clique-width. it is widely believed that determining the clique-width of a graph is np-hard; in spite of considerable efforts, no np-hardness proof has been found so far. we give the first hardness proof. we show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless p=np. we also show that, given a graph g and an integer k, deciding whether the clique-width of g is at most k is nphy complete. this solves a problem that has been open since the introduction of clique-width in the early 1990s.
maximum k-chains in planar point sets: combinatorial structure and algorithms. a chain of a set p of n points in the plane is a chain of the dominance order on p. a k-chain is a subset c of p that can be covered by k chains. a k-chain c is a maximum k-chain if no other k-chain contains more elements than c. this paper deals with the problem of finding a maximum k-chain of p in the cardinality and in the weighted case.using the skeleton s(p) of a point set p introduced by viennot we describe a fairly simple algorithm that computes maximum k-chains in time o(kn log n) and linear space. the basic idea is that the canonical chain partition of a maximum (k-1)-chain in the skeleton s(p) provides k regions in the plane such that a maximum k-chain for p can be obtained as the union of a maximal chain from each of these regions.by the symmetry between chains and antichains in the dominance order we may use the algorithm for maximum k-chains to compute maximum k-antichains for planar points in time o(kn log n). however, for large k one can do better. we describe an algorithm computing maximum k-antichains (and, by symmetry, k-chains) in time o((n2 k) log n) and linear space. consequently, a maximum k-chain can be computed in time o(n3/2 log n) for arbitrary k.the background for the algorithms is a geometric approach to the greene--kleitman theory for permutations. we include a skeleton-based exposition of this theory and give some hints on connections with the theory of young tableaux.the concept of the skeleton of a planar point set is extended to the case of a weighted point set. this extension allows to compute maximum weighted k-chains with an algorithm that is similar to the algorithm for the cardinality case. the time and space requirements of the algorithm for weighted k-chains are o(2kn log(2kn)) and o(2kn), respectively.
competitive generalized auctions. we describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive compatible) and guarantee high "net" profit. we make use of appropriate variants of competitive analysis of algorithms in designing and analyzing our mechanisms. thus, we do not require any probabilistic assumptions on bids.we present two new concepts regarding auctions, that of a cancellable auction and that of a generalized auction. we use cancellable auctions in the design of generalized auctions, but they are of independent interest as well. cancellable auctions have the property that if the revenue collected does not meet certain predetermined criteria, then the auction can be cancelled and the resulting auction is still truthful. the trivial approach (run a truthful auction and cancel if needed) yields an auction that is not necessarily truthfu.generalized auctions can be used to model many problems previously considered in the literature, as well as numerous new problems. in particular, we give the first truthful profit-maximizing auctions for problems such as conditional financing and multicast.
better algorithms for unfair metrical task systems and applications. unfair metrical task systems are a generalization of online metrical task systems. in this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces.
implicit o(1) probe search given a set of n elements from the domain 1, &hellip;, m, we investigate how to arrange them in a table of size n, so that searching for an element in the table can be done in constant time. yao has shown that this cannot be done when the domain is sufficiently large as a function of n ([yao]). [fnss] have shown that this can be done when the domain is linear in the number of elements. we give a constructive solution when the domain m is polynomial in the number of elements n, and give a nonconstructive proof for m no larger than exponential in poly(n). we improve upon [yao] and give better bounds on the maximum m for which implicit o(1) probe search can be done. we achieve our results by showing the tight relationship between hashing and certain encoding problems.
rigorous time/space tradeoffs for inverting functions we provide rigorous time-space tradeoffs for inverting any function. given a function f, we give a time space tradeoff of ts2 = n3q(f), where q(f) is the probability that two random elements are mapped to the same image under f. we also give a more general tradeoff, ts3 = n3, that can invert any function at any point.
lower bounds for the cycle detection problem given a function f over a domain and an element x in the domain, the cycle detection problem is to find a repetition in the sequence of values x, f(x), f(f(x)), f3(x),. . . , if one exists. this paper investigates lower bounds on the number of function evaluations needed when there is a bound on the amount of memory available. for certain restricted classes of algorithms which use two memory locations optimality is achieved. a summary of the major results appears in the final section.
new bounds for parallel prefix circuits in this paper, new upper and lower bounds are obtained for the number of gates in parallel prefix circuits with minimum depth when the number of inputs is a power of two. in addition, structural information concerning these circuits is described. parallel prefix circuits with bounds imposed on the fan-out of the gates are also considered. in both cases, the upper and lower bounds obtained differ by small constant factors.
the parallel complexity of exponentiating polynomials over finite fields modular integer exponentiation (given a, e, and m, compute ae mod m) is a fundamental problem in algebraic complexity for which no efficient parallel algorithm is known. two closely related problems are modular polynomial exponentiation (given a(x), e, and m(x), compute (a(x))e mod m(x)) and polynomial exponentiation (given a(x), e. and t, compute the coefficient of xt in (a(x))e). it is shown that these latter two problems are in nc2 when a(x) and m(x) are polynomials over a finite field whose characteristic is polynomial in the input size.
fast matrix multiplication this paper deals with three aspects of algebraic complexity. the first section is concerned with lower bounds on the number of operations required to compute several functions. several theorems are presented and their proofs sketched. the second section deals with relationships among the complexities of several sets of functions. in the third section, several matrices of general interest are examined and upper bounds on the number of operations required to multiply by them are constructively derived.
polynomial evaluation via the division algorithm: the fast fourier transform revisited a polynomial p(x) can be evaluated at several points x1,...,xm by first constructing a polynomial d(x) which has x1,...,xm as roots, then dividing p(x) by d(x), and finally evaluating the remainder r(x) at x1,...,xm. this method is useful if the coefficient sequence of d(x) can be chosen to be sparse, thus simplifying the construction of r(x). the case m&equil;1 and d(x) &equil; x&minus;x1 is horner's rule, while the case d(x) &equil; xm&minus;1 yields the fast fourier transform algorithm.
an efficient algorithm for determining whether a cubic graph is toroidal the algorithm of the title is presented. it runs in time bounded by a polynomial in the number of the edges of the graph.
sorting and searching in the presence of memory faults (without redundancy). we investigate the design of algorithms resilient to memory faults, i. e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. in this framework, we consider two fundamental problems: sorting and searching. in particular, we prove that any o(nlog n) comparison-based sorting algorithm can tolerate at most o((nlog n)1/2) memory faults. furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to o((nlog n)1/3) faults. we also prove polylogarithmic lower and upper bounds on fault-tolerant searching.
the difficulty of testing for isomorphism against a graph that is given in advance. motivated by a question from [e. fischer, g. kindler, d. ron, s. safra, and a. samorodnitsky, j. comput. system sci., 68 (2004), pp. 753--787], we investigate the number of queries required for testing that an input graph g is isomorphic to a fixed graph h that is given in advance. we correlate this number with a measure of the "complexity" of h that we define here, by proving both an upper bound and a lower bound on the number of queries that depends on this new measure. as far as we know this is the first characterization of this type for graphs.
some properties of precedence languages the classes of languages definable by operator precedence grammars1 and by wirth-weber precedence grammars2 are studied. a grammar is backwards-deterministic3 if no two productions have the same right part. operator precedence grammars have no more generative power than backwards deterministic operator precedence grammars, but wirth-weber precedence grammars (i.e., grammars having unique wirth-weber precedence relations) are more powerful than backwards-deterministic wirth-weber precedence grammars; indeed they can generate any context-free language. an algorithm is developed for finding a wirth-weber precedence grammar equivalent to a given operator precedence grammar, a result of possible practical significance. the operator precedence languages are shown to be a proper subclass of the backwards-deterministic wirth-weber precedence languages which in turn are a proper subclass of the deterministic context-free languages.
monotonicity testing over general poset domains. the field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are `far' from satisfying the property. testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube {1,&ldots;,m}n. these works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.we show that in its most general setting, testing that boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. these problems include: testing that a boolean assignment of variables is close to an assignment that satisfies a specific 2-cnf formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.we then investigate the query complexity of monotonicity testing of both boolean and integer functions over general partial orders. we give algorithms and lower bounds for the general problem, as well as for some interesting special cases. in proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.
lower bounds on the size of boolean formulas: preliminary report let c(n)k be the boolean function of n variables that equals one iff the number of arguments equal to one is a multiple of k. it is shown that every boolean expression for c(n)k, allowing all of the 16 binary connectives, has size exceeding &egr;n log n/log log n, &egr;> 0. this result follows from a general criterion relating the minimum size expression for a boolean function to the kinds of subfunctions obtainable through restriction. lower bounds on formula size for several other functions are obtained. in some cases, the lower bounds are nearly achievable by known constructions.
testing of matrix properties. combinatorial property testing deals with the following relaxation of decision problems: given a fixed property p and an input f, distinguish between the case that f satisfies p, and the case that no input that differs from f in less than some fixed fraction of the places satisfies p. an (&egr;,q)-test for p is a randomized algorithm that queries at most q places of an input x and distinguishes with probability 2/3 between the case that f has the property and the case that at least an &egr;-fraction of the places of f need to be changed in order for it to have the property.here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e as a product order of total orders). the main result here is an (&egr,poly(1/&egr))-test for every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. such properties include the `monotonicity' property and many other properties. a (less efficient) test for such properties with larger fixed size alphabets is also presented. another result is a more efficient test than was previously known for a collection of bipartite graph properties.both collections above are variants of properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations (and some additional relations for the bipartite graph properties). we also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of o(n^{1/10}) exists. the above results identify new classes of efficiently
testing versus estimation of graph properties. tolerant testing is an emerging topic in the field of property testing, which was defined in [m. parnas, d. ron, and r. rubinfeld, j. comput. system sci., 72 (2006), pp. 1012-1042] and has recently become a very active topic of research. in the general setting, there exist properties that are testable but are not tolerantly testable [e. fischer and l. fortnow, proceedings of the $20$th ieee conference on computational complexity, 2005, pp. 135-140]. on the other hand, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable (which was already implicitly proved in [n. alon, e. fischer, m. krivelevich, and m. szegedy, combinatorica, 20 (2000), pp. 451-476] and [o. goldreich and l. trevisan, random structures algorithms, 23 (2003), pp. 23-57]), but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant. in the course of the proof we develop a framework for extending szemer&eacute;di's regularity lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. in particular, we construct a probabilistic algorithm that finds the parameters of a regular partition of an input graph using a constant number of queries, and an algorithm to find a regular partition of a graph using a $\mathrm{tc}_0$ circuit. this, in some ways, strengthens the results of [n. alon, r. a. duke, h. lefmann, v. r&ouml;dl, and r. yuster, j. algorithms, 16 (1994), pp. 80-109].