BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Sushant Sachdeva

Sushant Sachdeva appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsMachine Learningmath.OCDiscrete Mathematicsmath.NANumerical Analysismath.COComputational Complexitymath.CAmath.MGmath.STphysics.soc-phSocial and Information NetworksStatistics Theory

Catalog footprint

What is connected

24works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2022arXiv

A Convergent and Dimension-Independent Min-Max Optimization Algorithm

We study a variant of a recently introduced min-max optimization framework where the max-player is constrained to update its parameters in a greedy manner until it reaches a first-order stationary point. Our equilibrium definition for this framework depends on a proposal distribution which the min-player uses to choose directions in which to update its parameters. We show that, given a smooth and bounded nonconvex-nonconcave objective function, access to any proposal distribution for the min-player's updates, and stochastic gradient oracle for the max-player, our algorithm converges to the aforementioned approximate local equilibrium in a number of iterations that does not depend on the dimension. The equilibrium point found by our algorithm depends on the proposal distribution, and when applying our algorithm to train GANs we choose the proposal distribution to be a distribution of stochastic gradients. We empirically evaluate our algorithm on challenging nonconvex-nonconcave test-functions and loss functions arising in GAN training. Our algorithm converges on these test functions and, when used to train GANs, trains stably on synthetic and real-world datasets and avoids mode collapse

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, $p$-norm flows, and $p$-norm isotonic regression on arbitrary directed acyclic graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\text{poly}(\log n))$ time [Daitch-Spielman, STOC'08]. Intuitively, $Ω(n^{1.5})$ is a natural runtime barrier for IPM-based methods, since they require $\sqrt{n}$ iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly $\sqrt{n}$ update time, resulting in a total running time of $O(n\cdot\text{poly}(\log n))$. Our results immediately extend to all families of separable graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{th}$-order smooth, monotone operators -- a problem that generalizes convex optimization and saddle-point problems. Recent works (Bullins and Lai (2020), Lin and Jordan (2021), Jiang and Mokhtari (2022)) present methods that achieve a rate of $\tilde{O}(ε^{-2/(p+1)})$ for $p\geq 1$, extending results by (Nemirovski (2004)) and (Monteiro and Svaiter (2012)) for $p=1,2$. A drawback to these approaches, however, is their reliance on a line search scheme. We provide the first $p^{\textrm{th}}$-order method that achieves a rate of $O(ε^{-2/(p+1)}).$ Our method does not rely on a line search routine, thereby improving upon previous rates by a logarithmic factor. Building on the Mirror Prox method of Nemirovski (2004), our algorithm works even in the constrained, non-Euclidean setting. Furthermore, we prove the optimality of our algorithm by constructing matching lower bounds. These are the first lower bounds for smooth MVIs beyond convex optimization for $p > 1$. This establishes a separation between solving smooth MVIs and smooth convex optimization, and settles the oracle complexity of solving $p^{\textrm{th}}$-order smooth MVIs.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Almost-linear-time Weighted $\ell_p$-norm Solvers in Slightly Dense Graphs via Sparsification

We give almost-linear-time algorithms for constructing sparsifiers with $n\ poly(\log n)$ edges that approximately preserve weighted $(\ell^{2}_2 + \ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit $\ell_p$ weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find $(1+2^{-\text{poly}(\log n)})$ approximations for weighted $\ell_p$-norm minimizing flows or voltages in $p(m^{1+o(1)} + n^{4/3 + o(1)})$ time for $p=ω(1),$ which is almost-linear for graphs that are slightly dense ($m \ge n^{4/3 + o(1)}$).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

Linear regression in $\ell_p$-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving $\ell_p$-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p > 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that is guaranteed to converge rapidly for p > 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any $p \in [2,\infty).$ Our algorithm is simple to implement and is guaranteed to find a $(1+\varepsilon)$-approximate solution in $O(p^{3.5} m^{\frac{p-2}{2(p-1)}} \log \frac{m}{\varepsilon}) \le O_p(\sqrt{m} \log \frac{m}{\varepsilon} )$ iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10--50x, and is the fastest among available implementations in the high-accuracy regime.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster p-norm minimizing flows, via smoothed q-norm problems

We present faster high-accuracy algorithms for computing $\ell_p$-norm minimizing flows. On a graph with $m$ edges, our algorithm can compute a $(1+1/\text{poly}(m))$-approximate unweighted $\ell_p$-norm minimizing flow with $pm^{1+\frac{1}{p-1}+o(1)}$ operations, for any $p \ge 2,$ giving the best bound for all $p\gtrsim 5.24.$ Combined with the algorithm from the work of Adil et al. (SODA '19), we can now compute such flows for any $2\le p\le m^{o(1)}$ in time at most $O(m^{1.24}).$ In comparison, the previous best running time was $Ω(m^{1.33})$ for large constant $p.$ For $p\simδ^{-1}\log m,$ our algorithm computes a $(1+δ)$-approximate maximum flow on undirected graphs using $m^{1+o(1)}δ^{-1}$ operations, matching the current best bound, albeit only for unit-capacity graphs. We also give an algorithm for solving general $\ell_{p}$-norm regression problems for large $p.$ Our algorithm makes $pm^{\frac{1}{3}+o(1)}\log^2(1/\varepsilon)$ calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted $\ell_{p}$-norm minimizing flows that runs in time $o(m^{1.5})$ for some $p=m^{Ω(1)}.$ Our key technical contribution is to show that smoothed $\ell_p$-norm problems introduced by Adil et al., are interreducible for different values of $p.$ No such reduction is known for standard $\ell_p$-norm problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Framework for Analyzing Resparsification Algorithms

A spectral sparsifier of a graph $G$ is a sparser graph $H$ that approximately preserves the quadratic form of $G$, i.e. for all vectors $x$, $x^T L_G x \approx x^T L_H x$, where $L_G$ and $L_H$ denote the respective graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have found many applications in designing graph algorithms. In recent years, there has been interest in computing spectral sparsifiers in semi-streaming and dynamic settings. Natural algorithms in these settings often involve repeated sparsification of a graph, and accumulation of errors across these steps. We present a framework for analyzing algorithms that perform repeated sparsifications that only incur error corresponding to a single sparsification step, leading to better results for many resparsification-based algorithms. As an application, we show how to maintain a spectral sparsifier in the semi-streaming setting: We present a simple algorithm that, for a graph $G$ on $n$ vertices and $m$ edges, computes a spectral sparsifier of $G$ with $O(n \log n)$ edges in a single pass over $G$, using only $O(n \log n)$ space, and $O(m \log^2 n)$ total time. This improves on previous best semi-streaming algorithms for both spectral and cut sparsifiers by a factor of $\log{n}$ in both space and runtime. The algorithm extends to semi-streaming row sampling for general PSD matrices. We also use our framework to combine a spectral sparsification algorithm by Koutis with improved spanner constructions to give a parallel algorithm for constructing $O(n\log^2{n}\log\log{n})$ sized spectral sparsifiers in $O(m\log^2{n}\log\log{n})$ time. This is the best known combinatorial graph sparsification algorithm.The size of the sparsifiers is only a factor $\log{n}\log\log{n}$ more than ones produced by numerical routines.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Arithmetic Analogue of Fox's Triangle Removal Argument

We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group $\mathbb{F}_2^n$. A triangle in $\mathbb{F}_2^n$ is a triple $(x,y,z)$ such that $x+y+z = 0$. The triangle removal lemma for $\mathbb{F}_2^n$ states that for every $ε> 0$ there is a $δ> 0$, such that if a subset $A$ of $\mathbb{F}_2^n$ requires the removal of at least $ε\cdot 2^n$ elements to make it triangle-free, then it must contain at least $δ\cdot 2^{2n}$ triangles. This problem was first studied by Green [Gre05] who proved a lower bound on $δ$ using an arithmetic regularity lemma. Regularity based lower bounds for triangle removal in graphs were recently improved by Fox and we give a direct proof of an analogous improvement for triangle removal in $\mathbb{F}_2^n$. The improved lower bound was already known to follow (for triangle-removal in all groups), using Fox's removal lemma for directed cycles and a reduction by Král, Serra and Vena [KSV09] (see [Fox11,CF13]). The purpose of this note is to provide a direct Fourier-analytic proof for the group $\mathbb{F}_2^n.$

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization, the version of Gaussian elimination for symmetric matrices. This is the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our analysis is a novel concentration bound for matrix martingales where the differences are sums of conditionally independent variables.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Matrix Inversion Is As Easy As Exponentiation

We prove that the inverse of a positive-definite matrix can be approximated by a weighted-sum of a small number of matrix exponentials. Combining this with a previous result [OSV12], we establish an equivalence between matrix inversion and exponentiation up to polylogarithmic factors. In particular, this connection justifies the use of Laplacian solvers for designing fast semi-definite programming based algorithms for certain graph problems. The proof relies on the Euler-Maclaurin formula and certain bounds derived from the Riemann zeta function.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof

We study the mixing time of the Dikin walk in a polytope - a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing time are important for algorithms for sampling and optimization over polytopes. Here, we provide a simple proof of their result that this random walk mixes in time O(mn) for an n-dimensional polytope described using m inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Algorithms for Lipschitz Learning on Graphs

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large $p$ of $p$-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time $\widetilde{O} (m n)$. The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform $l_{0}$-regularization on the given values in polynomial time and $l_{1}$-regularization on the initial function values and on graph edge weights in time $\widetilde{O} (m^{3/2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fast, Provable Algorithms for Isotonic Regression in all $\ell_{p}$-norms

Given a directed acyclic graph $G,$ and a set of values $y$ on the vertices, the Isotonic Regression of $y$ is a vector $x$ that respects the partial order described by $G,$ and minimizes $||x-y||,$ for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted $\ell_{p}$-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Simultaneous Approximation of Constraint Satisfaction Problems

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context. Our main result is that for every CSP $F$, for $k < \tilde{O}(\log^{1/4} n)$, there is a polynomial time constant factor Pareto approximation algorithm for $k$ simultaneous Max-$F$-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for $k <\tilde{O}(\log^{1/3} n)$). In contrast, for $k = ω(\log n)$, no nonzero approximation factor for $k$ simultaneous Max-$F$-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis). These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximation Theory and the Design of Fast Algorithms

We survey key techniques and results from approximation theory in the context of uniform approximations to real functions such as e^{-x}, 1/x, and x^k. We then present a selection of results demonstrating how such approximations can be used to speed up primitives crucial for the design of fast algorithms for problems such as simulating random walks, graph partitioning, solving linear system of equations, computing eigenvalues and combinatorial approaches to solve semi-definite programs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cuts in Cartesian Products of Graphs

The k-fold Cartesian product of a graph G is defined as a graph on k-tuples of vertices, where two tuples are connected if they form an edge in one of the positions and are equal in the rest. Starting with G as a single edge gives G^k as a k-dimensional hypercube. We study the distributions of edges crossed by a cut in G^k across the copies of G in different positions. This is a generalization of the notion of influences for cuts on the hypercube. We show the analogues of results of Kahn, Kalai, and Linial (KKL Theorem [KahnKL88]) and that of Friedgut (Friedgut's Junta theorem [Friedgut98]), for the setting of Cartesian products of arbitrary graphs. Our proofs extend the arguments of Rossignol [Rossignol06] and of Falik and Samorodnitsky [FalikS07], to the case of arbitrary Cartesian products. We also extend the work on studying isoperimetric constants for these graphs [HoudreT96, ChungT98] to the value of semidefinite relaxations for edge-expansion. We connect the optimal values of the relaxations for computing expansion, given by various semidefinite hierarchies, for G and G^k.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders

We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form $y = Ax + η$ where $A$ is an unknown $n \times n$ matrix and $x$ is a random variable whose components are independent and have a fourth moment strictly less than that of a standard Gaussian random variable and $η$ is an $n$-dimensional Gaussian random variable with unknown covariance $Σ$: We give an algorithm that provable recovers $A$ and $Σ$ up to an additive $ε$ and whose running time and sample complexity are polynomial in $n$ and $1 / ε$. To accomplish this, we introduce a novel "quasi-whitening" step that may be useful in other contexts in which the covariance of Gaussian noise is not known in advance. We also give a general framework for finding all local optima of a function (given an oracle for approximately finding just one) and this is a crucial step in our algorithm, one that has been overlooked in previous attempts, and allows us to control the accumulation of error when we find the columns of $A$ one by one via local search.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Testing Permanent Oracles -- Revisited

Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task. The oracle-testing problem is of interest because a recent paper of Aaronson and Arkhipov showed that if there is a polynomial-time algorithm for simulating boson-boson interactions in quantum mechanics, then an approximation oracle for the permanent (of the type described above) exists in BPP^NP. Since computing the permanent of even 0/1 matrices is #P-complete, this seems to demonstrate more computational power in quantum mechanics than Shor's factoring algorithm does. However, unlike factoring, which is in NP, it was unclear previously how to test the correctness of an approximation oracle for the permanent, and this is the contribution of the paper. The technical difficulty overcome here is that univariate polynomial self-correction, which underlies similar oracle-testing algorithms for permanent over finite fields --- and whose discovery led to a revolution in complexity theory --- does not seem to generalize to complex (or even, real) numbers. We believe that this tester will motivate further progress on understanding the permanent of Gaussian matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Reformulation of the Arora-Rao-Vazirani Structure Theorem

In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut. At the heart of their result is a geometric statement about sets of points that satisfy triangle inequalities, which also underlies subsequent work on approximation algorithms and geometric embeddings. In this note, we give an equivalent formulation of the Structure theorem in [ARV] in terms of the expansion of large sets in geometric graphs on sets of points satisfying triangle inequalities.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter γ, either finds an Ω(b)-balanced cut of conductance O(\sqrt(γ)) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least γ, and runs in time \tilde{O}(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute \exp(-L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to \exp(-A)v for a class of PSD matrices A and a given vector u, in time roughly \tilde{O}(m_A), where m_A is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting SDD matrices in \tilde{O}(m_A) time. Finally, we prove e^{-x} can be uniformly approximated up to a small additive error, in a non-negative interval [a,b] with a polynomial of degree roughly \sqrt{b-a}. While this result is of independent interest in approximation theory, we show that, via the Lanczos method from numerical analysis, it yields a simple algorithm to compute \exp(-A)v for PSD matrices that runs in time roughly O(t_A \sqrt{||A||}), where t_A is the time required for computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(\sqrt(γ)), for balanced separator that runs in time \tilde{O}(m/\sqrt(γ)). This latter algorithm matches the running time, but improves on the approximation guarantee of the algorithm by Andersen and Peres.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

A "community" in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, etc. For many years algorithms for finding communities implicitly assumed communities are nonoverlapping (leading to use of clustering-based approaches) but there is increasing interest in finding overlapping communities. A barrier to finding communities is that the solution concept is often defined in terms of an NP-complete problem such as Clique or Hierarchical Clustering. This paper seeks to initiate a rigorous approach to the problem of finding overlapping communities, where "rigorous" means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time. Our assumptions about the network lie between worst-case and average-case. An average case analysis would require a precise probabilistic model of the network, on which there is currently no consensus. However, some plausible assumptions about network parameters can be gleaned from a long body of work in the sociology community spanning five decades focusing on the study of individual communities and ego-centric networks. Thus our assumptions are somewhat "local" in nature. Nevertheless they suffice to permit a rigorous analysis of running time of algorithms that recover global structure. Our algorithms use random sampling similar to that in property testing and algorithms for dense graphs. However, our networks are not necessarily dense graphs, not even in local neighborhoods. Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work both in computer science and sociology.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover can be computed in polynomial time. For general k, the problem was studied by Lovász, who gave a k/2 -approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich showed a tight integrality gap of (k/2 - o(1)) for the LP relaxation. While this problem was known to be NP-hard for k >= 3, the first non-trivial NP-hardness of approximation factor of k/4- \eps was shown in a recent work by Guruswami and Saket. They also showed that assuming Khot's Unique Games Conjecture yields a k/2 - \eps inapproximability for this problem, implying the optimality of Lovász's result. In this work, we show that this problem is NP-hard to approximate within k/2- 1 + 1/2k -\eps. This hardness factor is off from the optimal by an additive constant of at most 1 for k >= 4. Our reduction relies on the Multi-Layered PCP of Dinur et al. and uses a gadget - based on biased Long Codes - adapted from the LP integrality gap of Aharoni et al. The nature of our reduction requires the analysis of several Long Codes with different biases, for which we prove structural properties of the so called cross-intersecting collections of set families - variants of which have been studied in extremal set theory.

0 citations0 reviewsNo code linkedOpen access