waashk/dblp huggingface dataset:
the vpn conjecture is true. we consider the following network design problem. we are given an undirected graph g=(v,e) with edges costs c(e) and a set of terminal nodes w. a hose demand matrix for w is any symmetric matrix [dij] such that for each i, ∑ j ≠ i dij ≤ 1. we must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. an oblivious routing template, in this context, is a simple path pij for each pair i,j ∈ w. given such a template, if we are to route a demand matrix d, then for each i,j we send dij units of flow along each pij. fingerhut et al. and gupta et al. obtained a 2-approximation for this problem, using a solution template in the form of a tree. it has been widely asked and subsequently conjectured [italiano 2006] that this solution actually results in the optimal capacity for the single path vpn design problem; this has become known as the vpn conjecture. the conjecture has previously been proven for some restricted classes of graphs [hurkens 2005, grandoni 2007, fiorini 2007]. our main theorem establishes that this conjecture is true in general graphs. this also gives the first polynomial time algorithm for the single path vpn problem. we also show that the multipath version of the conjecture is false.
sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. the connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. in recent years, this connection has prominently figured in several tight ugc-based hardness results. we show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. specifically, we convert linear programming integrality gaps for the multiway cut, 0-extension, and and metric labeling problems into ugc-based hardness results. qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthmover linear program) yields the best possible approximation. taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthmover linear program. prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming.
stateless distributed gradient descent for positive linear programs. we develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. our model has a separate "agent" controlling each variable and an agent is allowed to read-off the current values only of those constraints in which it has non-zero coefficients. this is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets. the most appealing feature of our algorithms is their simplicity and polylogarithmic convergence. for the packing lp max{cx | ax i = exp[1ε * (aix/bi -1)] for each constraint i and each agent j iteratively increases (resp. decreases) xj multiplicatively if ajt y is too small (resp. large) as compared to cj. our algorithm starting from a feasible solution, always maintains feasibility, and computes a (1+epsilon) approximation in poly((ln (mn a_max))ε) rounds. here m and n are number of rows and columns of a and a_max, also known as the "width" of the lp, is the ratio of maximum and minimum non-zero entries aij/(bicj). similar algorithm works for the covering lp min{by | at y >= c, y >= 0} as well. while exponential dual variables are used in several packing/ covering lp algorithms before [25, 9, 13, 12, 26, 16], this is the first algorithm which is both stateless and has polylogarithmic convergence. our algorithms can be thought of as applying distributed gradient descent/ascent on a carefully chosen potential. our analysis differs from those of previous multiplicative update based algorithms and argues that while the current solution is far away from optimality, the potential function decreases/increases by a significant factor.
lossy trapdoor functions and their applications. we propose a new general primitive called lossy trapdoor functions (lossy tdfs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional diffie-hellman (ddh) problem and the worst-case hardness of lattice problems. using lossy tdfs, we develop a new approach for constructing several important cryptographic primitives, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems. all of the constructions are simple, efficient, and black-box. these results resolve some long-standing open problems in cryptography. they give the first known injective trapdoor functions based on problems not directly related to integer factorization, and provide the first known cca-secure cryptosystem based solely on the worst-case complexity of lattice problems.
fast-converging tatonnement algorithms for one-time and ongoing market problems. why might markets tend toward and remain near equilibrium prices? in an effort to shed light on this question from an algorithmic perspective, this paper formalizes the setting of ongoing markets, by contrast with the classic market scenario, which we term one-time markets. the ongoing market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. as such, it appears to be a more plausible model of actual markets. for both market settings, this paper defines and analyzes variants of a simple tatonnement algorithm that differs from previous algorithms that have been subject to asymptotic analysis in three significant respects: the price update for a good depends only on the price, demand, and supply for that good, and on no other information; the price update for each good occurs distributively and asynchronously; the algorithms work (and the analyses hold) from an arbitrary starting point. our algorithm introduces a new and natural update rule. we show that this update rule leads to fast convergence toward equilibrium prices in a broad class of markets that satisfy the weak gross substitutes property. these are the first analyses for computationally and informationally distributed algorithms that demonstrate polynomial convergence. our analysis identifies three parameters characterizing the markets, which govern the rate of convergence of our protocols. these parameters are, broadly speaking: 1. a bound on the fractional rate of change of demand for each good with respect to fractional changes in its price. 2. a bound on the fractional rate of change of demand for each good with respect to fractional changes in wealth. 3. the closeness of the market to a fisher market (a market with buyers starting with money alone). we give two types of protocols. the first type assumes global knowledge of only (an upper bound on) the first parameter. for this protocol, we also provide a matching lower bound in terms of these parameters for the one-time market. our second protocol, which is analyzed for the one-time market alone, assumes no global knowledge whatsoever.
decodability of group homomorphisms beyond the johnson bound. given a pair of finite groups g and h, the set of homomorphisms from g to h form an error-correcting code where codewords differ in at least 1/2 the coordinates. we show that for every pair of abelian groups g and h, the resulting code is (locally) list-decodable from a fraction of errors arbitrarily close to its distance. at the heart of this result is the following combinatorial result: there is a fixed polynomial p(•) such that for every pair of abelian groups g and h, if the maximum fraction of agreement between two distinct homomorphisms from g to h is λ, then for every ε> 0 and every function f:g -> h, the number of homomorphisms that have agreement λ + ε with f is at most p(1/ε). we thus give a broad class of codes whose list-decoding radius exceeds the "johnson bound". examples of such codes are rare in the literature, and for the ones that do exist, "combinatorial" techniques to analyze their list-decodability are limited. our work is an attempt to add to the body of such techniques. we use the fact that abelian groups decompose into simpler ones and thus codes derived from homomorphisms over abelian groups may be viewed as certain "compositions" of simpler codes. we give techniques to lift list-decoding bounds for the component codes to bounds for the composed code. we believe these techniques may be of general interest.
towards an optimal separation of space and length in resolution. most state-of-the-art satisfiability algorithms today are variants of the dpll procedure augmented with clause learning. the main bottleneck for such algorithms, other than the obvious one of time, is the amount of memory used. in the field of proof complexity, the resources of time and memory correspond to the length and space of resolution proofs. there has been a long line of research trying to understand these proof complexity measures, as well as relating them to the width of proofs, i.e., the size of the largest clause in the proof, which has been shown to be intimately connected with both length and space. while strong results have been proven for length and width, our understanding of space is still quite poor. for instance, it has remained open whether the fact that a formula is provable in short length implies that it is also provable in small space (which is the case for length versus width), or whether on the contrary these measures are completely unrelated in the sense that short proofs can be arbitrarily complex with respect to space. in this paper, we present some evidence that the true answer should be that the latter case holds and provide a possible roadmap for how such an optimal separation result could be obtained. we do this by proving a tight bound of theta(√(n)) on the space needed for so-called pebbling contradictions over pyramid graphs of size n. also, continuing the line of research initiated by (ben-sasson 2002) into trade-offs between different proof complexity measures, we present a simplified proof of the recent length-space trade-off result in (hertel and pitassi 2007), and show how our ideas can be used to prove a couple of other exponential trade-offs in resolution.
an effective ergodic theorem and some applications. this work is a synthesis of recent advances in computable analysis with the theory of algorithmic randomness. in this theory, we try to strengthen probabilistic laws, i.e., laws which hold with probability 1, to laws which hold in their pointwise effective form - i.e., laws which hold for every individual constructively random point. in a tour-de-force, v'yugin proved an effective version of the ergodic theorem which holds when the probability space, the transformation and the random variable are computable. however, v'yugin's theorem cannot be directly applied to many examples, because all computable functions are continuous, and many applications use discontinuous functions. we prove a stronger effective ergodic theorem to include a restriction of braverman's "graph-computable functions". we then use this to give effective ergodic proofs of the effective versions of levy-kuzmin and khinchin theorems relating to continued fractions.
inverse conjecture for the gowers norm is false. let p be a fixed prime number and n be a large integer. the "inverse conjecture for the gowers norm" states that if the "d-th gowers norm" of a function f:fnp to fp is non-negligible, that is larger than a constant independent of n, then f has a non-trivial correlation with a degree d-1 polynomial. the conjecture is known to hold for d=2,3 and for any prime p. in this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. essentially the same result, with different bounds for correlation, was independently obtained by green and tao. their analysis uses a modification of a ramsey-type argument of alon and beigel to show inapproximability of certain functions by low-degree polynomials. we observe that a combination of our results with the argument of alon and beigel implies the inverse conjecture to be false for any prime p, for d = p2.
logconcave random graphs. we propose the following model of a random graph on n vertices. let f be a distribution in r+n(n-1)/2 with a coordinate for every pair ij with 1 ≤ i,j ≤ n. then gf,p is the distribution on graphs with n vertices obtained by picking a random point x from f and defining a graph on n vertices whose edges are pairs ij for which xij ≤ p. the standard erdos-renyi model is the special case when f is uniform on the 0-1 unit cube. we determine basic properties such as the connectivity threshold for quite general distributions. we also consider cases where the xij are the edge weights in some random instance of a combinatorial optimization problem. by choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.
communication in the presence of replication. we consider the following problem. suppose that a big amount of data is distributed among several parties, so that each party misses only few pieces of data. the parties wish to perform some global computation on the data while minimizing the communication between them. this situation is common in many real-life scenarios. a naive solution to this problem is to first perform a synchronization step, letting one party learn all pieces of data, and then let this party perform the required computation locally. we study the question of obtaining better solutions to the problem, focusing mainly on the case of computing low-degree polynomials via non-interactive protocols. we present interesting connections between this problem and the well studied cryptographic problem of secret sharing. we use this connection to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing. the relation with open problems from the area of secret sharing also provides evidence for the difficulty of resolving some of the questions we leave open.
algebraic property testing: the role of invariance. we argue that the symmetries of a property being tested play a central role in property testing. we support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space kn over a field k to a subfield f. we consider (f-)linear properties that are invariant under linear transformations of the domain and prove that an o(1)-local "characterization" is a necessary and sufficient condition for o(1)-local testability. when |k| = o(1). (a local characterization of a property is a definition of a property in terms of local constraints satisfied by functions exhibiting a property.) for the subclass of properties that are invariant under affine transformations of the domain, we prove that the existence of a single o(1)-local constraint implies o(1)-local testability. these results generalize and extend the class of algebraic properties, most notably linearity and low-degree-ness, that were previously known to be testable. in particular, the extensions include properties satisfied by functions of degree linear in n that turn out to be o(1)-locally testable. our results are proved by introducing a new notion that we term "formal characterizations". roughly this corresponds to characterizations that are given by a single local constraint and its permutations under linear transformations of the domain. our main testing result shows that local formal characterizations essentially imply local testability. we then investigate properties that are linear-invariant and attempt to understand their local formal characterizability. our results here give coarse upper and lower bounds on the locality of constraints and characterizations for linear-invariant properties in terms of some structural parameters of the property we introduce. the lower bounds rule out any characterization, while the upper bounds give formal characterizations. combining the two gives a test for all linear-invariant properties with local characterizations. we believe that invariance of properties is a very interesting notion to study in the context of property testing in general and merits a systematic study. in particular, the class of linear-invariant and affine-invariant properties exhibits a rich variety among algebraic properties and offer better intuition about algebraic properties than the more limited class of low-degree functions.
unique games on expanding constraint graphs are easy: extended abstract. we present an efficient algorithm to find a good solution to the unique games problem when the constraint graph is an expander. we introduce a new analysis of the standard sdp in this case that involves correlations among distant vertices. it also leads to a parallel repetition theorem for unique games when the graph is an expander.
the chow parameters problem. in the 2nd annual focs (1961), c. k. chow proved that every boolean threshold function is uniquely determined by its degree-0 and degree-1 fourier coefficients. these numbers became known as the chow parameters. providing an algorithmic version of chow's theorem --- i.e., efficiently constructing a representation of a threshold function given its chow parameters --- has remained open ever since. this problem has received significant study in the fields of circuit complexity, game theory and the design of voting systems, and learning theory. in this paper we effectively solve the problem, giving a randomized ptas with the following behavior: theorem: given the chow parameters of a boolean threshold function f over n bits and any constant ε > 0, the algorithm runs in time o(n2 log2 n) and with high probability outputs a representation of a threshold function f' which is ε-close to f. along the way we prove several new results of independent interest about boolean threshold functions. in addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called "halfspaces"): an ~o(n2)-time uniform distribution algorithm for learning halfspaces to constant accuracy in the "restricted focus of attention" (rfa) model of ben-david et al. [3]. this answers the main open question of [6]. an o(n2)-time agnostic-type learning algorithm for halfspaces under the uniform distribution. this contrasts with recent results of guruswami and raghavendra [21] who show that the learning problem we solve is np-hard under general distributions. as a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution pac learning model. for constant ε our algorithm runs in time ~o(n2), which substantially improves on previous bounds and nearly matches the ω(n2) bits of training data that any successful learning algorithm must use.
a (de)constructive approach to program checking. program checking, program self-correcting and program self-testing were pioneered by [blum and kannan] and [blum, luby and rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by input basis rather than full program verification. work in the field of program checking focused on designing, for specific functions, checkers, testers and correctors which are more efficient than the best program known for the function. these were designed utilizing specific algebraic, combinatorial or completeness properties of the function at hand. in this work we introduce a novel composition methodology for improving the efficiency of program checkers. we use this approach to design a variety of program checkers that are provably more efficient, in terms of circuit depth, than the optimal program for computing the function being checked. extensions of this methodology for the cases of program testers and correctors are also presented. in particular, we show: for all i ≥ 1, every language in rnci (that is nco-hard under ncz-reductions) has a program checker in rnci-1. in addition, for all i ≥ 1, every language in rnci (that is nco-hard under acz-reductions) has a program corrector, tester and checker in raci-1. this is the first time checkers are designed for a wide class of functions characterized only by its complexity, rather than by algebraic or combinatorial properties. this characterization immediately yields new and efficient checkers for languages such as graph connectivity, perfect matching and bounded-degree graph isomorphism. constant-depth checkers, testers and correctors for matrix multiplication, inversion, determinant and rank. all previous program checkers, testers and correctors for these problems run in nearly logarithmic depth. moreover, except for matrix multiplication, they all require the use of the library notion of [blum-luby-rubinfeld], in which checkers have access to a library of programs for various matrix functions, rather than only having access to a program for the function being checked. furthermore, we provide conditions under which program libraries can be eliminated. important ingredients in these results are new and very efficient checkers for complete languages in low complexity classes (e.g. nco). these constructions are based on techniques that were developed in the field of cryptography.
trapdoors for hard lattices and new cryptographic constructions. we show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. a core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete gaussian probability distribution whose standard deviation is essentially the length of the longest gram-schmidt vector of the basis. a crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
infeasibility of instance compression and succinct pcps for np. the or-sat problem asks, given boolean formulae φ1,...,φm each of size at most n, whether at least one of the φi's is satisfiable. we show that there is no reduction from or-sat to any set a where the length of the output is bounded by a polynomial in n, unless np ⊆ conp/poly, and the polynomial-time hierarchy collapses. this result settles an open problem proposed by bodlaender et. al. [4] and harnik and naor [15] and has a number of implications. a number of parametric $\np$ problems, including satisfiability, clique, dominating set and integer programming, are not instance compressible or polynomially kernelizable unless np ⊆ conp/poly. satisfiability does not have pcps of size polynomial in the number of variables unless np ⊆ conp/poly. an approach of harnik and naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (buhrman-hitchcock) there are no subexponential-size hard sets for np unless np is in co-np/poly. we also study probabilistic variants of compression, and show various results about and connections between these variants. to this end, we introduce a new strong derandomization hypothesis, the oracle derandomization hypothesis, and discuss how it relates to traditional derandomization assumptions.