We show the following hardness results for monotone learning and approximation of monotone circuit size: 1) Under the Randomised Exponential-Time Hypothesis (rETH), it requires time n^{Ω(log n)} to PAC-learn monotone formulas with n input bits and size s(n) = n by monotone circuits of size n^{(log n)^{1-ε}}, for every ε > 0. 2) Under the Randomised Exponential-Time Hypothesis (rETH), for any δ > 0, there is a polynomially bounded function m such that m^{1-δ}-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of m(n) labelled examples {(x_i, b_i)} over n-bit inputs requires time m^{Ω(log(m))}. Our results are shown by a novel application of lifting arguments in proof and communication complexity to hardness of monotone learning, by building on the seminal result of Atserias and Müller [Atserias and Müller, 2020] on hardness of automating Resolution proofs.

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.

Abstract We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $${\rm TC}^0$$ TC 0 -Frege. This extends the line of results of Krajííček and Pudlík( Information and Computation , 1998), Bonet, Pitassi, and Raz ( SIAM Journal on Computing , 2000),and Bonet, Domingo, Gavaldá, Maciel, and Pitassi ( Computational Complexity, 2004 ), who showed that ExtendedFrege, $${\rm TC}^0$$ TC 0 -Frege and $${\rm AC}^0$$ AC 0 -Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.

The complexity class CLS was introduced by Daskalakis and Papadimitriou (SODA 2010) to capture the computational complexity of important TFNP problems solvable by local search over continuous domains and, thus, lying in both PLS and PPAD. It was later shown that, e.g., the problem of computing fixed points guaranteed by Banach’s fixed point theorem is CLS-complete by Daskalakis et al. (STOC 2018). Recently, Fearnley et al. (J. ACM 2023) disproved the plausible conjecture of Daskalakis and Papadimitriou that CLS is a proper subclass of PLS∩PPAD by proving that CLS = PLS∩PPAD. To study the possibility of other collapses in TFNP, we connect classes formed as the intersection of existing subclasses of TFNP with the phenomenon of feasible disjunction in propositional proof complexity; where a proof system has the feasible disjunction property if, whenever a disjunction F ∨ G has a small proof, and F and G have no variables in common, then either F or G has a small proof. Based on some known and some new results about feasible disjunction, we separate the classes formed by intersecting the classical subclasses PLS, PPA, PPAD, PPADS, PPP and CLS. We also give the first examples of proof systems which have the feasible interpolation property, but not the feasible disjunction property.

Emissions from fossil fuel power plants are a major contributor to climate change. Directly measuring emissions at the source is cost-prohibitive throughout most of the world, while self-reporting varies widely in detail, recency, and spatiotemporal resolution. We use machine learning to infer power generation and carbon dioxide (CO2) emissions from proxy signals in multi-spectral satellite imagery, including Landsat 8, Sentinel-2, and PlanetScope. We built and evaluated classification models to predict plant on/off status and regression models to predict generation. By training on a data set of power plants for which we know the generation, we are able to apply our models globally with higher spatial and temporal precision than alternative approaches, producing a scalable and consistent approach to estimate CO2emissions.

In this video, real-life acting professor Matthew Gray tutors Data the Robot (a Nao model) to improve his expression of emotion via Chekhov's Psychological Gestures. Though the video narrative is fictional and the robot actions pre-programmed, the aim of the dramatization is to introduce an acting methodology that social robots could use to leverage full body affect expressions.