Search

The scale and capabilities of single-cell RNA-sequencing methods have expanded rapidly in recent years, enabling major discoveries and large-scale cell mapping efforts. However, these methods have not been systematically and comprehensively benchmarked. Here, we directly compare seven methods for single-cell and/or single-nucleus profiling-selecting representative methods based on their usage and our expertise and resources to prepare libraries-including two low-throughput and five high-throughput methods. We tested the methods on three types of samples: cell lines, peripheral blood mononuclear cells and brain tissue, generating 36 libraries in six separate experiments in a single center. To directly compare the methods and avoid processing differences introduced by the existing pipelines, we developed scumi, a flexible computational pipeline that can be used with any single-cell RNA-sequencing method. We evaluated the methods for both basic performance, such as the structure and alignment of reads, sensitivity and extent of multiplets, and for their ability to recover known biological information in the samples.

Passive gamma spectroscopy has been successfully used for nuclear warhead inspection systems based on the template-matching approach. The most prominent example of such a system is Sandia’s Trusted...

Williams syndrome (WS) is a multisystem neurodevelopmental disorder caused by a de novo hemizygous deletion of ~26 genes from chromosome 7q11.23, among them the general transcription factor II-I (GTF2I). By studying a novel murine model for the hypersociability phenotype associated with WS, we previously revealed surprising aberrations in myelination and cell differentiation properties in the cortices of mutant mice compared to controls. These mutant mice had selective deletion of Gtf2i in the excitatory neurons of the forebrain. Here, we applied diffusion magnetic resonance imaging and fiber tracking, which showed a reduction in the number of streamlines in limbic outputs such as the fimbria/fornix fibers and the stria terminalis, as well as the corpus callosum of these mutant mice compared to controls. Furthermore, we utilized next-generation sequencing (NGS) analysis of cortical small RNAs’ expression (RNA-Seq) levels to identify altered expression of microRNAs (miRNAs), including two from the miR-34 cluster, known to be involved in prominent processes in the developing nervous system. Luciferase reporter assay confirmed the direct binding of miR-34c-5p to the 3’UTR of PTPRU—a gene involved in neural development that was elevated in the cortices of mutant mice relative to controls. Moreover, we found an age-dependent variation in the expression levels of doublecortin (Dcx)—a verified miR-34 target. Thus, we demonstrate the substantial effect a single gene deletion can exert on miRNA regulation and brain structure, and advance our understanding and, hopefully, treatment of WS.

Williams syndrome is a neurodevelopmental disorder characterized by hypersociability and unique neurocognitive abnormalities. One of the characteristics of Williams syndrome is an inappropriate increase in social behavior. People with the syndrome may be overly friendly, even to strangers. We performed a novel study in our lab that demonstrated that the lack of a gene called Gtf2i may play a role in Williams syndrome. When this gene is absent, there are changes to one of the most important brain components for transferring signals in the brain and are likely to contribute to the over-friendliness observed in Williams syndrome. We expose surprising mechanisms involved in an increased social behavior, which is one of the characteristics of Williams Syndrome. In this article, we demonstrate how drugs can compensate for the damaged part of the brain and can bring the increased friendly behavior down to a normal level.

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) "characterized" by a low-degree sum-of-squares proof. Our results are obtained by rounding \emph{low-entropy} solutions -- measured via a new global potential function -- to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for \emph{worst-case} optimization problems. As corollaries, we obtain the first polynomial-time algorithms for solving any UG instance where the constraint graph is either the \emph{noisy hypercube}, the \emph{short code} or the \emph{Johnson} graph. The prior best algorithm for such instances was the eigenvalue enumeration algorithm of Arora, Barak, and Steurer (2010) which requires quasi-polynomial time for the noisy hypercube and nearly-exponential time for the short code and Johnson graphs. All of our results achieve an approximation of $1-\epsilon$ vs $\delta$ for UG instances, where $\epsilon>0$ and $\delta > 0$ depend on the expansion parameters of the graph but are independent of the alphabet size., Comment: To appear in STOC 2021

An amendment to this paper has been published and can be accessed via a link at the top of the paper.

Key points There are two electrophysiological dichotomous populations of parvalbumin (PV) interneurons located in the dorsal striatum. Striatal PV interneurons in medial and lateral regions differ significantly in their intrinsic excitability. Parvalbumin interneurons in the dorsomedial striatum, but not in the dorsolateral striatum, receive afferent glutamatergic input from cingulate cortex. Abstract Dorsomedial striatum circuitry is involved in goal-directed actions or movements that become habits upon repetition, as encoded by the dorsolateral striatum. An inability to shift from habits can compromise action-control and prevent behavioural adaptation. Although these regions appear to be clearly behaviourally distinct, little is known about their distinct physiology. Parvalbumin (PV) interneurons are a major source of striatal inhibition and are usually considered as a homogeneous population in the entire dorsal striatum. In the present study, we recorded PV interneurons in dorsal striatum slices from wild-type male mice and suggest the existence of two electrophysiological dichotomous populations. We found that PV interneurons located at the dorsomedial striatum region have increased intrinsic excitability compared to PV interneurons in dorsolateral region. We also found that PV interneurons in the dorsomedial region, but not in the dorsolateral striatum region, receive short-latency excitatory inputs from cingulate cortex. Therefore, the results of the present study demonstrate the importance of considering region specific parvalbumin interneuron populations when studying dorsal striatal function.

Quantum computing combines great promise with daunting challenges — the road to devices that solve real-world problems is still long. Now, an implementation of a quantum algorithm maps the problems we want to solve to the devices we already have.

Visual Abstract, In the central and peripheral nervous systems, the myelin sheath promotes neuronal signal transduction. The thickness of the myelin sheath changes during development and in disease conditions like multiple sclerosis. Such changes are routinely detected using electron microscopy through g-ratio quantification. While g-ratio is one of the most critical measurements in myelin studies, a major drawback is that g-ratio quantification is extremely laborious and time-consuming. Here, we report the development and validation of MyelTracer, an installable, stand-alone software for semi-automated g-ratio quantification based on the Open Computer Vision Library (OpenCV). Compared with manual g-ratio quantification, using MyelTracer produces consistent results across multiple tissues and animal ages, as well as in remyelination after optic nerve crush, and reduces total quantification time by 40–60%. With g-ratio measurements via MyelTracer, a known hypomyelination phenotype can be detected in a Williams syndrome mouse model. MyelTracer is easy to use and freely available for Windows and Mac OS X (https://github.com/HarrisonAllen/MyelTracer).

A multitude of single-cell RNA sequencing methods have been developed in recent years, with dramatic advances in scale and power, and enabling major discoveries and large scale cell mapping efforts. However, these methods have not been systematically and comprehensively benchmarked. Here, we directly compare seven methods for single cell and/or single nucleus profiling from three types of samples – cell lines, peripheral blood mononuclear cells and brain tissue – generating 36 libraries in six separate experiments in a single center. To analyze these datasets, we developed and applied scumi, a flexible computational pipeline that can be used for any scRNA-seq method. We evaluated the methods for both basic performance and for their ability to recover known biological information in the samples. Our study will help guide experiments with the methods in this study as well as serve as a benchmark for future studies and for computational algorithm development.

The scale and capabilities of single-cell RNA-sequencing methods have expanded rapidly in recent years, enabling major discoveries and large-scale cell mapping efforts. However, these methods have not been systematically and comprehensively benchmarked. Here, we directly compare seven methods for single-cell and/or single-nucleus profiling-selecting representative methods based on their usage and our expertise and resources to prepare libraries-including two low-throughput and five high-throughput methods. We tested the methods on three types of samples: cell lines, peripheral blood mononuclear cells and brain tissue, generating 36 libraries in six separate experiments in a single center. To directly compare the methods and avoid processing differences introduced by the existing pipelines, we developed scumi, a flexible computational pipeline that can be used with any single-cell RNA-sequencing method. We evaluated the methods for both basic performance, such as the structure and alignment of reads, sensitivity and extent of multiplets, and for their ability to recover known biological information in the samples.

Optogenetics is among the most widely employed techniques to manipulate neuronal activity. However, a major drawback is the need for invasive implantation of optical fibers. To develop a minimally invasive optogenetic method that overcomes this challenge, we engineered SOUL, a new step-function opsin with ultra-high light sensitivity. We show that SOUL can activate neurons located in deep mouse brain regions via transcranial optical stimulation and elicit behavioral changes in SOUL knock-in mice. Moreover, SOUL can be used to modulate neuronal spiking and induce oscillations reversibly in macaque cortex via optical stimulation from outside the dura. By enabling external light delivery, our new opsin offers a minimally invasive tool for manipulating neuronal activity in rodent and primate models with fewer limitations on the depth and size of target brain regions, and may further facilitate the development of minimally invasive optogenetic tools for the treatment of neurological disorders.

I survey some of the recent progress on software obfuscation spurred by the exciting paper of Garg, Gentry, Halevi, Raykova, Sahai and Waters [GGH13]. This is a preprint version of a review article [Bar16] appearing in the Communications of the ACM. That article was written for a general computing audience, and is also not up to date on the latest research in this fast-moving field since it was mostly written in 2014. Nevertheless, I thought it might still be of interest to cryptographers. Computer programs are arguably the most complex objects ever constructed by humans. Even understanding a 10-line program such as the one depicted in Figure 1 can be extremely difficult. The complexity of programs has been the bane (as well as the boon) of the software industry, and taming it has been the objective of many efforts in industry and academia. Given this, it is not surprising that both theoreticians and practitioners have been trying to “harness this complexity for good” and use it to protect sensitive information and computation. In its most general form this is known as software obfuscation, and it is the topic of this survey. In a certain sense, any cryptographic tool such as encryption or authentication can be thought of harnessing complexity for security, but with software obfuscation people have been aiming for something far more ambitious: a way to transform arbitrary programs into an “inscrutable” or obfuscated form. By this we don’t mean that reverse engineering the program should be cumbersome but rather that it should be infeasible, in the same way that recovering the plaintext of a secure encryption cannot be performed using any reasonable amount of resources. ∗Harvard John A. Paulson School of Engineering and Applied Sciences, b@boazbarak.org. This article was written while the author was at Microsoft Research

Edge networks connected to the Internet need effective monitoring techniques to inform routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. Here, we design and analyze a lightweight path-quality monitoring protocol that reliably raises an alarm when the packet-loss rate exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets. Our protocol is based on sublinear algorithms for sketching the second moment of stream of items and can monitor billions of packets using only 250--600 B of storage and the periodic transmission of a comparably sized IP packet. We also show how this protocol can be used to construct a more sophisticated protocol that allows the sender to localize the link responsible for the dropped packets. We prove that our protocols satisfy a precise definition of security, analyze their performance using numerical experiments, and derive analytic expressions for the tradeoff between statistical accuracy and system overhead. This paper contains a deeper treatment of results from earlier conference papers and several new results.

© 2020 Elsevier Inc. Optogenetics is among the most widely employed techniques to manipulate neuronal activity. However, a major drawback is the need for invasive implantation of optical fibers. To develop a minimally invasive optogenetic method that overcomes this challenge, we engineered a new step-function opsin with ultra-high light sensitivity (SOUL). We show that SOUL can activate neurons located in deep mouse brain regions via transcranial optical stimulation and elicit behavioral changes in SOUL knock-in mice. Moreover, SOUL can be used to modulate neuronal spiking and induce oscillations reversibly in macaque cortex via optical stimulation from outside the dura. By enabling external light delivery, our new opsin offers a minimally invasive tool for manipulating neuronal activity in rodent and primate models with fewer limitations on the depth and size of target brain regions and may further facilitate the development of minimally invasive optogenetic tools for the treatment of neurological disorders.

An m output pseudorandom generator \(\mathcal {G}:(\{\pm 1\}^b)^n \rightarrow \{\pm 1\}^m\) that takes input n blocks of b bits each is said to be \(\ell \)-block local if every output is a function of at most \(\ell \) blocks. We show that such \(\ell \)-block local pseudorandom generators can have output length at most \(\tilde{O}(2^{\ell b} n^{\lceil \ell /2 \rceil })\), by presenting a polynomial time algorithm that distinguishes inputs of the form \(\mathcal {G}(x)\) from inputs where each coordinate is sampled from the uniform distribution on m bits.

Mutation in the SHANK3 human gene leads to different neuropsychiatric diseases including Autism Spectrum Disorder (ASD), intellectual disabilities and Phelan-McDermid syndrome. Shank3 disruption in mice leads to dysfunction of synaptic transmission, behavior, and development. Protein S-nitrosylation, the nitric oxide (NO•)-mediated posttranslational modification (PTM) of cysteine thiols (SNO), modulates the activity of proteins that regulate key signaling pathways. We tested the hypothesis that Shank3 mutation would generate downstream effects on PTM of critical proteins that lead to modification of synaptic functions. SNO-proteins in two ASD-related brain regions, cortex and striatum of young and adult InsG3680(+/+) mice (a human mutation-based Shank3 mouse model), were identified by an innovative mass spectrometric method, SNOTRAP. We found changes of the SNO-proteome in the mutant compared to WT in both ages. Pathway analysis showed enrichment of processes affected in ASD. SNO-Calcineurin in mutant led to a significant increase of phosphorylated Synapsin1 and CREB, which affect synaptic vesicle mobilization and gene transcription, respectively. A significant increase of 3-nitrotyrosine was found in the cortical regions of the adult mutant, signaling both oxidative and nitrosative stress. Neuronal NO• Synthase (nNOS) was examined for levels and localization in neurons and no significant difference was found in WT vs. mutant. S-nitrosoglutathione concentrations were higher in mutant mice compared to WT. This is the first study on NO•-related molecular changes and SNO-signaling in the brain of an ASD mouse model that allows the characterization and identification of key proteins, cellular pathways, and neurobiological mechanisms that might be affected in ASD., Army Research Office Institute for Collaborative Biotechnologies (Grant W911NF-09-0001)

For every $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}/\epsilon^2))$-time algorithm for the $1$ vs $1-\epsilon$ \emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2\times n^2$ matrix $\mathcal{M}$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $\mathcal{M}$ accepts with probability $1$, and the case that every separable state is accepted with probability at most $1-\epsilon$. Equivalently, our algorithm takes the description of a subspace $\mathcal{W} \subseteq \mathbb{F}^{n^2}$ (where $\mathbb{F}$ can be either the real or complex field) and distinguishes between the case that $\mathcal{W}$ contains a rank one matrix, and the case that every rank one matrix is at least $\epsilon$ far (in $\ell_2$ distance) from $\mathcal{W}$. To the best of our knowledge, this is the first improvement over the brute-force $\exp(n)$-time algorithm for this problem. Our algorithm is based on the \emph{sum-of-squares} hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank-$n$ Boolean matrix is bounded by $\tilde{O}(\sqrt{n})$., Comment: 23 pages + 1 title-page + 1 table-of-contents

The association between cardiovascular fitness and cognitive functions in both animals and humans is intensely studied. Research in rodents shows that a higher cardiovascular fitness has beneficial effects on hippocampus-dependent spatial abilities, and the underlying mechanisms were largely teased out. Research into the impact of cardiovascular fitness on spatial learning in humans, however, is more limited, and involves mostly behavioral and imaging studies. Herein, we point out the state of the art in the field of spatial learning and cardiovascular fitness. The differences between the methodologies utilized to study spatial learning in humans and rodents are emphasized along with the neuronal basis of these tasks. Critical gaps in the study of spatial learning in the context of cardiovascular fitness between the two species are discussed.

The verification of nuclear warheads for arms control involves a paradox: international inspectors will have to gain high confidence in the authenticity of submitted items while learning nothing about them. Proposed inspection systems featuring 'information barriers', designed to hide measurements stored in electronic systems, are at risk of tampering and snooping. Here we show the viability of a fundamentally new approach to nuclear warhead verification that incorporates a zero-knowledge protocol, which is designed in such a way that sensitive information is never measured and so does not need to be hidden. We interrogate submitted items with energetic neutrons, making, in effect, differential measurements of both neutron transmission and emission. Calculations for scenarios in which material is diverted from a test object show that a high degree of discrimination can be achieved while revealing zero information. Our ideas for a physical zero-knowledge system could have applications beyond the context of nuclear disarmament. The proposed technique suggests a way to perform comparisons or computations on personal or confidential data without measuring the data in the first place.

Multiple hypothalamic neuronal populations that regulate energy balance have been identified. Although hypothalamic glia exist in abundance and form intimate structural connections with neurons, their roles in energy homeostasis are less known. Here we show that selective Ca[superscript 2+] activation of glia in the mouse arcuate nucleus (ARC) reversibly induces increased food intake while disruption of Ca[superscript 2+] signaling pathway in ARC glia reduces food intake. The specific activation of ARC glia enhances the activity of agouti-related protein/neuropeptide Y (AgRP/NPY)-expressing neurons but induces no net response in pro-opiomelanocortin (POMC)-expressing neurons. ARC glial activation non-specifically depolarizes both AgRP/NPY and POMC neurons but a strong inhibitory input to POMC neurons balances the excitation. When AgRP/NPY neurons are inactivated, ARC glial activation fails to evoke any significant changes in food intake. Collectively, these results reveal an important role of ARC glia in the regulation of energy homeostasis through its interaction with distinct neuronal subtype-specific pathways., Massachusetts Institute of Technology. Poitras Center for Affective Disorders Research, Singapore. Agency for Science, Technology and Research, National Institutes of Health (U.S.) (R01EY007023), National Institutes of Health (U.S.) (R01EY018648), National Institutes of Health (U.S.) (U01NS090473), National Science Foundation (U.S.) (EF1451125), Simons Foundation, Massachusetts Institute of Technology. Simons Center for the Social Brain, Autism Science Foundation

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$. This yields a nearly tight $n^{1/2 - o(1)}$ bound on the value of this program for any degree $d = o(\log n)$. Moreover we introduce a new framework that we call \emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others., Comment: 55 pages

The main result of this paper is an explicit disperser for two independent sources on n bits, each of min-entropy k = 2 1−α0 , for some small absolute constant α0 > 0). Put differently, setting N = 2 and K = 2, we construct an explicit N ×N Boolean matrix for which no K ×K sub-matrix is monochromatic. Viewed as the adjacency matrix of a bipartite graph, this gives an explicit construction of a bipartite K-Ramsey graph of 2N vertices. This improves the previous the previous bound of k = o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson [BKS05]. As a corollary, we get a construction of a 2 log1−α0 n (non bipartite) Ramsey graph of 2 vertices, significantly improving the previous bound of 2O √ n) due to Frankl and Wilson [FW81]. We also give a construction of a new independent sources extractor that can extract from a constant number of sources of polynomially small min-entropy with exponentially small error. This improves independent sources extractor of Rao [Rao06], which only achieved polynomially small error. Our dispersers combine ideas and constructions from several previous works in the area together with some new ideas. In particular, we rely on the extractors of Raz [Raz05] and Bourgain [Bou05] as well as an improved version of the extractor of Rao [Rao06]. A key ingredient that allows us to beat the barrier of k = √ n is a new and more complicated variant of the challenge-response mechanism of Barak et al. [BKS05] that allows us to locate the min-entropy concentrations in a source of low min-entropy.

We prove fractional analogs of the classical Sylvester–Gallai theorem. Our theorems translate local information about collinear triples in a set of points into global bounds on the dimension of the set. Specifically, we show that if for every points v in a finite set , there are at least δ| V | other points u ∈ V for which the line through v , u contains a third point in V , then the V resides in a (13/δ 2 )-dimensional affine subspace of . This result, which is one of several variants we study, is motivated by questions in theoretical computer science and, in particular, from the area of error correcting codes. Our proofs combine algebraic, analytic, and combinatorial arguments. A key ingredient is a new lower bound for the rank of design matrices, specified only by conditions on their zero/non-zero pattern.

Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O ( P ) that has the same functionality as P yet is “unintelligible” in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the “unintelligibility” condition in obfuscation as meaning that O ( P ) is a “virtual black box,” in the sense that anything one can efficiently compute given O ( P ), one could also efficiently compute given oracle access to P . In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of efficient programs P that are unobfuscatable in the sense that (a) given any efficient program P ' that computes the same function as a program P ∈ p , the “source code” P can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program P ∈ p , no efficient algorithm can reconstruct P (or even distinguish a certain bit in the code from random) except with negligible probability. We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation ( TC 0 ). We also rule out several potential applications of obfuscators, by constructing “unobfuscatable” signature schemes, encryption schemes, and pseudorandom function families.

This paper introduces notions from computational complexity into the study of financial derivatives. Traditional economics argues that derivatives, like CDOs and CDSs, ameliorate the negative costs imposed due to asymmetric information between buyers and sellers. This is because securitization via these derivatives allows the informed party to find buyers for the information-insensitive part of the cash flow stream of an asset (e.g., a mortgage) and retain the remainder. In this paper we show that this viewpoint may need to be revised once computational complexity is brought into the picture. Assuming reasonable complexity-theoretic conjectures, we show that derivatives can actually amplify the costs of asymmetric information instead of reducing them. We prove our results both in the worst-case setting, as well as the more realistic average case setting. In the latter case, to argue that our constructions result in derivatives that “look like” real-life derivatives, we use the notion of computational indistinguishability a la cryptography.

Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where all messages sent by the parties may be tampered with and modified by the adversary without the uncorrupted parties being able to detect this fact. In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees can be provided: Essentially, all the adversary can do is to partition the network into disjoint sets, where in each set the computation is secure in of itself, and also independent of the computation in the other sets. In this setting we provide, for the first time, nontrivial security guarantees in a model with no setup assumptions whatsoever. We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and nonmalleable commitments. As an application of our results, we study the question of constructing secure protocols in partially authenticated networks, where some of the links are authenticated, and some are not (as is the case in most networks today).

We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. We say that a distribution X on binary strings of length n is a δ-source if X assigns probability at most 2 −δ n to any string of length n . For every δ>0, we construct the following poly( n )-time computable functions: 2-source disperser: D:({0, 1} n ) 2 → {0, 1} such that for any two independent δ-sources X 1 , X 2 we have that the support of D ( X 1 , X 2 ) is {0, 1}. Bipartite Ramsey graph: Let N =2 n . A corollary is that the function D is a 2-coloring of the edges of K N,N (the complete bipartite graph over two sets of N vertices) such that any induced subgraph of size N δ by N δ is not monochromatic. 3-source extractor: E :({0, 1} n ) 3 → {0, 1} such that for any three independent δ-sources X 1 , X 2 , X 3 we have that E ( X 1 , X 2 , X 3 ) is o (1)-close to being an unbiased random bit. No previous explicit construction was known for either of these for any δ A component in these results is a new construction of condensers that may be of independent interest: This is a function C :{0, 1} n → ({0, 1} n/c ) d (where c and d are constants that depend only on δ) such that for every δ-source X one of the output blocks of C(X) is (exponentially close to) a 0.9-source. (This result was obtained independently by Ran Raz.) The constructions are quite involved and use as building blocks other new and known objects. A recurring theme in these constructions is that objects that were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The construction of the disperser is based on a new technique which we call “the challenge-response mechanism” that (in some sense) allows “identifying high entropy regions” in a given pair of sources using only one sample from the two sources.

Priming is the process by which vesicles become available for fusion at nerve terminals and it is modulated by numerous proteins and second messengers. One of the prominent members of this diverse family is Tomosyn. Tomosyn has been identified as a Syntaxin-binding protein; it inhibits vesicle priming, but its mode of action is not fully understood. Tomosyn's inhibitory activity depends on its N-terminal WD40-repeat domain and is regulated by the binding of its SNARE-motif to Syntaxin. The present review describes new physiological information on Tomosyn's function and addresses possible interpretations of these results in the framework of the recently described crystal structure of the yeast Tomosyn homolog Sro7. We also present possible molecular scenarios for vesicle priming and the involvement of Tomosyn in these processes.

We give two applications of Nisan-Wigderson-type (NW-type) (“noncryptographic”) pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct the following two protocols: (1) a one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an “NP proof system.” (2) a noninteractive bit-commitment scheme based on any one-way function. The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if $E = DTIME(2^{O(n)})$ has a function of nondeterministic circuit complexity $2^{\Omega(n)}$. Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor [Proceedings of the 41st Annual ACM Symposium on Foundations of Computer Science, 2000, pp. 283-293]. To our knowledge, this is the first construction of an NP proof system achieving a secrecy property. Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor [J. Cryptology, 4 (1991), pp. 151-158]. Previous constructions of noninteractive commitment schemes were known only under incomparable assumptions.

Genetic studies have revealed significant overlaps of risk genes among psychiatric disorders. However, it is not clear how different mutations of the same gene contribute to different disorders. We characterized two lines of mutant mice with Shank3 mutations linked to ASD and schizophrenia. We found both shared and distinct synaptic and behavioral phenotypes. Mice with the ASD-linked InsG3680 mutatio n manifest striatal synaptic transmission defects before weaning age and impaired juvenile social interaction, coinciding with the early onset of ASD symptoms. On the other hand, adult mice carrying the schizophrenia-linked R1117X mutation show profound synaptic defects in prefrontal cortex and social dominance behavior. Furthermore, we found differential Shank3 mRNA stability and SHANK1/2 upregulation in these two lines. These data demonstrate that different alleles of the same gene may have distinct phenotypes at molecular, synaptic, and circuit levels in mice, which may inform exploration of these relationships in human patients., National Institute of Mental Health (U.S.) (Grant 5R01MH097104), National Institute of Mental Health (U.S.) (Grant 5DP1-MH100706), National Institutes of Health (U.S.) (Grant R01-NS 07312401)

Neurogenesis, the process of generating new neurons in the brain, fascinates researchers for its promise to affect multiple cognitive and functional processes in both health and disease. Many cellular pathways are involved in the regulation of neurogenesis, a complexity exemplified by the extensive regulation of this process during brain development. Toll-like receptors (TLRs), hallmarks of innate immunity, are increasingly implemented in various central nervous system plasticity-related processes including neurogenesis. As TLRs are involved in neurodegenerative disorders, understanding the involvement of TLRs in neurogenesis may hold keys for future therapeutic interventions. Herein, we describe the current knowledge on the involvement of TLRs in neurogenesis and neuronal plasticity and point to current knowledge gaps in the field.

We give a new approach to the dictionary learning (also known as “sparse coding”) problem of recovering an unknown n × m matrix A (for m ≥ n) from examples of the form [y = Ax + e], where x is a random vector in R[superscript m] with at most τ m nonzero coordinates, and e is a random noise vector in R[superscript n] with bounded magnitude. For the case m = O(n), our algorithm recovers every column of A within arbitrarily good constant accuracy in time m[superscript O(log m/log(τ[superscript −1]))], in particular achieving polynomial time if τ = m[superscript −δ] for any δ > 0, and time m[superscript O(log m)] if τ is (a sufficiently small) constant. Prior algorithms with comparable assumptions on the distribution required the vector x to be much sparser—at most √n nonzero coordinates—and there were intrinsic barriers preventing these algorithms from applying for denser x. We achieve this by designing an algorithm for noisy tensor decomposition that can recover, under quite general conditions, an approximate rank-one decomposition of a tensor T, given access to a tensor T[supserscript ′] that is τ-close to T in the spectral norm (when considered as a matrix). To our knowledge, this is the first algorithm for tensor decomposition that works in the constant spectral-norm noise regime, where there is no guarantee that the local optima of T and T[superscript ′] have similar structures. Our algorithm is based on a novel approach to using and analyzing the Sum of Squares semidefinite programming hierarchy (Parrilo 2000, Lasserre 2001), and it can be viewed as an indication of the utility of this very general and powerful tool for unsupervised learning problems., National Science Foundation (U.S.) (grant 1111109)