NDLI: On the effect of randomness on planted 3-coloring models

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

Almost tight bounds for eliminating depth cycles in three dimensions

Constant-round interactive proofs for delegating computation

Complexity theoretic limitations on learning halfspaces

Lift-and-round to improve weighted completion time on unrelated machines

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Optimal principal component analysis in distributed and streaming models

Two-source dispersers for polylogarithmic entropy and improved ramsey graphs

Parallel exhaustive search without coordination

A tight space bound for consensus

Cell-probe lower bounds for dynamic problems via a new communication model

Algorithmic Bayesian persuasion

Distributed (∆+1)-coloring in sublogarithmic rounds

Fault tolerant subgraph for single source reachability: generic and optimal

Improved approximation for node-disjoint paths in planar graphs

Near-optimal small-depth lower bounds for small distance connectivity

Reed-Muller codes achieve capacity on erasure channels

Tight bounds for single-pass streaming complexity of the set cover problem

Bipartite perfect matching is in quasi-NC

Semidefinite programs on sparse random graphs and their application to community detection

Separations in query complexity using cheat sheets

A duality based unified approach to Bayesian mechanism design

Exponential separation of communication and external information

A polynomial lower bound for testing monotonicity

Algebraic attacks against random local functions and their countermeasures

Geometric median in nearly linear time

Candidate hard unique game

A cost function for similarity-based hierarchical clustering

A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

Repairing Reed-solomon codes

Weighted low rank approximations with provable guarantees

Non-malleable extractors and codes, with their many tampered extensions

Beyond matroids: secretary problem and prophet inequality with general constraints

The 4/3 additive spanner exponent is tight

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

The sample complexity of auctions with side information

A lower bound for the distributed Lovász local lemma

Deterministic and probabilistic binary search in graphs

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

On the size of homogeneous and of depth four formulas with low individual degree

Explicit two-source extractors and resilient functions

Streaming algorithms for embedding and computing edit distance in the low distance regime

Exact algorithms via monotone local search

How robust are reconstruction thresholds for community detection?

Entangled simultaneity versus classical interactivity in communication complexity

Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders

Interactive compression for product distributions

Relating two property testing models for bounded degree directed graphs

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations

Separating subadditive euclidean functionals

On the effect of randomness on planted 3-coloring models

The computational power of optimization in online learning

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Efficiently decoding Reed-Muller codes from random errors

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

Extractors for sumset sources

Online matching: haste makes waste!

Deterministic decremental single source shortest paths: beyond the o(mn) bound

Do prices coordinate markets?

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Ramanujan coverings of graphs

Approximating connectivity domination in weighted bounded-genus graphs

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

Graph isomorphism in quasipolynomial time [extended abstract]

On approximating functions of the singular values in a stream

Basis collapse for holographic algorithms over all domain sizes

Sparsified Cholesky and multigrid solvers for connection laplacians

Classical verification of quantum proofs

Watch and learn: optimizing from revealed preferences feedback

Constant-rate coding for multiparty interactive communication is impossible

Algorithmic stability for adaptive data analysis

Watermarking cryptographic capabilities

Bounded degree cosystolic expanders of every dimension

Matrix rigidity of random toeplitz matrices

Instance optimal learning of discrete distributions

Maximizing determinants under partition constraints

New deterministic approximation algorithms for fully dynamic matching

A discrete and bounded envy-free cake cutting protocol for four agents

Contention resolution with log-logstar channel accesses

Enumerating parametric global minimum cuts by random interleaving

Routing under balance

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

Beating CountSketch for heavy hitters in insertion streams

Base collapse of holographic algorithms

Parallel algorithms for select and partition with noisy comparisons

Efficient quantum tomography

The price of anarchy in large games

Communication lower bounds for statistical estimation problems via a distributed data processing inequality

The fourier transform of poisson multinomial distributions and its algorithmic applications

Textbook non-malleable commitments

Separations in query complexity based on pointer functions

Sample-optimal tomography of quantum states

A size-free CLT for poisson multinomials and its applications

On the effect of randomness on planted 3-coloring models

Content Provider	ACM Digital Library
Author	David, Roee Feige, Uriel
Abstract	We present the hosted coloring framework for studying al- gorithmic and hardness results for the k-coloring problem. There is a class H of host graphs. One selects a graph H ∈ H and plants in it a balanced k-coloring (by partitioning the vertex set into k roughly equal parts, and removing all edges within each part). The resulting graph G is given as input to a polynomial time algorithm that needs to k-color G (any legal k-coloring would do – the algorithm is not required to recover the planted k-coloring). Earlier planted models correspond to the case that H is the class of all n-vertex d-regular graphs, a member H ∈ H is chosen at random, and then a balanced k-coloring is planted at random. Blum and Spencer [1995] designed algorithms for this model when d = n δ (for 0 < δ ≤ 1), and Alon and Kahale [1997] managed to do so even when d is a sufficiently large constant. The new aspect in our framework is that it need not in- volve randomness. In one model within the framework (with k = 3) H is a d regular spectral expander (meaning that ex- cept for the largest eigenvalue of its adjacency matrix, every other eigenvalue has absolute value much smaller than d) chosen by an adversary, and the planted 3-coloring is ran- dom. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In an- other model H is a random d-regular graph but the planted balanced 3-coloring is chosen by an adversary, after seeing H. We show that for a certain range of average degrees somewhat below √ n, finding a 3-coloring is NP-hard. To- gether these results (and other results that we have) help clarify which aspects of randomness in the planted coloring model are the key to successful 3-coloring algorithms. .
Starting Page	77
Ending Page	90
Page Count	14
File Format	PDF
ISBN	9781450341325
DOI	10.1145/2897518.2897561
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Exact recovery Expanders Np-hardness Adversary
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