Search for: All records

We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can sample distributions that subexponential-size classical circuits cannot approximate even to TV distance $1-o(1)$. Prior work of Aaronson and Arkhipov (2011) showed such a separation for the case of exact sampling (i.e.~TV distance $$0$$), but separations for approximate sampling were only known for uniform algorithms. A key ingredient in our proof is a new hardness amplification lemma for the classical query complexity of the Yamakawa--Zhandry (2022) search problem. We show that the probability that any family of query algorithms collectively finds $$k$$ distinct solutions decays exponentially in $$k$$. 

The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions - even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show that its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded. 

The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a distributional-lifting theorem: This upgrades a learner that succeeds with respect to a limited distribution family \mathcal{D} to one that succeeds with respect to any distribution D^\star, with an efficiency overhead that scales with the complexity of expressing D^\star as a mixture of distributions in \mathcal{D}. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for D^\star, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns D^\star and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn D^\star, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler. 

ABSTRACT The development of vaccines for fungal diseases, including cryptococcosis, is an emergent line of research and development. In previous studies, we showed that aCryptococcusmutant lacking theSGL1gene (∆sgl1) accumulates certain glycolipids called steryl glucosides (SGs) on the fungal capsule, promoting an effective immunostimulation that totally protects the host from a secondary cryptococcal infection. However, this protection is lost when the cryptococcal capsule is absent in the∆sgl1background. The cryptococcal capsule is mainly composed of glucuronoxylomannan (GXM), a polysaccharide microfiber consisting of glucuronic acid, xylose, and mannose linked by glycosidic bonds forming specific triads. In this study, we engineered cells to lack each of the GXM components and tested the effect of these deletions on protection under the condition of SG accumulation. We found that glucuronic acid and xylose are required for protection, and their absence abrogates the production of IFNγ and IL-17A by γδ T cells, which are necessary stimulants for the protective phenotype of the∆sgl1. We analyzed the structure of the GXM microfibers and found that although the deletion ofSGL1only slightly affects the size and distribution of these microfibers, it significantly changes the ratio of mannose to other components. In conclusion, this study identifies the structural modifications that the deletion ofSGL1and the consequent accumulation of SGs impart to the GXM structure ofC. neoformans. This provides significant insights into the protective mechanisms mediated by SG accumulation on the capsule, with important implications for the future development of an efficacious cryptococcal vaccine.IMPORTANCECryptococcus neoformansis an encapsulated fungus that causes invasive fungal infections with high morbidity and mortality in susceptible patients. With increasing drug resistance and high toxicity of current antifungal drugs, there is a need for alternative therapeutic strategies, such as a cryptococcal vaccine. In this study, we identify the necessary capsular components and their structural organization required for a cryptococcal vaccine to protect the host against challenge with a virulent strain. These capsular components are glucuronic acid, xylose, and mannose, and they work together with certain glycolipids called steryl glucosides (SGs) to stimulate host immunity. Interestingly, SGs on the capsule may favor the formation of small capsular microfibers organized in specific mannose triads. Thus, the results of this paper are important because they identify a mechanism by which SGs affect the structure of the cryptococcal capsule, with important implications for the future development of a cryptococcal vaccine using capsular components and SGs. 

We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍D. The efficiency of our transformation scales with the inherent complexity of ‍D, running in (n, (md)d) time for distributions over n whose pmfs are computed by depth-d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍D, and for general ones it uses subcube conditioning samples. A key technical ingredient is an algorithm which, given the aforementioned access to D, produces an optimal decision tree decomposition of D: an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning. 

We give a pseudorandom generator that fools m -facet polytopes over {0, 1} n with seed length polylog( m ) · log n . The previous best seed length had superlinear dependence on m .