Search

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.

Microglia are the immune cells of the brain, involved in synapse formation, circuit sculpting, myelination, plasticity, and cognition. Being active players during early development as well as in adulthood, microglia affect other cells directly by their long processes and unique receptors and indirectly by secreting growth factors and cytokines. In this review, we discuss the roles of microglia in neurodevelopmental disorders, synaptic plasticity, myelination, and homeostatic conditions throughout human and mouse development. Within these processes, we specifically focus on the contribution of altered microglial interactions with neurons and oligodendrocytes, altered cytokine and growth factor activities, and alterations in the complement system. We conclude by highlighting future perspectives and providing an overview of future research on microglia.

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.

We prove that every key agreement protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary who makes \(O(n^2)\) queries to the oracle. This improves on the previous \({\tilde{\Omega }}(n^6)\) query attack given by Impagliazzo and Rudich (STOC ’89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with n queries to a random oracle and cannot be broken by any adversary who asks \(o(n^2)\) queries.

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.

Williams syndrome (WS), caused by a heterozygous microdeletion on chromosome 7q11.23, is a neurodevelopmental disorder characterized by hypersociability and neurocognitive abnormalities. Of the deleted genes, general transcription factor IIi (Gtf2i) has been linked to hypersociability in WS, although the underlying mechanisms are poorly understood. We show that selective deletion of Gtf2i in the excitatory neurons of the forebrain caused neuroanatomical defects, fine motor deficits, increased sociability and anxiety. Unexpectedly, 70% of the genes with significantly decreased messenger RNA levels in the mutant mouse cortex are involved in myelination, and mutant mice had reduced mature oligodendrocyte cell numbers, reduced myelin thickness and impaired axonal conductivity. Restoring myelination properties with clemastine or increasing axonal conductivity rescued the behavioral deficits. The frontal cortex from patients with WS similarly showed reduced myelin thickness, mature oligodendrocyte cell numbers and mRNA levels of myelination-related genes. Our study provides molecular and cellular evidence for myelination deficits in WS linked to neuronal deletion of Gtf2i.

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.

Streams provide a variety of ecosystem and recreational services. Several studies have documented that the public often has a strong willingness to pay for stream restoration, however, many do not distinguish between the values for different types of uses of restored streams. Given that stream restoration can include a variety of actions both instream and along streambanks, which differ widely in terms of cost, it is important to distinguish between such benefits. Taking Israel as a case study, this paper uses an approach based on respondents’ willingness to allocate tax monies in a choice modeling framework to evaluate the relative priorities that the public assigns to instream versus land-based uses of stream areas. In Israel, some rehabilitation of streambanks and riparian areas has occurred, but much less progress has been made on instream improvements, which would demand allocation of water, a scarce and pricey resource in the region. Respondents indicated a slight preference for land-based uses. Greater familiarity with streams was associated with higher utility from land uses. This indicates that less costly rehabilitation of land along stream banks is a reasonable first step for policymakers to take, before attempting more costly efforts requiring allocation of instream flows.

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

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for publickey encryption schemes, and the types of evidence we have for the veracity of these assumptions.

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.

The presence of infrastructure on and around the coastline affects the utility of visitors to the beach. The research examines this impact with the goals to: 1.) assist policy makers in determining the optimal level of coastline development; and 2.) determine the public's view of adequate compensation for the perceived utility loss from the presence of infrastructure. The model uses a discrete choice analysis of varying scenarios for beach conditions (e.g., water and sand quality, crowdedness of the beach) and presence of infrastructure, such as ports, hotels, and marinas. Willingness to pay to visit a beach in Israel with infrastructure facilities nearby was found to be 10 USD less than that of beaches in their natural state. Results reflect expected outcomes: the public prefers natural settings, followed by preference for hotels, marinas, and ports, respectively. Results showed that water quality has the highest impact on utility levels, in fact twice as impactful as sand quality, followed by the extent of beach crowdedness. Surprisingly, people are willing to pay higher prices for clean water when beaches are in proximity to ports and factories. Ports and factories were found to create a more significant degree of fear of harm to water quality in comparison to marinas, restaurants and hotels. The study demonstrates that public trust of environmental quality is monetarily measurable and has a noticeable effect on people's choices for beach selection.

We describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~O(√CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~O(I) bits of communication.These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. For average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. If μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of nevaluations of f, and obtain results analogous to those above.

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.

The use of artificial, prepatterned neuronal networks in vitro is a promising approach for studying the development and dynamics of small neural systems in order to understand the basic functionality of neurons and later on of the brain. The present work presents a high fidelity and robust procedure for controlling neuronal growth on substrates such as silicon wafers and glass, enabling us to obtain mature and durable neural networks of individual cells at designed geometries. It offers several advantages compared to other related techniques that have been reported in recent years mainly because of its high yield and reproducibility. The procedure is based on surface chemistry that allows the formation of functional, tailormade neural architectures with a micrometer high-resolution partition, that has the ability to promote or repel cells attachment. The main achievements of this work are deemed to be the creation of a large scale neuronal network at low density down to individual cells, that develop intact typical neurites and synapses without any glia-supportive cells straight from the plating stage and with a relatively long term survival rate, up to 4 weeks. An important application of this method is its use on 3D nanopillars and 3D nanowire-device arrays, enabling not only the cell bodies, but also their neurites to be positioned directly on electrical devices and grow with registration to the recording elements underneath. Refereed/Peer-reviewed

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)

Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption.

A hallmark of Huntington's disease is the pronounced sensitivity of striatal neurons to polyglutamine-expanded huntingtin expression. Here we show that cultured striatal cells and murine brain striatum have remarkably low levels of phosphorylation of translation initiation factor eIF2 alpha, a stress-induced process that interferes with general protein synthesis and also induces differential translation of pro-apoptotic factors. EIF2 alpha phosphorylation was elevated in a striatal cell line stably expressing pathogenic huntingtin, as well as in brain sections of Huntington's disease model mice. Pathogenic huntingtin caused endoplasmic reticulum (ER) stress and increased eIF2 alpha phosphorylation by increasing the activity of PKR-like ER-localized eIF2 alpha kinase (PERK). Importantly, striatal neurons exhibited special sensitivity to ER stress-inducing agents, which was potentiated by pathogenic huntingtin. We could strongly reduce huntingtin toxicity by inhibiting PERK. Therefore, alteration of protein homeostasis and eIF2 alpha phosphorylation status by pathogenic huntingtin appears to be an important cause of striatal cell death. A dephosphorylated state of eIF2 alpha has been linked to cognition, which suggests that the effect of pathogenic huntingtin might also be a source of the early cognitive impairment seen in patients.

An evasive circuit family is a collection of circuits \(\mathcal{C}\) such that for every input x, a random circuit from \(\mathcal{C}\) outputs 0 on x with overwhelming probability. We provide a combination of definitional, constructive, and impossibility results regarding obfuscation for evasive functions

Synaptic transmission relies on spatially and temporally coordinated multistep processes that allow neuronal communication; activity-dependent changes in synaptic transmission underlie synaptic plasticity. These processes are coordinated by a large number of specific proteins whose dynamic interactions, expression, and regulation define the efficacy of transmission and the mode of synaptic plasticity. In this chapter, we discuss the molecular mechanisms of some of the basic processes associated with neurotransmission in the presynaptic terminal—vesicle docking, priming, and fusion—elaborate on the contribution of specific proteins to different modes of vesicle recycling, and discuss their nanoscale distribution in the synapses. We also describe the involvement of these proteins in synaptic plasticity and animal behavior, the expression ratios between specific proteins and the possible contribution of these ratios to various modes and kinetics of neurotransmitter release.

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brand��o and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector $v$ in the subspace satisfying $|v|_4^4 > c(k/d^{1/3}) |v|_2^2$, where $|v|_p = (E_i v_i^p)^{1/p}$. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted $��$-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever $��< O(\min(1,n/d^2))$, improving for $d < n^{2/3}$ prior methods which intrinsically required $��< O(1/\sqrt(d))$.

Tomosyn, a syntaxin-binding protein, is known to inhibit vesicle priming and synaptic transmission via interference with the formation of SNARE complexes. Using a lentiviral vector, we specifically overexpressed tomosyn1 in hippocampal dentate gyrus neurons in adult mice. Mice were then subjected to spatial learning and memory tasks and electrophysiological measurements from hippocampal slices. Tomosyn1-overexpression significantly impaired hippocampus-dependent spatial memory while tested in the Morris water maze. Further, tomosyn1-overexpressing mice utilize swimming strategies of lesser cognitive ability in the Morris water maze compared with control mice. Electrophysiological measurements at mossy fiber-CA3 synapses revealed impaired paired-pulse facilitation in the mossy fiber of tomosyn1-overexpressing mice. This study provides evidence for novel roles for tomosyn1 in hippocampus-dependent spatial learning and memory, potentially via decreased synaptic transmission in mossy fiber-CA3 synapses. Moreover, it provides new insight regarding the role of the hippocampal dentate gyrus and mossy fiber-CA3 synapses in swimming strategy preference, and in learning and memory.

This work studies several questions about the optimality of semidefinite programming (SDP) for constraint satisfaction problems (CSPs). First we propose the hypothesis that the well known Basic SDP relaxation is actually optimal for random instances of constraint satisfaction problems for every predicate. This unifies several conjectures proposed in the past, and suggests a unifying principle for the average-case complexity of CSPs. We provide several types of indirect evidence for the truth of this hypothesis, and also show that it (and its variants) imply several conjectures in hardness of approximation including polynomial factor hardness for the densest k subgraph problem and hard instances for the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell (1993).Second, we observe that for every predicate P, the basic SDP relaxation achieves the same approximation guarantee for the CSP for P and for a more general problem (involving not just Boolean but constrained vector assignments), which we call the Generalized CSP for P. Raghavendra (2008) showed that it is UGC-hard to approximate the CSP for P better than this guarantee. We show that it is NP-hard to approximate the Generalized CSP for P better than this guarantee.