We present CHASE-SQL, a novel framework addressing large language model (LLM) performance challenges for Text-to-SQL tasks by leveraging multi-agent modeling and test-time compute for improved candidate generation and selection. CHASE-SQL uses LLMs to generate diverse SQL candidates with: (1) a divide-and-conquer approach to break down complex queries, (2) chain-of-thought reasoning based on query execution plans, and (3) instance-aware synthetic example generation for tailored few-shot demonstrations. A selection agent ranks candidates via pairwise comparisons using a fine-tuned binary selection LLM, offering robust performance. This framework improves SQL query quality and diversity, achieving state-of-the-art execution accuracy of 73.0% on the BIRD Text-to-SQL benchmark test set, topping the leaderboard at the time of submission.

In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon Gale-Shapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log² n). In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log³ n) interviews to each applicant or position.

We offer a novel theoretical perspective on employing sub graph sampling methods for the training of graph neural networks (GNNs). We prove that, under mild assumptions, parameters learned from training GNNs on small samples of a large input graph are within an ∊-neighborhood of the outcome of training the same architecture on the entire graph. We derive bounds on the number of samples, the size of the sub graph, and the training steps required as a function of ∊. Our results offer a theoretical justification for the empirical success of GNNs trained on small subgraph samples of the graphs of interest, a paradigm theoretically formalized as transferability [1] and which forms the backbone of efficient GNNs architectures. We validate our theoretical results empirically on node classification tasks using moderately large citation graphs, demonstrating that GNNs trained on sub graphs 12 × smaller than the original graph achieve comparable performance.

Large reasoning models (LRMs) excel at complex reasoning tasks but typically generate lengthy sequential chains-of-thought, resulting in long inference times before arriving at the final answer. To address this challenge, we introduce SPRINT, a novel post-training and inference-time framework designed to enable LRMs to dynamically identify and exploit opportunities for parallelization during their reasoning process. SPRINT incorporates an innovative data curation pipeline that reorganizes natural language reasoning trajectories into structured rounds of long-horizon planning and parallel execution. By fine-tuning LRMs on a small amount of such curated data, the models learn to dynamically identify independent subtasks within extended reasoning processes and effectively execute them in parallel. Through extensive evaluations, we demonstrate that models fine-tuned with the SPRINT framework match the performance of reasoning models on complex domains such as mathematics while generating up to 39% fewer sequential tokens on problems requiring more than 8,000 output tokens. Finally, we observe consistent results transferred to two out-of-distribution tasks, namely GPQA and Countdown, with up to 45% and 65% reduction in average sequential tokens respectively for longer reasoning trajectories, while matching the performance of the fine-tuned reasoning model.

We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC’21). Here, nodes on one side of the graph are given upfront, while at each time t, an online node and its edge weights are drawn from a time-dependent distribution. The optimal algorithm is PSPACE-hard to approximate within some universal constant. We refer to this optimal algorithm, which requires time to think (compute), as a philosopher, and refer to polynomial-time online approximations of the above as philosopher inequalities. The best known philosopher inequality for online matching yields a 0.652-approximation. In contrast, the best possible prophet inequality, or approximation of the optimum offline solution, is 0.5.

Given a so called “Sperner coloring” of a triangulation of the$D$-dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by all$D+1$colors. However, finding a rainbow simplex was the first problem to be proven PPAD-complete in Papadimitriou's classical paper introducing the class PPAD [1]. In this paper, we prove that the problem does not become easier if we relax “all -${D}+1$colors” to allow some fraction of missing colors: in fact, for any constant$D$, finding even a simplex with just three colors remains PPAD-complete! Our result has an interesting application for the envy-free cake cutting from fair division. It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (“a non-empty piece is better than an empty piece of cake”), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is PPAD-complete to find an allocation -even using any constant number of possibly disconnected pieces- that makes just three agents envy-free. Our results extend to super-constant dimension, number of agents, and number of pieces, as long as they are asymptotically bounded by any$\log^{1-\Omega(1)}(\varepsilon)$, where$\varepsilon$is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).

We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related maximum path cover problem, which asks for a collection of vertex disjoint paths that include the maximum number of edges. We show that for any fixed ε > 0, there is an algorithm that (1/2 - ε)-approximates the maximum path cover size of an n-vertex graph in Õ(n) time. This improves upon a (3/8-ε)-approximate Õ(n √n)-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give an Õ(n) time algorithm that estimates the cost of (1,2)-TSP within a factor of (1.5+ε) which is an improvement over a folklore (1.75 + ε)-approximate Õ(n)-time algorithm, as well as a (1.625+ε)-approximate Õ(n√n)-time algorithm of [CHK ICALP'20]. For graphic TSP, we present an Õ(n) algorithm that estimates the cost of graphic TSP within a factor of 1.83 which is an improvement over a 1.92-approximate Õ(n) time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. We show that the approximation can be further improved to 1.66 using n^{2-Ω(1)} time. All of our Õ(n) time algorithms are information-theoretically time-optimal up to polylog n factors. Additionally, we show that our approximation guarantees for path cover and (1,2)-TSP hit a natural barrier: We show better approximations require better sublinear time algorithms for the well-studied maximum matching problem.

Graph Neural Networks (GNNs) are popular models for machine learning on graphs that typically follow the message-passing paradigm, whereby the feature of a node is updated recursively upon aggregating information over its neighbors. While exchanging messages over the input graph endows GNNs with a strong inductive bias, it can also make GNNs susceptible to over-squashing, thereby preventing them from capturing long-range interactions in the given graph. To rectify this issue, graph rewiring techniques have been proposed as a means of improving information flow by altering the graph connectivity. In this work, we identify three desiderata for graph-rewiring: (i) reduce over-squashing, (ii) respect the locality of the graph, and (iii) preserve the sparsity of the graph. We highlight fundamental trade-offs that occur between spatial and spectral rewiring techniques; while the former often satisfy (i) and (ii) but not (iii), the latter generally satisfy (i) and (iii) at the expense of (ii). We propose a novel rewiring framework that satisfies all of (i)--(iii) through a locality-aware sequence of rewiring operations. We then discuss a specific instance of such rewiring framework and validate its effectiveness on several real-world benchmarks, showing that it either matches or significantly outperforms existing rewiring approaches.

Online Bayesian bipartite matching is a central problem in digital marketplaces and exchanges, including advertising, crowdsourcing, ridesharing, and kidney exchange. We introduce a graph neural network (GNN) approach that emulates the problem's combinatorially-complex optimal online algorithm, which selects actions (e.g., which nodes to match) by computing each action's *value-to-go (VTG)*—the expected weight of the final matching if the algorithm takes that action, then acts optimally in the future. We train a GNN to estimate VTG and show empirically that this GNN returns high-weight matchings across a variety of tasks. Moreover, we identify a common family of graph distributions in spatial crowdsourcing applications, such as rideshare, under which VTG can be efficiently approximated by aggregating information within local neighborhoods in the graphs. This structure matches the local behavior of GNNs, providing theoretical justification for our approach.

We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users.

We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a (½ + Ω(1))-approximation algorithm which can be implemented in O(n1+ε) time, where n is the number of vertices and the constant ε > 0 can be made arbitrarily small. The best known lower bound for the problem is Ω(n), which holds for any constant approximation. Existing algorithms either obtain the greedy bound of ½-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in o(n2)-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less “adaptive” augmentation algorithm for maximum matching that might be of independent interest.

The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence $2$-approximate) matching in $O(n)$ worst-case update time in $n$-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of {\em both} approximation ratio and worst-case update time. Specifically, we give a $(2-Ω(1))$-approximate algorithm with $O(m^{3/8})=O(n^{3/4})$ worst-case update time in $n$-node, $m$-edge graphs. For sufficiently small constant $ε>0$, no deterministic $(2+ε)$-approximate algorithm with worst-case update time $O(n^{0.99})$ was known. Our second result is the first deterministic $(2+ε)$-approximate weighted matching algorithm with $O_ε(1)\cdot O(\sqrt[4]{m}) = O_ε(1)\cdot O(\sqrt{n})$ worst-case update time. Our main technical contributions are threefold: first, we characterize the tight cases for \emph{kernels}, which are the well-studied matching sparsifiers underlying much of the $(2+ε)$-approximate dynamic matching literature. This characterization, together with multiple ideas -- old and new -- underlies our result for breaking the approximation barrier of $2$. Our second technical contribution is the first example of a dynamic matching algorithm whose running time is improved due to improving the \emph{recourse} of other dynamic matching algorithms. Finally, we show how to use dynamic bipartite matching algorithms as black-box subroutines for dynamic matching in general graphs without incurring the natural $\frac{3}{2}$ factor in the approximation ratio which such approaches naturally incur.

We study dynamic matching in a spatial setting. Drivers are distributed at random on some interval. Riders arrive in some (possibly adversarial) order at randomly drawn points. The platform observes the location of the drivers and can match newly arrived riders immediately or can wait for more riders to arrive. Unmatched riders incur a waiting cost of c per period. Furthermore, the platform can match riders and drivers irrevocably, and the cost of matching a driver to a rider is equal to the distance between them.

We introduce and study a variation of the submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first k items in the list for a k chosen at random from a given distribution, and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engagement of the shopper defined as the probability of purchase. This problem gives rise to a less-studied variation of submodular maximization in which we are asked to choose an ordering of a set of elements to maximize a linear combination of different submodular functions.

Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting, in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories c_min is large, our main result is a near-optimal 1-min(1/2,√log(cmin)/cmin) competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies - one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce post-processing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. We finally evaluate the performance of our algorithms using the numerical simulations on synthetic data.

We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a 1/2-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than (1-1/e)-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a 1-1/e bound implied by recent work of Aouad and Sarita (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.

No abstract available.

We study a simple model of epidemics where an infected node transmits the infection to its neighbors independently with probability p. This is also known as the independent cascade or Susceptible-Infected-Recovered (SIR) model with fixed recovery time. The size of an outbreak in this model is closely related to that of the giant connected component in “edge percolation”, where each edge of the graph is kept independently with probability p, studied for a large class of networks including configuration model [30] and preferential attachment [15, 37]. Even though these models capture the effects of degree inhomogeneity and the role of super-spreaders in the spread of an epidemic, they only consider graphs that are locally tree like i.e. have a few or no short cycles. Some generalizations of the configuration model were suggested to capture local communities, known as household models [6], or hierarchical configuration model [48]. Here, we ask a different question: what information is needed for general networks to predict the size of an outbreak? Is it possible to make predictions by accessing the distribution of small subgraphs (or motifs)? We answer the question in the affirmative for large-set expanders with local weak limits (also known as Benjamini-Schramm limits). In particular, we show that there is an algorithm which gives a (1–∊) approximation of the probability and the final size of an outbreak by accessing a constant-size neighborhood of a constant number of nodes chosen uniformly at random. We also present corollaries of the theorem for the preferential attachment model, and study generalizations with household (or motif) structure. The latter was only known for the configuration model.

Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of 2 of the naïve greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree Δ = O(log n), which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general adversarial arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a (1.9+o(1))-competitive online edge coloring algorithm for general graphs of degree Δ = ω(log n) under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching x online under vertex arrivals, guaranteeing that each edge e is matched with probability (1/2+c)⋅ x_e, for a constant c > 0.027.

We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable; the exact number of arborescences can be computed by a determinant [Tut48], and sampling can be reduced to counting [JVV86, JS96]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [Csa75]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery.

We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the men-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, we show that despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes results of [Pittel 1989] which correspond to uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market, and we give the first explicit calculations of rank beyond uniform markets.

We consider a model for repeated stochastic matching where compatibility is probabilistic, is realized the first time agents are matched, and persists in the future. Such a model has applications in the gig economy, kidney exchange, and mentorship matching. We ask whether adecentralized matching process can approximate the optimal online algorithm. In particular, we consider a decentralizedstable matching process where agents match with the most compatible partner who does not prefer matching with someone else, and known compatible pairs continue matching in all future rounds. We demonstrate that the above process provides a 0.316-approximation to the optimal online algorithm for matching on general graphs. We also provide a 1/7-approximation for many-to-one bipartite matching, a 1/11-approximation for capacitated matching on general graphs, and a 1/2k-approximation for forming teams of up to k agents. Our results rely on a novel coupling argument that decomposes the successful edges of the optimal online algorithm in terms of their round-by-round comparison with stable matching.

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?

We study a two-stage stochastic matching problem motivated in part by applications in online marketplaces used for ride hailing. Using a randomized primal-dual algorithm applied to a family of “balancing” convex programs, we obtain the optimal 3/4 competitive ratio against the optimum offline benchmark. These balancing convex programs offer a natural generalization of the matching skeleton by Goel et al. (2012) and may be of independent interest. Switching to the more precise benchmark of optimum online, we exploit connections to submodular optimization and use a factor-revealing program to improve the 3/4 ratio to (1 – 1/e + 1/e2) ≈ 0.767 for the unweighted and 0.761 for the weighted case. We also show it is NP-hard to obtain an FPTAS with respect to this benchmark.

Waiting lists are common mechanisms for allocating scarce items without monetary transfers. Examples include the allocation of cadaver organs to patients in need of a transplant, public housing apartments to applicants, health care services to patients, and even spots at childcare centers to parents. In all these markets waiting times play the role of prices in guiding the allocation and rationing items. But while prices are set by the designer, waiting times are endogenously determined by the number of agents waiting. Moreover, waiting times are not fixed, and continuously adjust as items arrive or agents join. When agents and items arrive stochastically over time, waiting times stochastically adjust over time.

In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.

We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.

We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our analysis builds upon [BCMV14] but allows for a wider range of perturbation models, including discrete ones. We give an application to recovering assemblies of neurons. Assemblies are large sets of neurons representing specific memories or concepts. The size of the intersection of two assemblies has been shown in experiments to represent the extent to which these memories co-occur or these concepts are related; the phenomenon is called association of assemblies. This suggests that an animal's memory is a complex web of associations, and poses the problem of recovering this representation from cognitive data. Motivated by this problem, we study the following more general question: Can we reconstruct the Venn diagram of a family of sets, given the sizes of their l-wise intersections? We show that as long as the family of sets is randomly perturbed, it is enough for the number of measurements to be polynomially larger than the number of nonempty regions of the Venn diagram to fully reconstruct the diagram.

Identifying the optimal set of individuals to first receive information (`seeds') in a social network is a widely-studied question in many settings, such as the diffusion of information, microfinance programs, and new technologies. Numerous studies have proposed various network-centrality based heuristics to choose seeds in a way that is likely to boost diffusion. Here we show that, for some frequently studied diffusion processes, randomly seeding S + x individuals can prompt a larger cascade than optimally targeting the best S individuals, for a small x. We prove our results for large classes of random networks, but also show that they hold in simulations over several real-world networks. This suggests that the returns to collecting and analyzing network information to identify the optimal seeds may not be economically significant. Given these findings, practitioners interested in communicating a message to a large number of people may wish to compare the cost of network-based targeting to that of slightly expanding initial outreach.

We study the problem of approximating the largest root of a real-rooted polynomial of degree n using its top k coefficients and give nearly matching upper and lower bounds. We present algorithms with running time polynomial in k that use the top k coefficients to approximate the maximum root within a factor of n1/k and when k ≤ log n and k > log n respectively. We also prove corresponding information-theoretic lower bounds of nΩ(1/k) and , and show strong lower bounds for noisy version of the problem in which one is given access to approximate coefficients. This problem has applications in the context of the method of interlacing families of polynomials, which was used for proving the existence of Ramanujan graphs of all degrees, the solution of the Kadison-Singer problem, and bounding the integrality gap of the asymmetric traveling salesman problem. All of these involve computing the maximum root of certain real-rooted polynomials for which the top few coefficients are accessible in subexponential time. Our results yield an algorithm with the running time of for all of them.

There has been a marked shift towards learning and consuming information through video. Most academic research, however, is still distributed only in text form, as researchers often have limited time, resources, and incentives to create video versions of their work. To address this gap, we propose, deploy, and evaluate a scalable, end-to-end system for crowdsourcing the creation of short, 5-minute research videos based on academic papers. Doing so requires solving complex coordination and collaborative video production problems. To assist coordination, we designed a structured workflow that enables efficient delegation of tasks, while also motivating the crowd through a collaborative learning environment. To facilitate video production, we developed an online tool with which groups can make micro-audio recordings that are automatically stitched together to create a complete talk. We tested this approach with a group of volunteers recruited from 52 countries through an open call. This distributed crowd produced over 100 video talks in 12 languages based on papers from top-tier computer science conferences. The produced talks consistently received high ratings from a diverse group of non-experts and experts, including the authors of the original papers. These results indicate that our crowdsourcing approach is a promising method for producing high-quality research talks at scale, increasing the distribution and accessibility of scientific knowledge.

We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c =γ+1≃ 4:84. We write a natural convex relaxation and show that its optimum solution gives a cn approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices. We also show that our result implies an approximate version of the permanent-ontop conjecture, which was recently refuted in its original form; we show that the permanent is within a cn factor of the top eigenvalue of the Schur power matrix.

We study the problem of allocating m items to n agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective, breaking the 1/2e^(1/e) approximation factor of Cole and Gkatzelis. Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.

While most existing research knowledge is distributed in the form of papers, there has been a shift towards learning and consuming information through video. Limited time and resources, however, prevent individual researchers from making their work available in this format. Crowdsourcing this task is a promising alternative, but it requires solving complex coordination and collaborative video production problems. In this paper, we propose an end-to-end solution to crowdsource the creation of research videos. To assist coordination, we designed a structured workflow that enables efficient delegation of tasks, while also providing a collaborative learning environment to the crowd for motivation. To facilitate video production, we developed an online system through which groups can make micro audio recordings that are automatically stitched together to create a complete talk. We tested this approach with a group of volunteers recruited from 24 countries through an open call. This distributed crowd produced five video talks based on the best paper winners and nominees from WWW 2016. Evaluations from the authors of the papers and outside reviewers rated the talks "very good" (giving a median score of 4 out of 5). We further applied this method to translate these talks and produce 11 additional videos in Spanish, Romanian, and Catalan. These results suggest that our crowdsourcing approach has the potential to significantly increase learning and the accessibility of the scientific knowledge.

We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find a partition, where each agent is guaranteed her maximin share. Such allocations do not always exist, hence we resort to approximation algorithms. Our main result is a 2/3-approximation that runs in polynomial time for any number of agents and goods. This improves upon the algorithm of Procaccia and Wang (2014), which is also a 2/3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of the algorithm in Procaccia and Wang (2014), exploiting the construction of carefully selected matchings in a bipartite graph representation of the problem. Furthermore, motivated by the apparent difficulty in establishing lower bounds, we undertake a probabilistic analysis. We prove that in randomly generated instances, maximin share allocations exist with high probability. This can be seen as a justification of previously reported experimental evidence. Finally, we provide further positive results for two special cases arising from previous works. The first is the intriguing case of three agents, where we provide an improved 7/8-approximation. The second case is when all item values belong to {0, 1, 2}, where we obtain an exact algorithm.

Motivated by the importance of energy storage networks in smart grids, we provide an algorithmic study of the online energy storage management problem in a network setting, the first to the best of our knowledge. Given online power supplies, either entirely renewable supplies or those in combination with traditional supplies, we want to route power from the supplies to demands using storage units subject to a decay factor. Our goal is to maximize the total utility of satisfied demands less the total production cost of routed power. We model renewable supplies with the zero production cost function and traditional supplies with convex production cost functions. For two natural storage unit settings, private and public, we design poly-logarithmic competitive algorithms in the network flow model using the dual fitting and online primal dual methods for convex problems. Furthermore, we show strong hardness results for more general settings of the problem. Our techniques may be of independent interest in other routing and storage management problems.

We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function : the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas — Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods.

The software platforms that mediate online learning experiences are the common ground where learning science and computer science intersect. This panel will discuss the affordances of current online learning platforms and lessons learned in using them with students. The goal of the panel is to help learning scientists and computer scientists understand each others' needs and how they might be effectively addressed in these platforms. The panelists, who have experience creating/using these platforms and interacting with learning scientists, will discuss how current platforms for learning at scale might evolve to better serve the community.

Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment.

We study the problem of node placement in a sensor network. We consider proximity-based communication models where each sensor can only communicate with the ones within a given distance from it and the quality of communication between two sensors decreases with their distance. Each sensor can move locally and our goal is to improve the network connectivity by locally relocating the sensors. We use tools from spectral graph theory to determine the criticality of each edge to the global network connectivity. Based on the criticality measure, we develop algorithms that iteratively move the sensors in directions that improve the communication along more critical edges. Our algorithms are fully decentralized and only use local information exchange which are essential features for the sensor network application due to lack of centralized control and access to information in such networks. We formulate our problem as a convex optimization and use techniques from proximal minorant methods to prove the convergence of our iterative algorithms. Further, to make the algorithms fully local we use ideas such as the alternating direction method of multipliers from the distributed optimization literature. We also quantitatively illustrate the effectiveness of our schemes using simulation on a few sample networks.

We study the evolution of cooperation in populations where individuals play prisoner's dilemma on a network. Every node of the network corresponds to an individual choosing whether to cooperate or defect in a repeated game. The players revise their actions by imitating those neighbors who have higher payoffs.

We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem . There are m items and n players. Every item has some nonnegative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovász local lemma that the integrality gap of a certain configuration LP for the problem is no worse than some (unspecified) constant. This gives a polynomial-time algorithm to estimate the optimum value of the problem within a constant factor, but does not provide a polynomial-time algorithm for finding a corresponding allocation. We use a different approach to analyze the integrality gap. Our approach is based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is no worse than 1/4. Our proof provides a local search algorithm which finds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.

We introduce a new framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework, we present online algorithms for several problems including allocation of online advertisement space, load balancing, and facility location.

For some positive constant ϵ0, we give a (3/2-ϵ0)-approximation algorithm for the following problem: given a graph G0= (V,V0), find the shortest tour that visits every vertex at least once. This is a special case of the metric traveling salesman problem when the underlying metric is defined by shortest path distances in Go. The result improves on the 3/2-approximation algorithm due to Christofides [13] for this special case. Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, then it finds the minimum cost Eulerian augmentation (or T-join) of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation. Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strongly Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope from polyhedral theory. Also, as a byproduct of our result, we show new properties of the near minimum cuts of any graph, which may be of independent interest.

We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.

We consider the online stochastic matching problem proposed by Feldman et al. [4] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the size of the matching. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than 1 − 1/e were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that no online algorithm can have a competitive ratio better than 0.823.

We consider a robust model proposed by Scarf, 1958, for stochastic optimization when only the marginal probabilities of (binary) random variables are given, and the correlation between the random variables is unknown. In the robust model, the objective is to minimize expected cost against worst possible joint distribution with those marginals. We introduce the concept of correlation gap to compare this model to the stochastic optimization model that ignores correlations and minimizes expected cost under independent Bernoulli distribution. We identify a class of functions, using concepts of summable cost sharing schemes from game theory, for which the correlation gap is well-bounded and the robust model can be approximated closely by the independent distribution model. As a result, we derive efficient approximation factors for many popular cost functions, like submodular functions, facility location, and Steiner tree. As a byproduct, our analysis also yields some new results in the areas of social welfare maximization and existence of Walrasian equilibria, which may be of independent interest.

We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality.We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability.

We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph Wk such that G+Wk is a good spectral sparsifer of G+W. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on G and W such that a good sparsifier exists and give a polynomial-time algorithm to find the sparsifer.

In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is $\Omega(\frac{1}{\sqrt{k}\log^{3}k})$. As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem.

We study a simple game theoretic model for the spread of an innovation in a network. The diffusion of the innovation is modeled as the dynamics of a coordination game in which the adoption of a common strategy between players has a higher payoff. Classical results in game theory provide a simple condition for an innovation to become widespread in the network. The present paper characterizes the rate of convergence as a function of graph structure. In particular, we derive a dichotomy between well-connected (e.g. random) graphs that show slow convergence and poorly connected, low dimensional graphs that show fast convergence.

We propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for this NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.

We present a simple and efficient algorithm for randomly generating simple graphs without small cycles. These graphs can be used to design high performance Low-Density Parity-Check (LDPC) codes. For any constant k, α ≤ 1/2k(k + 3) and m = O(n1+α), our algorithm generates an asymptotically uniform random graph with n vertices, m edges, and girth larger than k in polynomial time. To the best of our knowledge this is the first polynomial algorithm for the problem. Our algorithm generates a graph by sequentially adding m edges to an empty graph with n vertices. Recently, this type of sequential process has been very successful for efficiently counting and generating random graphs [35, 18, 11, 7, 5, 6].

We study the Cost-Per-Action or Cost-Per-Acquisition (CPA) charging scheme in online advertising. In this scheme, instead of paying per click, the advertisers pay only when a user takes a specific action (e.g. fills out a form) or completes a transaction on their websites.

We give the first polynomial time algorithm for exactly computing an equilibrium for the linear utilities case of the market model defined by Fisher. Our algorithm uses the primal--dual paradigm in the enhanced setting of KKT conditions and convex programs. We pinpoint the added difficulty raised by this setting and the manner in which our algorithm circumvents it.

We focus on efficient protocols that enhance a network with topology awareness. We discuss centralized algorithms with provable performance, and introduce decentralized asynchronous heuristics that use only local information and local computations. These algorithms are based on distributed solutions of convex programs expressing optimization of various spectral properties of the matrix associated with the graph of the network topology. For example, these algorithms assign special weights to links crossing or directed towards small cuts by minimizing the second eigenvalue. Our main technical ingredient is to perform the decentralized asynchronous computations in a manner that preserves critical invariants of the exact second eigenvalue of the adjacency matrix associated with the network topology.

We study the problem of finding approximate Nash equilibria of two player games. We show that for any 0<ε<1, there is no 1 1 + ε - approximate equilibrium with strategies of support O(log n ε2).

We study the problem of optimally allocating online advertisement space to budget-constrained advertisers. This problem was defined and studied from the perspective of worst-case online competitive analysis by Mehta et al.

In this paper we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. The approximation ratio of our algorithm is Ω1√k log3 k. As a part of our algorithm, we design an iterative method for rounding a fractional matching on a tree which might be of independent interest.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/ e for this problem.

Wireless LAN administrators often have to deal with the problem of sporadic client congestion in popular locations within the network. Existing approaches that relieve congestion by balancing the traffic load are encumbered by the modifications that are required to both access points and clients. We propose cell breathing, a well-known concept in cellular telephony, as a load balancing mechanism to handle client congestion in a wireless LAN. We develop power management algorithms for controlling the coverage of access points to handle dynamic changes in client workloads. We further incorporate hand-off costs and manufacturer specified power level constraints into our algorithms. Our approach does not require modification to clients or to the standard. It only changes the transmission power of beacon packets and does not change the transmission power of data packets to avoid the interactions with auto-rating. We analyze the worst-case bounds of the algorithms and show that they are either optimal or close to optimal. In addition, we evaluate our algorithms empirically using synthetic and real wireless LAN traces. Our results show that cell breathing significantly outperforms the commonly used fixed power scheme and performs at par with sophisticated load balancing schemes that require changes to both the client and access points

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs

We study multi-unit auctions for perishable goods, in a setting where the supply arrives online. This is motivated by its application in advertisement auctions on the internet. We give a 1 4 -competitive algorithm for computing the optimal single price auction assuming that all the agents report their bids truthfully. We use that algorithm to develop a truthful auction with a constant competitive ratio compared to the optimum offline single-price auction.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.

We study hybrid search schemes for unstructured peer-to-peer networks. We quantify performance in terms of number of hits, network overhead, and response time. Our schemes combine flooding and random walks, look ahead and replication. We consider both regular topologies and topologies with supernodes. We introduce a general search scheme, of which flooding and random walks are special instances, and show how to use locally maintained network information to improve the performance of searching. Our main findings are: (a) a small number of supernodes in an otherwise regular topology can offer sharp savings in the performance of search, both in the case of search by flooding and search by random walk, particularly when it is combined with 1-step replication. We quantify, analytically and experimentally, that the reason of these savings is that the search is biased towards nodes that yield more information. (b) There is a generalization of search, of which flooding and random walk are special instances, which may take further advantage of locally maintained network information, and yield better performance than both flooding and random walk in clustered topologies. The method determines edge critically and is reminiscent of fundamental heuristics from the area of approximation algorithms.

We study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard assumptions, we prove that it is impossible to design a non-trivial truthful auction which allocates all units, while we provide the design of an asymptotically revenue-maximizing truthful mechanism which may allocate only some of the units. Our asymptotic parameter is a budget dominance parameter which measures the size of the budget of a single agent relative to the maximum revenue. We discuss the relevance of these results for the design of Internet ad auctions.

We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achieves better results than flooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its horizon does not change much. For construction, we argue that an expander can he maintained dynamically with constant operations per addition. The key technical ingredient of our approach is a deep result of stochastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical properties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such connectivity is desired, and believed to hold, in every reasonable network and network model). This property has been previously used in complexity theory for construction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random bits to savings in processing overhead.

We propose to use the community structure of Usenet for organizing and retrieving the information stored in newsgroups. In particular, we study the network formed by cross-posts, messages that are posted to two or more newsgroups simultaneously. We present what is, to our knowledge, by far the most detailed data that has been collected on Usenet cross-postings. We analyze this network to show that it is a small-world network with significant clustering. We also present a spectral algorithm which clusters newsgroups based on the cross-post matrix. The result of our clustering provides a topical classification of newsgroups. Our clustering gives many examples of significant relationships that would be missed by semantic clustering methods.

We study the problem of fairly allocating a set of indivisible goods to a set of people from an algorithmic perspective. fair division has been a central topic in the economic literature and several concepts of fairness have been suggested. The criterion that we focus on is envy-freeness. In our model, a monotone utility function is associated with every player specifying the value of each subset of the goods for the player. An allocation is envy-free if every player prefers her own share than the share of any other player. When the goods are divisible, envy-free allocations always exist. In the presence of indivisibilities, we show that there exist allocations in which the envy is bounded by the maximum marginal utility, and present a simple algorithm for computing such allocations. We then look at the optimization problem of finding an allocation with minimum possible envy. In the general case the problem is not solvable or approximable in polynomial time unless P = NP. We consider natural special cases (e.g.additive utilities) which are closely related to a class of job scheduling problems. Approximation algorithms as well as inapproximability results are obtained. Finally we investigate the problem of designing truthful mechanisms for producing allocations with bounded envy.

We show that random graphs in the preferential connectivity model have constant conductance, and hence have worst-case routing congestion that scales logarithmically with the number of nodes. Another immediate implication is constant spectral gap between the first and second eigenvalues of the random walk matrix associated with these graphs. We also show that the expected frugality (overpayment in the Vickrey-Clarke-Groves mechanism for shortest paths) of a random graph is bounded by a small constant.

In citepapa, Papadimitriou formalized the notion of routing stability in BGP as the following coalitional game theoretic problem: Given a network with a multicommodity flow satisfying node capacity and demand constraints, the payoff of a node is the total flow originated or terminated at it. A payoff allocation is in the core if and only if there is no subset of nodes that can increase their payoff by seceding from the network. We answer one of the open problems in citepapa by proving that for any network, the core is non-empty in both the transferable (where the nodes can compensate each other with side payments) and the non-transferable case. In the transferable case we show that such an allocation can be computed in polynomial time. We also generalize this result to the case where a strictly concave utility function is associated with each commodity.

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees du and dv we have O(dudv ) units of demand. Thus the total demand is O(n ). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O . This is to be compared with a bound # that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O ( m log m ) and O ( n 3 ), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

Although the study of market equilibria has occupied center stage within mathematical economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's (1995) primal-dual algorithm for bipartite matching.

We study a fundamental problem in microeconomics called optimal auction design: a seller wishes to sell an item to a group of self-interested agents. Each agent i has a privately known valuation v/sub i/ for the object. Given a distribution on these valuations, the goal is to construct an optimal auction, i.e. a truth revealing protocol that maximizes the seller's expected revenue. We study this problem from a computational perspective and show several lower bounds. In particular we prove that no deterministic polynomial time ascending auction can achieve an approximation ratio better than 3/4. The probability distribution constructed in our example has sensitive dependencies among the agents. In contrast, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1.

We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k-median and facility location problems. We also prove a lower bound of 1+2/e on the approximability of the k-median problem. At the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.