waashk/dblp huggingface dataset:
computing how we became human. with our ability to sequence entire genomes, we have for the first time the opportunity to compare the genomes of present day species, and deduce the trajectories by which they diversified from a common ancestral genome. for example, starting with a small shrew-like ancestor in the cretaceous period about 100 million years ago, the different species of placental mammals radiated outward, creating a stunning diversity of forms from whales to armadillos to humans. from the genomes of present-day species, it is possible to computationally reconstruct what most of the dna bases in the genome of the common ancestor of placental mammals must have looked like, and deduce most of the changes that lead to humans. in so doing, we discover how darwinian evolution has shaped us at the molecular level. because most random mutations to functionally important regions of dna reduce fitness, these changes usually disappear over time, in a process known as negative selection. from its unusually high conservation between species, it is immediately evident that at least 5% of the human genome has been under negative selection during most of mammalian evolution, and is hence likely to be functionally important. protein-coding genes and structural rna genes stand out among the negatively selected regions because of their distinctive pattern of restricted dna base substitutions, insertions and deletions. however, most of the dna under negative selection in mammalian genomes, and indeed in vertebrate genomes in general, does not appear to be part of protein-coding or structural rna genes, and shares no sequence similarity with any dna in the genomes of invertebrates. experimental evidence suggests that many of these unclassified vertebrate-conserved dna elements serve to regulate genes involved in embryonic development. a significant amount of this material appears to have been put into place by the movement of transposons, mobile dna elements that are derived from ancient viruses, the remnants of which constitute at least half of our genome. this provides new evidence for older theories of mcclintock and later britten and davidson that mobile dna elements played a significant role in the evolution of plant and animal gene regulatory networks. overlaid on the background of negative selection, we occasionally see a short segment of dna that has changed rapidly in a particular lineage, suggesting possible positive selection for a modified function in that lineage. the most dramatic example of this in the last 5 million years of human evolution occurs in a previously unstudied rna gene expressed in the developing cerebral cortex, known as human accelerated region 1 (har1). this gene is turned on only in a select set of neurons, during the time in fetal development when these neurons orchestrate the formation of the substantially larger cortex of the human brain. it will be many years before the biology of such examples is fully understood, but right now we relish the opportunity to get a first peek at the molecular tinkering that transmuted our animal ancestors into humans.
graphs, polymorphisms and the complexity of homomorphism problems. we use a connection between polymorphisms and the structure of smooth digraphs to prove the conjecture of bang-jensen and hell from 1990 and, as a consequence, a conjecture of bang-jensen, hell and macgillivray from 1995. the conjectured characterization of computationally complex coloring problems for smooth digraphs is proved using tools of universal algebra. we cite further graph results obtained using this new approach. the proofs are based in an universal algebraic framework developed for the constraint satisfaction problem and the csp dichotomy conjecture of feder and vardi in particular.
span-program-based quantum algorithm for evaluating formulas. we give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., nand, 3-majority). the algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. the main new tool is a correspondence between a classical linear-algebraic model of computation, "span programs," and weighted bipartite graphs. a span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. a quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. for example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. in contrast, our algorithm generalizes the optimal quantum and-or formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.
optimal query complexity bounds for finding graphs. we consider the problem of finding an unknown graph by using two types of queries with an additive property. given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. the queries ask sum of weights for the weighted graphs. these types of queries were partially motivated in dna shotgun sequencing and linkage discovery problem of artificial intelligence. for a given unknown weighted graph g with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of g using o(m log n / log m) queries of both types provided that m ≥ nε for any constant ε > 0. for an unweighted graph, it is shown that the same bound holds for all range of m. this settles a conjecture of grebinski [23] for finding an unweighted graph using additive queries. we also consider the problem of finding the fourier coefficients of a certain class of pseudo-boolean functions. a similar coin weighing problem is also considered.
some topics in analysis of boolean functions. this article accompanies a tutorial talk given at the 40th acm stoc conference. in it, we give a brief introduction to fourier analysis of boolean functions and then discuss some applications: arrow's theorem and other ideas from the theory of social choice; the bonami-beckner inequality as an extension of chernoff/hoeffding bounds to higher-degree polynomials; and, hardness for approximation algorithms.
list-decoding reed-muller codes over small fields. we present the first local list-decoding algorithm for the rth order reed-muller code rm(2,m) over f for r ≥ 2. given an oracle for a received word r: fm --r - ε) from r for any ε r,ε-r). the list size could be exponential in m at radius 2-r, so our bound is optimal in the local setting. since rm(2,m) has relative distance 2-r, our algorithm beats the johnson bound for r ≥ 2. in the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. we give a deterministic list-decoder that works at error rate below j(21-r), where j(δ) denotes the johnson radius for minimum distance δ. this shows that rm(2,m) codes are list-decodable up to radius η for any constant η q, we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. we conjecture that the list-decoding radius approaches the minimum distance (like over f), and prove this holds true when the degree is divisible by q-1.
combinatorial construction of locally testable codes. an error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. locally testable codes (ltcs) were first systematically studied by goldreich and sudan (j. acm 53(4)) and since then several constructions of ltcs have been suggested. while the best known construction of ltcs by ben-sasson and sudan (stoc 2005) and dinur (j. acm 54(3)) achieves very efficient parameters, it relies heavily on algebraic tools and on pcp machinery. in this work we present a new and arguably simpler construction of ltcs that is purely combinatorial, does not rely on pcp machinery and matches the parameters of the best known construction. however, unlike the latter construction, our construction is not entirely explicit.
algorithms for subset selection in linear regression. we study the problem of selecting a subset of k random variables to observe that will yield the best linear prediction of another variable of interest, given the pairwise correlations between the observation variables and the predictor variable. under approximation preserving reductions, this problem is equivalent to the "sparse approximation" problem of approximating signals concisely. the subset selection problem is np-hard in general; in this paper, we propose and analyze exact and approximation algorithms for several special cases of practical interest. specifically, we give an fptas when the covariance matrix has constant bandwidth, and exact algorithms when the associated covariance graph, consisting of edges for pairs of variables with non-zero correlation, forms a tree or has a large (known) independent set. furthermore, we give an exact algorithm when the variables can be embedded into a line such that the covariance decreases exponentially in the distance, and a constant-factor approximation when the variables have no "conditional suppressor variables". much of our reasoning is based on perturbation results for the r2 multiple correlation measure, which is frequently used as a natural measure for "goodness-of-fit statistics". it lies at the core of our fptas, and also allows us to extend our exact algorithms to approximation algorithms when the matrix "nearly" falls into one of the above classes. we also use our perturbation analysis to prove approximation guarantees for the widely used "forward regression" heuristic under the assumption that the observation variables are nearly independent.
elusive functions and lower bounds for arithmetic circuits. a basic fact in linear algebra is that the image of the curve f(x)=(x1,x2,x3,...,xm), say over c, is not contained in any m-1 dimensional affine subspace of cm. in other words, the image of f is not contained in the image of any polynomial-mapping γ:cm-1 → cm of degree~1 (that is, an affine mapping). can one give an explicit example for a polynomial curve f:c → cm, such that, the image of f is not contained in the image of any polynomial-mapping γ:cm-1 → cm of degree 2? in this paper, we show that problems of this type are closely related to proving lower bounds for the size of general arithmetic circuits. for example, any explicit f as above (with the right notion of explicitness implies super-polynomial lower bounds for computing the permanent over~c. more generally, we say that a polynomial-mapping f:fn → fm is (s,r)-elusive, if for every polynomial-mapping γ:fs → fm of degree r, im(f) ⊄ im(γ). we show that for many settings of the parameters n,m,s,r, explicit constructions of elusive polynomial-mappings imply strong (up to exponential) lower bounds for general arithmetic circuits. finally, for every r n → fn2, of degree o(r), that is (s,r)-elusive for s = n1+ω(1/r). we use this to construct for any r, an explicit example for an n-variate polynomial of total-degree o(r), with coefficients in {0,1,}such that, any depth r arithmetic circuit for this polynomial (over any field) is of size ≥ n1+ω(1/r). in particular, for any constant r, this gives a constant degree polynomial, such that, any depth r arithmetic circuit for this polynomial is of size ≥ n1+ω(1). previously, only lower bounds of the type ω(n • λr (n)), where λr (n) are extremely slowly growing functions (e.g., λ5(n) = log n, and λ7(n) = log* log*n), were known for constant-depth arithmetic circuits for polynomials of constant degree.
testing symmetric properties of distributions. we introduce the notion of a canonical tester for a class of properties on distributions, that is, a tester strong and general enough that "a distribution property in the class is testable if and only if the canonical tester tests it". we construct a canonical tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. analyzing the performance of the canonical tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy α/β- o(1) samples, and distinguishing whether a pair of distributions has statistical distance 1-o(1) samples. our techniques also resolve a conjecture about a property that our canonical tester does not apply to: distinguishing identical distributions from those with statistical distance >β requires ω(n2/3) samples.
additive approximation for bounded degree survivable network design. we study a general network design problem with additional degree constraints. given connectivity requirements ruv for all pairs of vertices, a steiner network is a graph in which there are at least ruv edge-disjoint paths between u and v for all pairs of vertices u,v. in the minimum bounded-degree steiner network problem, we are given an undirected graph g with an edge cost for each edge, a connectivity requirement ruv for each pair of vertices u and v, and a degree upper bound for each vertex v. the task is to find a minimum cost steiner network which satisfies all the degree upper bounds. the aim of this paper is to design approximation algorithms that minimize the total cost and the degree violation simultaneously. our main results are the following: there is a polynomial time algorithm which returns a steiner forest of cost at most 2 opt and the degree violation at each vertex is at most 3 ,where opt is the cost of an optimal solution which satisfies all the degree bounds. there is a polynomial time algorithm which returns a steiner network of cost at most 2 opt and the degree violation at each vertex is at most 6r max +3 ,where opt is the cost of an optimal solution which satisfies all the degree bounds, and r max := max u,v {r uv}. these results achieve the best known guarantees for both the total cost and the degree violation simultaneously. as corollaries, these results provide the first additive approximation algorithms for finding low degree subgraphs including steiner forests, k -edge-connected subgraphs, and steiner networks. the algorithms develop on the iterative relaxation method applied to a natural linear programming relaxation as in [10, 16, 22]. the new algorithms avoid paying a multiplicative factor of two on the degree bounds even though the algorithm can only pick edges with fractional value 1/2 . this is based on a stronger characterization of the basic so-algorithm is nearly tight.
regret minimization and the price of total anarchy. we propose weakening the assumption made when studying the price of anarchy: rather than assume that self-interested players will play according to a nash equilibrium (which may even be computationally hard to find), we assume only that selfish players play so as to minimize their own regret. regret minimization can be done via simple, efficient algorithms even in many settings where the number of action choices for each player is exponential in the natural parameters of the problem. we prove that despite our weakened assumptions, in several broad classes of games, this "price of total anarchy" matches the nash price of anarchy, even though play may never converge to nash equilibrium. in contrast to the price of anarchy and the recently introduced price of sinking, which require all players to behave in a prescribed manner, we show that the price of total anarchy is in many cases resilient to the presence of byzantine players, about whom we make no assumptions. finally, because the price of total anarchy is an upper bound on the price of anarchy even in mixed strategies, for some games our results yield as corollaries previously unknown bounds on the price of anarchy in mixed strategies.
on hardness of learning intersection of two halfspaces. we show that unless np = rp, it is hard to (even) weakly pac-learn intersection of two halfspaces in rn using a hypothesis which is a function of up to l linear threshold functions for any integer l. specifically, we show that for every integer l and an arbitrarily small constant ε > 0, unless np = rp, no polynomial time algorithm can distinguish whether there is an intersection of two halfspaces that correctly classifies a given set of labeled points in rn, or whether any function of l linear threshold functions can correctly classify at most 1/2+ε fraction of the points.
direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. a basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. we investigate this question in various models of classical communication complexity. we introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. we nonetheless show that for the communication complexity of boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. we prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. more importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. these results subsume and strengthen, in a unified manner, several recent results on the direct product question. the simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.
games for exchanging information. we consider the rational versions of two of the classical problems in foundations of cryptography: secret sharing and multiparty computation, suggested by halpern and teague (stoc 2004). our goal is to design games and fair strategies that encourage rational participants to exchange information about their inputs for their mutual benefit, when the only mean of communication is a broadcast channel. we show that protocols for the above information exchanging tasks, where players' values come from a bounded domain, cannot satisfy some of the most desirable properties. in contrast, we provide a rational secret sharing scheme with simultaneous broadcast channel in which shares are taken from an unbounded domain, but have finite (and polynomial sized) expectation. previous schemes (mostly cryptographic) have required computational assumptions, making them inexact and susceptible to backward induction, or used stronger communication channels. our scheme is non-cryptographic, immune to backward induction, and satisfies a stronger rationality concept (strict nash equilibrium). we show that our solution can also be used to construct an ε-nash equilibrium secret sharing scheme for the case of a non-simultaneous broadcast channel.
an o(log k)-approximation algorithm for the k-vertex connected spanning subgraph problem. we present an o(log n• log k)-approximation algorithm for the problem of finding k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in the input graph, and k is the connectivity requirement. our algorithm works for both directed and undirected graphs. the best known approximation guarantees for these problems are o(ln k• min{√k,n/n-k ln k}) by kortsarz and nutov, and o(ln{k}) in the case of undirected graphs where n≥ 6k2 by cheriyan, vempala, and vetta. our algorithm is the first that has a polylogarithmic guarantee for all values of k. combining our algorithm with the algorithm of kortsarz and nutov in case of small k, e.g., k2 k)-approximation algorithm. as in previous work, we use the frank-tardos algorithm for finding k-outconnected subgraphs as a subroutine. however, with a structural lemmas that we proved, we are able to show that we need only partial solutions returned by the frank-tardos algorithm; thus, we can avoid paying the whole cost of the optimal solution every time the algorithm is applied.
randomized competitive algorithms for generalized caching. we consider online algorithms for the generalized caching problem. here we are given a cache of size k and pages with arbitrary sizes and fetching costs. given a request sequence of pages, the goal is to minimize the total cost of fetching the pages into the cache. we give an online algorithm with competitive ratio o(log2k), which is the first algorithm for the problem with competitive ratio sublinear in k. we also give improved o(log k)-competitive algorithms for the special cases of the bit model and fault model. in the bit model, the fetching cost is proportional to the size of the page and in the fault model all fetching costs are uniform. previously, an o(log2 k)-competitive algorithm due to irani [14] was known for both of these models. our algorithms are based on an extension of the primal-dual framework for online algorithms which was developed by buchbinder and naor [7]. we first generate an o(log k)-competitive fractional algorithm for the problem. this is done by using a strengthened lp formulation with knapsack-cover constraints, where exponentially many constraints are added upon arrival of a new request. second, we round online the fractional solution and obtain a randomized online algorithm. our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.
improved approximation for directed cut problems. we present improved approximation algorithms for directed multicutand directed sparsest cut. the current best known approximationratio for these problems is o(n1/2). we obtain an õ(n11/23)-approximation. our algorithm works with thenatural lp relaxation used in prior work. we use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. this also implies a õ(n11/23) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.
on agnostic boosting and parity learning. the motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy nearly matches the accuracy of the best parity function. our algorithm runs in time 2o(n/log n), which matches the best known for the easier cases of learning parities with random classification noise (blum et al, 2003) and for agnostically learning parities over the uniform distribution on inputs (feldman et al, 2006). our approach is as follows. we give an agnostic boosting theorem that is capable of nearly achieving optimal accuracy, improving upon earlier studies (starting with ben david et al, 2001). to achieve this, we circumvent previous lower bounds by altering the boosting model. we then show that the (random noise) parity learning algorithm of blum et al (2000) fits our new model of agnostic weak learner. our agnostic boosting framework is completely general and may be applied to other agnostic learning problems. hence, it also sheds light on the actual difficulty of agnostic learning by showing that full agnostic boosting is indeed possible.