waashk/dblp huggingface dataset:
polynomial-time theory of matrix groups. we consider matrix groups, specified by a list of generators, over finite fields. the two most basic questions about such groups are membership in and the order of the group. even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic problems (factoring and discrete log); in fact, constructive membership testing in the case of 1 × 1 matrices is precisely the discrete log problem. so the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. one of the new ingredients of this result is the following. a group is called semisimple if it has no abelian normal subgroups. for matrix groups over finite fields, we show that the order of the largest semisimple quotient can be determined in randomized polynomial time (no number theory oracles required and no restriction on parity). as a by-product, we obtain a natural problem that belongs to bpp and is not known to belong either to rp or to corp. no such problem outside the area of matrix groups appears to be known. the problem is the decision version of the above: given a list a of nonsingular d × d matrices over a finite field and an integer n, does the group generated by a have a semisimple quotient of order > n? we also make progress in the area of constructive recognition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become las vegas.
new direct-product testers and 2-query pcps. the "direct product code" of a function f gives its values on all k-tuples (f(x1),...,f(xk)). this basic construct underlies "hardness amplification" in cryptography, circuit complexity and pcps. goldreich and safra [12] pioneered its local testing and its pcp application. a recent result by dinur and goldenberg [5] enabled for the first time testing proximity to this important code in the "list-decoding" regime. in particular, they give a 2-query test which works for polynomially small success probability 1/kα, and show that no such test works below success probability 1/k. our main result is a 3-query test which works for exponentially small success probability exp(-kα). our techniques (based on recent simplified decoding algorithms for the same code [15]) also allow us to considerably simplify the analysis of the 2-query test of [5]. we then show how to derandomize their test, achieving a code of polynomial rate, independent of k, and success probability 1/kα. finally we show the applicability of the new tests to pcps. starting with a 2-query pcp over an alphabet σ and with soundness error 1-δ, rao [19] (building on raz's (k-fold) parallel repetition theorem [20] and holenstein's proof [13]) obtains a new 2-query pcp over the alphabet σk with soundness error exp(-δ2 k). our techniques yield a 2-query pcp with soundness error exp(-δ √k). our pcp construction turns out to be essentially the same as the miss-match proof system defined and analyzed by feige and kilian [8], but with simpler analysis and exponentially better soundness error.
explicit construction of a small epsilon-net for linear threshold functions. we give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. the size of the constructed nets is polynomial in the dimension n and in 1/ε. to the best of our knowledge no such constructions were previously known. our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. as a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c√{n log n}, for any constant c. this improves upon the well known construction of dual bch codes that only guarantee covering radius of n/2 - c√n.
an improved constant-time approximation algorithm for maximum~matchings. this paper studies approximation algorithms for problems on degree-bounded graphs. let n and d be the number of vertices and the degree bound, respectively. this paper presents an algorithm to approximate the size of some maximal independent set with additive error ε n whose running time is o(d2). using this algorithm, it also shows that there are approximation algorithms for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/ε. its approximation algorithm for the maximum matching problem can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. on the contrary, it also shows that every one-sided error tester for the property requires at least ω(n) queries.
a competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. we consider the online problem of scheduling jobs on unrelated machines so as to minimize the total weighted flow time. this problem has an unbounded competitive ratio even for very restricted settings. in this paper we show that if we allow the machines of the online algorithm to have ε more speed than those of the offline algorithm then we can get an o((1+ε-1)2)-competitive algorithm. our algorithm schedules jobs preemptively but without migration. however, we compare our solution to an offline algorithm which allows migration. our analysis uses a potential function argument which can also be extended to give a simpler and better proof of the randomized immediate dispatch algorithm of chekuri-goel-khanna-kumar for minimizing average flow time on parallel machines.
linear time approximation schemes for the gale-berlekamp game and related minimization problems. we design a linear time approximation scheme for the gale-berlekamp switching game and generalize it to a wider class of dense fragile minimization problems including the nearest codeword problem (ncp) and unique games problem. further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. as another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.
artin automorphisms, cyclotomic function fields, and folded list-decodable codes. algebraic codes that achieve list decoding capacity were recently constructed by a careful "folding" of the reed-solomon code. the "low-degree" nature of this folding operation was crucial to the list decoding algorithm. we show how such folding schemes arise out of the artin-frobenius automorphism at primes in galois extensions. using this approach, we construct new folded algebraic-geometric codes for list decoding based on cyclotomic function fields with a cyclic galois group. such function fields are obtained by adjoining torsion points of the carlitz action of an irreducible m ∈ fq[t]. the reed-solomon case corresponds to the simplest such extension (corresponding to the case m=t). in the general case, we need to descend to the fixed field of a suitable galois subgroup in order to ensure the existence of many degree one places that can be used for encoding. our methods shed new light on algebraic codes and their list decoding, and lead to new codes achieving list decoding capacity. quantitatively, these codes provide list decoding (and list recovery/soft decoding) guarantees similar to folded reed-solomon codes but with an alphabet size that is only polylogarithmic in the block length. in comparison, for folded rs codes, the alphabet size is a large polynomial in the block length. this has applications to fully explicit (with no brute-force search) binary concatenated codes for list decoding up to the zyablov radius.
near-perfect load balancing by randomized rounding. we consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. the aim is minimizing the discrepancy between the maximum and minimum load. in every time-step paired processors balance their load as evenly as possible. the direction of the excess token is chosen according to a randomized rounding of the participating loads. we prove that in comparison to the corresponding model of rabani, sinclair, and wanka (1998) with arbitrary roundings, the randomization yields an improvement of roughly a square root of the achieved discrepancy in the same number of time-steps on all graphs. for the important case of expanders we can even achieve a constant discrepancy in o(log n (log log n)3) rounds. this is optimal up to loglog-factors while the best previous algorithms in this setting either require ©(log2 n) time or can only achieve a logarithmic discrepancy. our new result also demonstrates that with randomized rounding the difference between discrete and continuous load balancing vanishes almost completely.
a unified framework for concurrent security: universal composability from stand-alone non-malleability. we present a unified framework for obtaining universally composable (uc) protocols by relying on stand-alone secure non-malleable commitments. essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the crs model, the imperfect crs model, or the timing model)--are obtained as special cases of our framework. this not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions. additionally, this framework allows us to consider new relaxed models of security: we show that uc security where the adversary is a uniform ppt but the simulator is allowed to be a non-uniform ppt (i.e., essentially, traditional uc security, but with a non-uniform reduction) is possible without any trusted set-up. this gives the first results on concurrent secure computation without set-up, which can be used for securely computing "computationally-sensitive" functionalities (e.g., data-base queries, "proof of work"-protocols, or playing bridge on the internet).
message passing algorithms and improved lp decoding. linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding algorithms--- and its amenability to finite-blocklength analysis. several works starting with the work of feldman et al. showed how to analyze lp decoding using properties of expander graphs. this line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. it is possible to do better for the case of random noise, as shown by daskalakis et al. and koetter and vontobel. building on work of koetter and vontobel, we obtain a novel understanding of lp decoding, which allows us to establish a 0.05-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for lp decoding. unlike other techniques, our analysis directly works with the primal linear program and exploits an explicit connection between lp decoding and message passing algorithms. an interesting byproduct of our method is a notion of a "locally optimal" solution that we show to always be globally optimal (i.e., it is the nearest codeword). such a solution can in fact be found in near-linear time by a "re-weighted" version of the min-sum algorithm, obviating the need for linear programming. our analysis implies, in particular, that this re-weighted version of the min-sum decoder corrects up to a 0.05-fraction of errors.
randomly supported independence and resistance. we prove that for any positive integer k, there is a constant ck such that a randomly selected set of ck nk log n boolean vectors with high probability supports a balanced k-wise independent distribution. in the case of k ≤ 2 a more elaborate argument gives the stronger bound ck nk. using a recent result by austrin and mossel this shows that a predicate on t bits, chosen at random among predicates accepting c2 t2 input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. these results are close to tight: we show that there are other constants, ck', such that a randomly selected set of cardinality ck' nk points is unlikely to support a balanced k-wise independent distribution and, for some c>0, a random predicate accepting ct2/log t input vectors is non-trivially approximable with high probability. in a different application of the result of austrin and mossel we prove that, again assuming the unique games conjecture, any predicate on t bits accepting at least (32/33) • 2t inputs is approximation resistant. the results extend from the boolean domain to larger finite domains.
an efficient algorithm for partial order production. we consider the problem of partial order production: arrange the elements of an unknown totally ordered set t into a target partially ordered set s, by comparing a minimum number of pairs in t. special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction. we give an algorithm performing itlb + o(itlb) + o(n) comparisons in the worst case. here, n denotes the size of the ground sets, and itlb denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset. the overall complexity of our algorithm is polynomial. this answers a question of yao (sicomp, 1989). our strategy is to extend the poset s to a weak order w whose corresponding information-theoretic lower bound is provably not much larger than that for s. taking w instead of s as a target poset, we then solve the problem by applying a multiple selection algorithm that performs not much more than itlb comparisons. we base our analysis on the entropy of the target poset s, a quantity that can be efficiently computed and provides a good estimate of itlb.
bit-probe lower bounds for succinct data structures. we prove lower bounds on the redundancy necessary to represent a set s of objects using a number of bits close to the information-theoretic minimum log2 |s|, while answering various queries by probing few bits. our main results are: to represent n ternary values t ∈ {0,1,2}n in terms of u bits b ∈ {0,1}u while accessing a single value ti ∈ {0,1,2} by probing q bits of b, one needs u ≥ (log2 3)n + n/2o(q). this matches an exciting representation by patrascu (focs 2008), later refined with thorup, where u ≤ (log_2 3)n + n/2ω(q). we also note that results on logarithmic forms imply the lower bound u ≥ (log2 3)n + n/logo(1) n if we access ti by probing one cell of log n bits. to represent sets of size n/3 from a universe of n elements in terms of u bits b ∈ {0,1}u while answering membership queries by probing q bits of b, one needs u ≥ log2 n/(n/3) + n/2o(q) - log n. both results above hold even if the probe locations are determined adaptively. ours are the first lower bounds for these fundamental problems; we obtain them drawing on ideas used in lower bounds for locally decodable codes.
finding sparse cuts locally using evolving sets. a local graph partitioning algorithm finds a set of vertices with small conductance (i.e.~a sparse cut) by adaptively exploring a large graph g, starting from a specified vertex. for the algorithm to be local, its complexity must be bounded in terms of the size of the set it outputs, with at most a weak dependence on n, the number of vertices in g. previous local partitioning algorithms find sparse cuts using random walks and personalized pagerank. in this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process, which is a markov chain on sets of vertices. we prove that for any set of vertices a that has conductance at most φ, and for at least half of the starting vertices in a, our algorithm will output (with probability at least half) a set of conductance o(φ1/2 log1/2 n). the complexity of a local partitioning algorithm is measured by its work/volume ratio, which is the ratio between the computational complexity of the algorithm on a given run, and the volume of the set output. we prove that for our algorithm, the expected value of the work/volume ratio is polylognoparen(φ-1/2). the best previous local partitioning algorithm, due to andersen, chung, and lang, has the same approximation guarantee but a larger work/volume ratio of polylognoparen(φ-1). as an application of our local partitioning algorithm, we construct a fast algorithm for finding balanced cuts. the resulting algorithm takes as input a graph and a fixed value of φ, has complexity polylog{m+nφ-1/2), and returns a cut with conductance o(φ1/2 log1/2 n) and volume at least vφ/2, where vφ is the volume of the largest set in the graph with conductance at most φ.
random graphs and the parity quantifier. the classical zero-one law for first-order logic on random graphs says that for every first-order property φ in the theory of graphs and every p ∈ (0,1), the probability that the random graph g(n, p) satisfies φ approaches either 0 or 1 as n approaches infinity. it is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that g(n,p) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1. in this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, fop, over g(n,p), thus eluding the above hurdles. specifically, we establish the following "modular convergence law": for every fop sentence φ, there are two explicitly computable rational numbers a0, a1, such that for i ∈ {0,1}, as n approaches infinity, the probability that the random graph g(2n+i, p) satisfies φ approaches ai. our results also extend appropriately to fo equipped with modq quantifiers for prime q. in the process of deriving the above theorem, we explore a new question that may be of interest in its own right. specifically, we study the joint distribution of the subgraph statistics modulo 2 of g(n,p): namely, the number of copies, mod 2, of a fixed number of graphs f1, ..., fl of bounded size in g(n,p). we first show that every fop property φ is almost surely determined by subgraph statistics modulo 2 of the above type. next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on n mod 2, and we determine this limiting distribution completely. interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the gowers norm that we introduce. the first step above is analogous to the razborov-smolensky method for lower bounds for ac0 with parity gates, yet stronger in certain ways. for instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every fop sentence, which is something that is not known for ac.
affiliation networks. in the last decade, structural properties of several naturally arising networks (the internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. in recent empirical work, leskovec, kleinberg, and faloutsos identify two new and surprising properties of the evolution of many real-world networks: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). these properties run counter to conventional wisdom, and are certainly inconsistent with graph models prior to their work. in this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known properties of the social networks, as well as densification and shrinking diameter. our model is based on ideas studied empirically in the social sciences, primarily on the groundbreaking work of breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies. we also present algorithms that harness the structural consequences of our model. specifically, we show how to overcome the bottleneck of densification in computing shortest paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. this is a rare example of an algorithmic benefit derived from a realistic graph model. finally, our work also presents a modular approach to connecting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).
on the geometry of graphs with a forbidden minor. we study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the gupta-newman-rabinovich-sinclair (gnrs) l1 embedding conjecture to a pair of manifestly simpler conjectures. the gnrs conjecture characterizes all graphs that have an o(1)-approximate multi-commodity max-flow/min-cut theorem. in particular, its resolution would imply a constant factor approximation for the general sparsest cut problem in every family of graphs which forbids some minor. in the course of our study, we prove a number of results of independent interest.
on the convergence of regret minimization dynamics in concave games. we study a general sub-class of concave games which we call socially concave games. we show that if each player follows any no-external regret minimization procedure then the dynamics will converge in the sense that both the average action vector will converge to a nash equilibrium and that the utility of each player will converge to her utility in that nash equilibrium. we show that many natural games are indeed socially concave games. specifically, we show that linear cournot competition and linear resource allocation games are socially-concave games, and therefore our convergence result applies to them. in addition, we show that a simple best response dynamics might diverge for linear resource allocation games, and is known to diverge for linear cournot competition. for the tcp congestion games we show that "near" the equilibrium the games are socially-concave, and using our general methodology we show the convergence of a specific regret minimization dynamics.
the work of leslie valiant. on saturday, may 30, one day before the start of the regular stoc 2009 program, a workshop was held in celebration of leslie valiant's 60th birthday. talks were given by jin-yi cai, stephen cook, vitaly feldman, mark jerrum, michael kearns, mike paterson, michael rabin, rocco servedio, paul valiant, vijay vazirani, and avi wigderson. the workshop was organized by michael kearns, rocco servedio, and salil vadhan, with support from the stoc local arrangements team and program committee. to accompany the workshop, here we briefly survey valiant's many fundamental contributions to the theory of computing.