NDLI: (1 + Ω(1))-approximation to MAX-CUT requires linear space

Please wait, while we are loading the content...

Proximity in the age of distraction: robust approximate nearest neighbor search

High-dimensional approximate r-nets

A framework for similarity search with space-time tradeoffs using locality-sensitive filtering

Optimal hashing-based time-space trade-offs for approximate near neighbors

LSH forest: practical algorithms made theoretical

Faster approximation schemes for the two-dimensional knapsack problem

Split packing: an algorithm for packing circles with optimal worst-case density

Stochastic k-center and j-flat-center problems

Local search for max-sum diversification

Maximum scatter TSP in doubling metrics

Matrix balancing in $L_{p}$ norms: bounding the convergence rate of osborne's iteration

Decidability of the membership problem for 2 × 2 integer matrices

The identity problem for matrix semigroups in $SL_{2}(ℤ)$ is NP-complete

Exploring an infinite space with finite memory scouts

Universal shape replicators via self-assembly with attractive and repulsive forces

Parameter-free locality sensitive hashing for spherical range reporting

Distance sensitive bloom filters without false negatives

Optimal approximate polytope membership

Massively-parallel similarity join, edge-isoperimetry, and distance correlations on the hypercube

Even delta-matroids and the complexity of planar boolean CSPs

Linear diophantine equations, group CSPs, and graph isomorphism

Robust algorithms with polynomial loss for near-unanimity CSPs

Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

Hardness of permutation pattern matching

pBWT: achieving succinct data structures for parameterized pattern matching and related problems

Space-efficient construction of compressed indexes in deterministic linear time

Sparse suffix tree construction in optimal time and space

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

Deterministic partially dynamic single source shortest paths for sparse graphs

Fully dynamic approximate maximum matching and minimum vertex cover in $O(log^{3}$ n) worst case update time

Connectivity oracles for graphs subject to vertex failures

Fully dynamic connectivity in O(log n(log log $n)^{2})$ amortized expected time

Best-response dynamics in combinatorial auctions with item bidding

Approximating spanners and directed steiner forest: upper and lower bounds

Convergence of incentive-driven dynamics in fisher markets

A hierarchy of lower bounds for sublinear additive spanners

Totally unimodular congestion games

LAST but not least: online spanners for buy-at-bulk

Linear size distance preservers

Playing anonymous games using simple strategies

Computing walrasian equilibria: fast algorithms and structural properties

Efficient algorithms for constructing very sparse spanners and emulators

Metric embeddings with outliers

Probabilistic clustering of high dimensional norms

Near-optimal (euclidean) metric compression

A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs

Beyond metric embedding: approximating group steiner trees on bounded treewidth graphs

Negative-weight shortest paths and unit capacity minimum cost flow in $Õ(m^{10/7}$ log W) time: (extended abstract)

Generalized preconditioning and undirected minimum-cost flow

Scaling algorithms for weighted matching in general graphs

Near-linear time approximation schemes for some implicit fractional packing problems

Fast and memory-efficient algorithms for evacuation problems

Approximate hierarchical clustering via sparsest cut and spreading metrics

Approximating multicut and the demand graph

Minimum fill-in: inapproximability and almost tight lower bounds

Minimizing the union: tight approximations for small set bipartite vertex expansion

Approximation algorithms for label cover and the log-density threshold

An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs

Find your place: simple distributed algorithms for community detection

Sorting from noisier samples

Sampling on the sphere by mutually orthogonal subspaces

Exponential segregation in a two-dimensional schelling model with tolerant individuals

Tight bounds for online TSP on the line

An improved upper bound for the universal TSP on the grid

The (h, k)-server problem on bounded depth trees

Online lower bounds via duality

Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays

A faster pseudopolynomial time algorithm for subset sum

A near-linear pseudopolynomial time algorithm for subset sum

Computing minimum cuts in hypergraphs

Random contractions and sampling for hypergraph and hedge connectivity

Sandpile prediction on a tree in near linear time

Explicit resilient functions matching ajtai-linial

Optimal induced universal graphs for bounded-degree graphs

Approximation algorithms for finding maximum induced expanders

Parallel algorithms and concentration bounds for the lovász local lemma via witness-DAGs

Deterministic parallel algorithms for fooling polylogarithmic juntas and the lovász local lemma

Online submodular maximization with free disposal: randomization beats 1/4 for partition matroids

Reordering buffers with logarithmic diameter dependency for trees

O(depth)-competitive algorithm for online multi-level aggregation

Competitive analysis of the top-K ranking problem

Statistical query algorithms for mean vector estimation and stochastic convex optimization

Sample-optimal density estimation in nearly-linear time

On rationality of nonnegative matrix factorization

Make up your mind: the price of online queries in differential privacy

ETH hardness for densest-k-subgraph with perfect completeness

The rainbow at the end of the line: a PPAD formulation of the colorful carathéodory theorem with applications

Hardness of continuous local search: query complexity and cryptographic lower bounds

LP relaxations of some NP-hard problems are as hard as any LP

Feedback vertex set inspired kernel for chordal vertex deletion

Approximation and kernelization for chordal vertex deletion

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

Spanning circuits in regular matroids

Algorithmic and hardness results for the hub labeling problem

Beyond highway dimension: small distance labels using tree skeletons

(1 + ϵ)-approximate f-sensitive distance oracles

On the insertion time of random walk cuckoo hashing

File maintenance: when in doubt, change the layout!

Cross-referenced dictionaries and the limits of write optimization

Polynomial kernels and wideness properties of nowhere dense graph classes

Partitioning a graph into small pieces with applications to path transversal

LP-branching algorithms based on biased graphs

About the structure of the integer cone and its application to bin packing

Testing for forbidden order patterns in an array

Sequential measurements, disturbance and property testing

A tight bound for green's arithmetic triangle removal lemma in vector spaces

Permutation property testing under different metrics with low query complexity

Online and random-order load balancing simultaneously

Building a good team: secretary problems and the supermodular degree

Combinatorial prophet inequalities

Adaptivity gaps for stochastic probing: submodular and XOS functions

(1 + Ω(1))-approximation to MAX-CUT requires linear space

On estimating maximum matching size in graph streams

Faster sublinear algorithms using conditional sampling

Input sparsity time low-rank approximation via ridge leverage score sampling

A hybrid sampling scheme for triangle counting

An FPTAS for counting proper four-colorings on cubic graphs

Random cluster dynamics for the ising model is rapidly mixing

Approximately sampling elements with fixed rank in graded posets

Random walks with the minimum degree local rule have $O(N^{2})$ cover time

Random walks and evolving sets: faster convergences and limitations

An O(nm) time algorithm for finding the min length directed cycle in a graph

Strong connectivity in directed graphs under failures, with applications

Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs

Local flow partitioning for faster edge connectivity

Doubly balanced connected graph partitioning

Three colors suffice: conflict-free coloring of planar graphs

LP-based robust algorithms for noisy minor-free and bounded treewidth graphs

LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs

Partial and constrained level planarity

Accurate and nearly optimal sublinear approximations to ulam distance

A framework for analyzing resparsification algorithms

Adaptive matrix vector product

Low-rank PSD approximation in input-sparsity time

Locally testable and locally correctable codes approaching the gilbert-varshamov bound

Maximally recoverable codes for grid-like topologies

MDS code constructions with small sub-packetization and near-optimal repair bandwidth

Bridging the capacity gap between interactive and one-way communication

Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

A (2 + ϵ)-approximation for maximum weight matching in the semi-streaming model

Completeness for first-order properties on sparse structures with algorithmic applications

Faster online matrix-vector multiplication

Beating brute force for systems of polynomial equations over finite fields

The complexity of simulation and matrix multiplication

Better approximations for tree sparsity in nearly-linear time

Counting matchings in irregular bipartite graphs and random lifts

A constant-time algorithm for middle levels gray codes

On max-clique for intersection graphs of sets and the hadwiger-debrunner numbers

Core congestion is inherent in hyperbolic networks

Better upper bounds on the füredi-hajnal limits of permutations

Popularity, mixed matchings, and self-duality

Constant approximation algorithm for non-uniform capacitated multi-item lot-sizing via strong covering inequalities

Small extended formulation for knapsack cover inequalities from monotone circuits

Extension complexity lower bounds for mixed-integer extended formulations

Opting into optimal matchings

Firefighting on trees beyond integrality gaps

Beating approximation factor two for weighted tree augmentation with bounded costs

Simplex transformations and the multiway cut problem

To augment or not to augment: solving unsplittable flow on a path by creating slack

Optimization of bootstrapping in circuits

Geodesic spanners for points on a polyhedral terrain

Computing the fréchet distance between real-valued surfaces

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances

Eliminating depth cycles among triangles in three dimensions

Dynamic planar voronoi diagrams for general distance functions and their algorithmic applications

Distributed degree splitting, edge coloring, and orientations

Tight network topology dependent bounds on rounds of communication

Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits

Time-space trade-offs in population protocols

Fair coin flipping: tighter analysis and the many-party case

Fair scheduling via iterative quasi-uniform sampling

A logarithmic additive integrality gap for bin packing

Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs

Iterative partial rounding for vertex cover with hard capacities

Unrelated machine scheduling of jobs with uniform smith ratios

On the configuration-LP of the restricted assignment problem

When and why the topological coverage criterion works

Deciding contractibility of a non-simple curve on the boundary of a 3-manifold

An efficient representation for filtrations of simplicial complexes

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first betti number

Parameter-free topology inference and sparsification for data on manifolds

(1 + Ω(1))-approximation to MAX-CUT requires linear space

Content Provider	ACM Digital Library
Author	Kapralov, Michael Khanna, Sanjeev Sudan, Madhu Velingker, Ameya
Abstract	We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $ϵ_{}$ > 0 such that any randomized streaming algorithm that computes a (1 + $ϵ_{})-approximation$ to MAX-CUT requires Ω(n) space on an n vertex graph. By contrast, there are algorithms that produce a (1 + ϵ)-approximation in space $O(n/ϵ^{2})$ for every ϵ > 0. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the literature [2]. The prior state of the art ruled out (2 ™ ϵ)-approximation in [EQUATION] space or (1 + ϵ)-approximation in $n^{1™O(ϵ)}$ space, for any ϵ > 0. Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given some edges of a graph and they wish to determine if the union of these edges is ϵ-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of [EQUATION] for this task when ϵ = 1/2, and $n^{1™O(ϵ)}$ for every ϵ > 0, even when one of the players is given a candidate bipartition of the graph and the graph is promised to be bipartite with respect to this partition or ϵ-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an $n^{1™O(ϵ)}$ communication protocol for this problem. In this work, we give an Ω(n) lower bound on the communication complexity of the original problem (without the extra information) for ϵ = Ω(1) in the three-player setting. Obtaining this Ω(n) lower bound on the communication complexity is the main technical result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity.
Starting Page	1703
Ending Page	1722
Page Count	20
File Format	PDF
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-01-16
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in