skip to main content


Title: Is Planted Coloring Easier than Planted Clique?
Award ID(s):
2007443
NSF-PAR ID:
10437160
Author(s) / Creator(s):
Date Published:
Journal Name:
Conference on Learning Theory
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Winter wheat is a main cereal crop grown in the United States of America (USA), and the USA is the third largest wheat exporter globally. Timely and reliable in-season forecast and year-end estimation of winter wheat grain production in the USA are needed for regional and global food security. In this study, we assessed the consistency between the agricultural statistical reports and satellite-based data for winter wheat over the contiguous US (CONUS) at both the county and national scales. First, we compared the planted area estimates from the National Agricultural Statistics Service (NASS) and the Cropland Data Layer (CDL) from 2008–2018. Second, we investigated the relationship between gross primary production (GPP) estimated by the vegetation photosynthesis model (VPM) and grain production from the NASS. Lastly, we explored the in-season utility of GPPVPM in monitoring seasonal production. Strong spatiotemporal consistency of planted areas was found between the NASS and CDL datasets. However, in the Southern Great Plains, both the CDL and NASS planted acreage were noticeable larger (>20%) than the NASS harvested area, where some winter wheat fields were used as forage for cattle grazing. County-level GPPVPM was linearly related with grain production of winter wheat, with an R2 value of 0.68 across the CONUS. The relationships between grain production and GPPVPM in those counties without a substantial difference (<20%) between planted and harvested area were much stronger and their harvest index (HIGPP) values ranged from 0.2–0.3. GPPVPM in May could explain about 70–90% of the variance of winter wheat grain production. Our findings highlight the potential of GPPVPM in winter wheat monitoring, especially for those high harvested/planted ratio, which could provide useful data to guide planning and marketing for decision makers, stakeholders, and the public. 
    more » « less
  2. We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian 2001. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices (Mehta, Mckenzie, Trevisan 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching n1/2 -- the information-theoretic threshold in the semi-random model (Steinhardt 2017) and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige 2019 and Steinhardt 2017. Our algorithms are based on higher constant degree sum-of-squares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite Erdős--Rényi random graphs into algorithms for semi-random planted clique. The use of a higher-constant degree sum-of-squares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size k=o(n2/3). We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree-polynomials model. 
    more » « less