waashk/dblp huggingface dataset:
first to market is not everything: an analysis of preferential attachment with fitness. the design of algorithms on complex networks, such as routing, ranking or recommendation algorithms, requires a detailed understanding of the growth characteristics of the networks of interest, such as the internet,the web graph, social networks or online communities. to this end, preferential attachment, in which the popularity (or relevance) of a node is determined by its degree, is a well-known and appealing random graph model, whose predictions are in accordance with experiments on the web graph and several social networks. however, its central assumption, that the popularity of the nodes dependsonly on their degree, is not a realistic one, since every node has potentially some intrinsic quality which can differentiate its attractiveness from other nodes with similar degrees. in this paper, we provide a rigorous analysis of preferential attachment with fitness, suggested by bianconi and barabási and studied by motwani and xu, in which the degree of a vertex is scaled by its quality to determine its attractiveness. including quality considerations in the classical preferential attachment model provides a much more realistic description of many complex networks, such as the web graph, and allows toobserve a much richer behavior in the growth dynamics of these networks. specifically, depending on the shape of the distributionfrom which the qualities of the vertices are drawn, we observe three distinct phases, namely a first-mover-advantage phase, afit-get-richer phase and an innovation-pays-offphase. we precisely characterize the properties of the quality distribution that result in each of these phases and we computethe exact growth dynamics for each phase. the dynamics provide rich information about the quality of the vertices, which can bevery useful in many practical contexts, including ranking algorithms for the web, recommendation algorithms, as well as thestudy of social networks.
network design for vertex connectivity. we study the survivable network design problem (sndp) for vertex connectivity. given a graph g(v,e) with costs on edges, the goal of sndp is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. when all connectivity requirements are between a special vertex, called the source, and vertices in a subset t ⊆ v, called terminals, the problem is called the single-source sndp. our main result is a randomized ko(k2) log4n-approximation algorithm for single-source sndp where k denotes the largest connectivity requirement for any source-terminal pair. in particular, we get a poly-logarithmic approximation for any constant k. prior to our work, no non-trivial approximation guarantees were known for this problem for any k ≥ 3. we also show that sndp is kω(1)-hard to approximate and provide an elementary construction that shows that the well-studied set-pair linear programming relaxation for this problem has an ω(k1/3) integrality gap.
a discriminative framework for clustering via similarity functions. problems of clustering data from pairwise similarity information are ubiquitous in computer science. theoretical treatments typically view the similarity information as ground-truth and then design algorithms to (approximately) optimize various graph-based objective functions. however, in most applications, this similarity information is merely based on some heuristic; the ground truth is really the unknown correct clustering of the data points and the real goal is to achieve low error on the data. in this work, we develop a theoretical approach to clustering from this perspective. in particular, motivated by recent work in learning theory that asks "what natural properties of a similarity (or kernel) function are sufficient to be able to learn well?" we ask "what natural properties of a similarity function are sufficient to be able to cluster well?" to study this question we develop a theoretical framework that can be viewed as an analog of the pac learning model for clustering, where the object of study, rather than being a concept class, is a class of (concept, similarity function) pairs, or equivalently, a property the similarity function should satisfy with respect to the ground truth clustering. we then analyze both algorithmic and information theoretic issues in our model. while quite strong properties are needed if the goal is to produce a single approximately-correct clustering, we find that a number of reasonable properties are sufficient under two natural relaxations: (a) list clustering: analogous to the notion of list-decoding, the algorithm can produce a small list of clusterings (which a user can select from) and (b) hierarchical clustering: the algorithm's goal is to produce a hierarchy such that desired clustering is some pruning of this tree (which a user could navigate). we develop a notion of the clustering complexity of a given property (analogous to notions of capacity in learning theory), that characterizes its information-theoretic usefulness for clustering. we analyze this quantity for several natural game-theoretic and learning-theoretic properties, as well as design new efficient algorithms that are able to take advantage of them. our algorithms for hierarchical clustering combine recent learning-theoretic approaches with linkage-style methods. we also show how our algorithms can be extended to the inductive case, i.e., by using just a constant-sized sample, as in property testing. the analysis here uses regularity-type results of [fk] and [afkk].
evolvability from learning algorithms. valiant has recently introduced a framework for analyzing the capabilities and the limitations of the evolutionary process of random change guided by selection. in his framework the process of acquiring a complex functionality is viewed as a substantially restricted form of pac learning of an unknown function from a certain set of functions. valiant showed that classes of functions evolvable in his model are also learnable in the statistical query (sq) model of kearns and asked whether the converse is true. we show that evolvability is equivalent to learnability by a restricted form of statistical queries. based on this equivalence we prove that for any fixed distribution d over the instance space, every class of functions learnable by sqs over d is evolvable over d. previously, only the evolvability of monotone conjunctions of boolean variables over the uniform distribution was known. on the other hand, we prove that the answer to valiant's question is negative when distribution-independent evolvability is considered. to demonstrate this, we develop a technique for proving lower bounds on evolvability and use it to show that decision lists and linear threshold functions are not evolvable in a distribution-independent way. this is in contrast to distribution-independent learnability of decision lists and linear threshold functions in the statistical query model.
optimal algorithms and inapproximability results for every csp? semidefinite programming(sdp) is one of the strongest algorithmic techniques used in the design of approximation algorithms. in recent years, unique games conjecture(ugc) has proved to be intimately connected to the limitations of semidefinite programming. making this connection precise, we show the following result : if ugc is true, then for every constraint satisfaction problem(csp) the best approximation ratio is given by a certain simple sdp. specifically, we show a generic conversion from sdp integrality gaps to ugc hardness results for every csp. this result holds both for maximization and minimization problems over arbitrary finite domains. using this connection between integrality gaps and hardness results we obtain a generic polynomial-time algorithm for all csps. assuming the unique games conjecture, this algorithm achieves the optimal approximation ratio for every csp. unconditionally, for all 2-csps the algorithm achieves an approximation ratio equal to the integrality gap of a natural sdp used in literature. further the algorithm achieves at least as good an approximation ratio as the best known algorithms for several problems like maxcut, max2sat, maxdicut and unique games.
parallel repetition in projection games and a concentration bound. in a two player game, a referee asks two cooperating players (who are not allowed to communicate) questions sampled from some distribution and decides whether they win or not based on some predicate of the questions and their answers. the parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends corresponding questions to the players simultaneously. the players may now answer each question in a way that depends on the other questions they are asked. if the players cannot win the original game with probability better than (1-ε), what's the best they can do in the repeated game? we improve earlier results of raz and holenstein, which showed that the players cannot win all copies in the repeated game with probability better than (1-ε3)ω(n/c) (here c is the length of the answers in the game), in the following ways: we prove the bound (1-ε2)ω(n) as long as the game is a "projection game", the type of game most commonly used in hardness of approximation results. our bound is independent of the answer length and has a better dependence on ε. by the recent work of raz, this bound is essentially tight. a consequence of this bound is to the unique games conjecture of khot. many tight or almost tight hardness of approximation results have been proved using the unique games conjecture, so it would be very interesting to prove this conjecture. we make progress towards this goal by showing that it suffices to prove the following easier statement: {unique games conjecture} for every δ,ε> 0, there exists an alphabet size m(ε) such that it is np-hard to distinguish a unique game with alphabet size m for which a 1-ε2 fraction of the constraints can be satisfied from one in which a 1-ε1-δ fraction of the constraints can be satisfied. we also prove a concentration bound for parallel repetition (of general games) showing that for any constant 04 n/c)). an application of this is in testing bell inequalities. our result implies that the parallel repetition of the chsh game can be used to get an experiment that has a very large classical versus quantum gap.
an optimal sdp algorithm for max-cut, and equally optimal long code tests. let g be an undirected graph for which the standard max-cut sdp relaxation achieves at least a c fraction of the total edge weight, 1/2 2' algorithm. thus we have given an efficient, optimal sdp-rounding algorithm for max-cut. the fact that it is rpr2 confirms a conjecture of feige and langberg [17]. we also describe and analyze the tight connection between sdp gaps and long code tests (and the constructions of [25, 3, 4]). using this connection, we give optimal long code tests for max-cut. combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - the max-cut sdp gap curve subject to triangle inequalities is also given by s(c). - no rpr2 algorithm can be guaranteed to find cuts of value larger than s(c) in graphs where the optimal cut is c. (contrast this with the fact that in the graphs exhibiting the c vs. s(c) sdp gap, our rpr2 algorithm actually finds the optimal cut.) - further, no polynomial-time algorithm of any kind can have such a guarantee, assuming p ≠ np and the unique games conjecture.
every minor-closed property of sparse graphs is testable. testing a property p of graphs in the bounded degree model deals with the following problem: given a graph g of bounded degree d we should distinguish (with probability 0.9, say) between the case that g satisfies p and the case that one should add/remove at least ε d n edges of g to make it satisfy p. in sharp contrast to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. in this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a constant number of queries. as a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. none of these properties was previously known to be testable even with o(n) queries. the proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.
uniform direct product theorems: simplified, optimized, and derandomized. the classical direct-product theorem for circuits says that if a boolean function f: {0,1}n -> {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function fk(x1,...,xk)=(f(x1),...,f(xk)) (where each xi -> {0,1}n) is significantly harder to compute on average by slightly smaller circuits. we prove a fully uniform version of the direct-product theorem with information-theoretically optimal parameters, up to constant factors. namely, we show that for given k and ε, there is an efficient randomized algorithm a with the following property. given a circuit c that computes fk on at least ε fraction of inputs, the algorithm a outputs with probability at least 3/4 a list of o(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1-δ fraction of inputs, for δ = o((log 1/ε)/k). moreover, each output circuit is an ac0 circuit (of size poly(n,k,log 1/δ,1/ε)), with oracle access to the circuit c. using the goldreich-levin decoding algorithm [5], we also get a fully uniform version of yao's xor lemma [18] with optimal parameters, up to constant factors. our results simplify and improve those in [10]. our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. we generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. the quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. as a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.
inapproximability of pure nash equilibria. the complexity of computing pure nash equilibria in congestion games was recently shown to be pls-complete. in this paper, we therefore study the complexity of computing approximate equilibria in congestion games. an alpha-approximate equilibrium, for α > 1, is a state of the game in which none of the players can make an α-greedy step, i.e., an unilateral strategy change that decreases the player's cost by a factor of at least α. our main result shows that finding an α-approximate equilibrium of a given congestion game is sc pls-complete, for any polynomial-time computable α > 1. our analysis is based on a gap introducing pls-reduction from flip, i.e., the problem of finding a local optimum of a function encoded by an arbitrary circuit. as this reduction is tight it additionally implies that computing an α-approximate equilibrium reachable from a given initial state by a sequence of α-greedy steps is pspace-complete. our results are in sharp contrast to a recent result showing that every local search problem in pls admits a fully polynomial time approximation scheme. in addition, we show that there exist congestion games with states such that any sequence of α-greedy steps leading from one of these states to an α-approximate nash equilibrium has exponential length, even if the delay functions satisfy a bounded-jump condition. this result shows that a recent result about polynomial time convergence for α-greedy steps in congestion games satisfying the bounded-jump condition is restricted to symmetric games only.
optimal mechanism design and money burning. mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. there is, however, a fundamental disconnect between the traditional application domains of mechanism design (such as auctions) and those arising in computer science (such as networks): while monetary "transfers" (i.e., payments) are essential for most of the known positive results in mechanism design, they are undesirable or even technologically infeasible in many computer systems. classical impossibility results imply that the reach of mechanisms without transfers is severely limited. computer systems typically do have the ability to reduce service quality--routing systems can drop or delay traffic, scheduling protocols can delay the release of jobs, and computational payment schemes can require computational payments from users (e.g., in spam-fighting systems). service degradation is tantamount to requiring that users "burn money", and such "payments" can be used to influence the preferences of the agents at a cost of degrading the social surplus. we develop a framework for the design and analysis of "money-burning mechanisms" to maximize the residual surplus-the total value of the chosen outcome minus the payments required. our primary contributions are the following. * we define a general template for prior-free optimal mechanism design that explicitly connects bayesian optimal mechanism design, the dominant paradigm in economics, with worst-case analysis. in particular, we establish a general and principled way to identify appropriate performance benchmarks in prior-free mechanism design. * for general single-parameter agent settings, we characterize the bayesian optimal money-burning mechanism. * for multi-unit auctions, we design a near-optimal prior-free money-burning mechanism: for every valuation profile, its expected residual surplus is within a constant factor of our benchmark, the residual surplus of the best bayesian optimal mechanism for this profile. * for multi-unit auctions, we quantify the benefit of general transfers over money-burning: optimal money-burning mechanisms always obtain a logarithmic fraction of the full social surplus, and this bound is tight.
cryptography with constant computational overhead. current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. we explore the possibility of implementing basic cryptographic primitives, such as encryption, authentication, signatures, and secure two-party computation, while incurring only a constant computational overhead compared to insecure implementations of the same tasks. here we make the usual security requirement that the advantage of any polynomial-time attacker must be negligible in the input length. we obtain affirmative answers to this question for most central cryptographic primitives under plausible, albeit sometimes nonstandard, intractability assumptions. we start by showing that pairwise-independent hash functions can be computed by linear-size circuits, disproving a conjecture of mansour, nisan, and tiwari (stoc 1990). this construction does not rely on any unproven assumptions and is of independent interest. our hash functions can be used to construct message authentication schemes with constant overhead from any one-way function. under an intractability assumption that generalizes a previous assumption of alekhnovich (focs 2003), we get (public and private key) encryption schemes with constant overhead. using an exponentially strong version of the previous assumption, we get signature schemes of similar complexity. assuming the existence of pseudorandom generators in nc z with polynomial stretch together with the existence of an (arbitrary) oblivious transfer protocol, we get similar results for the seemingly very complex task of secure two-party computation. more concretely, we get general protocols for secure two-party computation in the semi-honest model in which the two parties can be implemented by circuits whose size is a constant multiple of the size s of the circuit to be evaluated. in the malicious model, we get protocols whose communication complexity is a constant multiple of s and whose computational complexity is slightly super-linear in s. for natural relaxations of security in the malicious model that are still meaningful in practice, we can also keep the computational complexity linear in s. these results extend to the case of a constant number of parties, where an arbitrary subset of the parties can be corrupted. our protocols rely on non-black-box techniques, and suggest the intriguing possibility that the ultimate efficiency in this area of cryptography can be obtained via such techniques.
on partitioning graphs via single commodity flows. in this paper we obtain improved upper and lower bounds for the best approximation factor for sparsest cut achievable in the cut-matching game framework proposed in khandekar et al. [9]. we show that this simple framework can be used to design combinatorial algorithms that achieve o(log n) approximation factor and whose running time is dominated by a poly-logarithmic number of single-commodity max-flow computations. this matches the performance of the algorithm of arora and kale [2]. moreover, we also show that it is impossible to get an approximation factor of better than ω(√log n) in the cut-matching game framework. these results suggest that the simple and concrete abstraction of the cut-matching game may be powerful enough to capture the essential features of the complexity of sparsest cut.
the pattern matrix method for lower bounds on quantum communication. in a breakthrough result, razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=d(|x and y|) for some d:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. this was proved by the multidimensional discrepancy method. we give an entirely different proof of razborov's result, using the original, one-dimensional discrepancy method. this refutes the commonly held intuition (razborov 2003) that the original discrepancy method fails for functions such as disjointness. more importantly, our communication lower bounds hold for a much broader class of functions for which no methods were available. namely, fix an arbitrary function f:{0,1}n/4->{0,1} and let a be the boolean matrix whose columns are each an application of f to some subset of the variables x1,x2,...,xn. we prove that the communication complexity of a in the bounded-error quantum model with and without prior entanglement is omega(d), where d is the approximate degree of f. from this result, razborov's lower bounds follow easily. our result also establishes a large new class of total boolean functions whose quantum communication complexity (regardless of prior entanglement) is at best polynomially smaller than their classical complexity. our proof method is a novel combination of two ingredients. the first is a certain equivalence of approximation and orthogonality in euclidean n-space, which follows by linear-programming duality. the second is a new construction of suitably structured matrices with low spectral norm, the pattern matrices, which we realize using matrix analysis and the fourier transform over (z2)n. the method of this paper has recently inspired important progress in multiparty communication complexity.