Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Better Circuits for Binary Polynomial Multiplication.

ABSTRACT: We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over F2 . We restrict the search of small circuits to a class of circuits we call symmetric bilinear. These are circuits in which AND gates only compute functions of the form ?i?Sai??i?Sbi (S ? {0,…, n - 1}). These techniques yield improved recurrences for M(kn), the number of gates used in a circuit that multiplies two kn-term polynomials, for k = 4, 5, 6, and 7. We built and verified the circuits for n-term binary polynomial multiplication for values of n of practical interest. Circuits for n up to 100 are posted at http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/BinPolMult.tar.gz.

SUBMITTER: Find MG

PROVIDER: S-EPMC6774206 | biostudies-literature | 2019

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Better Circuits for Binary Polynomial Multiplication.

Find Magnus Gaudal MG Peralta René R

IEEE transactions on computers. Institute of Electrical and Electronics Engineers 20190101

We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over F 2 . We restrict the search of small circuits to a class of circuits we call symmetric bilinear. These are circuits in which AND gates only compute functions of the form ∑ i ∈ S a i ⋅ ∑ i ∈ S b i (S ⊆ {0,…, n - 1}). These techniques yield improved recurrences for M(kn), the number of gates used in a circuit that multiplies two k ...[more]

PMID: 31579277

Similar Datasets

Ultra-low-power switching circuits based on a binary pattern generator with spiking neurons.

Project description:Research on various neuro-inspired technologies has received much attention. However, while higher-order neural functions such as recognition have been emphasized, the fundamental properties of neural circuits as advanced control systems have not been fully exploited. Here, we applied the functions of central pattern generators, biological neural circuits for motor control, to the control technology of switching circuits for extremely power-saving terminal edge devices. By simply applying a binary waveform with an arbitrary temporal pattern to the transistor gate, low-power and real-time switching control can be achieved. This binary pattern generator consists of a specially designed spiking neuron circuit that generates spikes after a pre-programmed wait time in the six-order range, but consumes negligible power, with an experimental record of 1.2 pW per neuron. This control scheme has been successfully applied to voltage conversion circuits consuming only a few nanowatts, providing an ultra-low power technology for trillions of self-powered edge systems.

| S-EPMC8782828 | biostudies-literature

The McNemar test for binary matched-pairs data: mid-p and asymptotic are better than exact conditional.

Project description:BackgroundStatistical methods that use the mid-p approach are useful tools to analyze categorical data, particularly for small and moderate sample sizes. Mid-p tests strike a balance between overly conservative exact methods and asymptotic methods that frequently violate the nominal level. Here, we examine a mid-p version of the McNemar exact conditional test for the analysis of paired binomial proportions.MethodsWe compare the type I error rates and power of the mid-p test with those of the asymptotic McNemar test (with and without continuity correction), the McNemar exact conditional test, and an exact unconditional test using complete enumeration. We show how the mid-p test can be calculated using eight standard software packages, including Excel.ResultsThe mid-p test performs well compared with the asymptotic, asymptotic with continuity correction, and exact conditional tests, and almost as good as the vastly more complex exact unconditional test. Even though the mid-p test does not guarantee preservation of the significance level, it did not violate the nominal level in any of the 9595 scenarios considered in this article. It was almost as powerful as the asymptotic test. The exact conditional test and the asymptotic test with continuity correction did not perform well for any of the considered scenarios.ConclusionsThe easy-to-calculate mid-p test is an excellent alternative to the complex exact unconditional test. Both can be recommended for use in any situation. We also recommend the asymptotic test if small but frequent violations of the nominal level is acceptable.

| S-EPMC3716987 | biostudies-literature

Piecewise polynomial representations of genomic tracks.

Project description:Genomic data from micro-array and sequencing projects consist of associations of measured values to chromosomal coordinates. These associations can be thought of as functions in one dimension and can thus be stored, analyzed, and interpreted as piecewise-polynomial curves. We present a general framework for building piecewise polynomial representations of genome-scale signals and illustrate some of its applications via examples. We show that piecewise constant segmentation, a typical step in copy-number analyses, can be carried out within this framework for both array and (DNA) sequencing data offering advantages over existing methods in each case. Higher-order polynomial curves can be used, for example, to detect trends and/or discontinuities in transcription levels from RNA-seq data. We give a concrete application of piecewise linear functions to diagnose and quantify alignment quality at exon borders (splice sites). Our software (source and object code) for building piecewise polynomial models is available at http://sourceforge.net/projects/locsmoc/.

| S-EPMC3499510 | biostudies-literature

Maximal aggregation of polynomial dynamical systems.

Project description:Ordinary differential equations (ODEs) with polynomial derivatives are a fundamental tool for understanding the dynamics of systems across many branches of science, but our ability to gain mechanistic insight and effectively conduct numerical evaluations is critically hindered when dealing with large models. Here we propose an aggregation technique that rests on two notions of equivalence relating ODE variables whenever they have the same solution (backward criterion) or if a self-consistent system can be written for describing the evolution of sums of variables in the same equivalence class (forward criterion). A key feature of our proposal is to encode a polynomial ODE system into a finitary structure akin to a formal chemical reaction network. This enables the development of a discrete algorithm to efficiently compute the largest equivalence, building on approaches rooted in computer science to minimize basic models of computation through iterative partition refinements. The physical interpretability of the aggregation is shown on polynomial ODE systems for biochemical reaction networks, gene regulatory networks, and evolutionary game theory.

| S-EPMC5617256 | biostudies-literature

Better bones

Project description:Variation in the cystathionine beta synthase gene linked to susceptibility for osteoporosis in laying hens

| PRJEB32467 | ENA

TreeCmp: Comparison of Trees in Polynomial Time.

Project description:When a phylogenetic reconstruction does not result in one tree but in several, tree metrics permit finding out how far the reconstructed trees are from one another. They also permit to assess the accuracy of a reconstruction if a true tree is known. TreeCmp implements eight metrics that can be calculated in polynomial time for arbitrary (not only bifurcating) trees: four for unrooted (Matching Split metric, which we have recently proposed, Robinson-Foulds, Path Difference, Quartet) and four for rooted trees (Matching Cluster, Robinson-Foulds cluster, Nodal Splitted and Triple). TreeCmp is the first implementation of Matching Split/Cluster metrics and the first efficient and convenient implementation of Nodal Splitted. It allows to compare relatively large trees. We provide an example of the application of TreeCmp to compare the accuracy of ten approaches to phylogenetic reconstruction with trees up to 5000 external nodes, using a measure of accuracy based on normalized similarity between trees.

| S-EPMC3422086 | biostudies-other

Approximate protein structural alignment in polynomial time.

Project description:Alignment of protein structures is a fundamental task in computational molecular biology. Good structural alignments can help detect distant evolutionary relationships that are hard or impossible to discern from protein sequences alone. Here, we study the structural alignment problem as a family of optimization problems and develop an approximate polynomial-time algorithm to solve them. For a commonly used scoring function, the algorithm runs in O(n(10)/epsilon(6)) time, for globular protein of length n, and it detects alignments that score within an additive error of epsilon from all optima. Thus, we prove that this task is computationally feasible, although the method that we introduce is too slow to be a useful everyday tool. We argue that such approximate solutions are, in fact, of greater interest than exact ones because of the noisy nature of experimentally determined protein coordinates. The measurement of similarity between a pair of protein structures used by our algorithm involves the Euclidean distance between the structures (appropriately rigidly transformed). We show that an alternative approach, which relies on internal distance matrices, must incorporate sophisticated geometric ingredients if it is to guarantee optimality and run in polynomial time. We use these observations to visualize the scoring function for several real instances of the problem. Our investigations yield insights on the computational complexity of protein alignment under various scoring functions. These insights can be used in the design of scoring functions for which the optimum can be approximated efficiently and perhaps in the development of efficient algorithms for the multiple structural alignment problem.

| S-EPMC514457 | biostudies-literature

Local polynomial regression for pooled response data.

Project description:We propose local polynomial estimators for the conditional mean of a continuous response when only pooled response data are collected under different pooling designs. Asymptotic properties of these estimators are investigated and compared. Extensive simulation studies are carried out to compare finite sample performance of the proposed estimators under various model settings and pooling strategies. We apply the proposed local polynomial regression methods to two real-life applications to illustrate practical implementation and performance of the estimators for the mean function.

| S-EPMC7986571 | biostudies-literature

A general model for binary cell fate decision gene circuits with degeneracy: indeterminacy and switch behavior in the absence of cooperativity.

Project description:BackgroundThe gene regulatory circuit motif in which two opposing fate-determining transcription factors inhibit each other but activate themselves has been used in mathematical models of binary cell fate decisions in multipotent stem or progenitor cells. This simple circuit can generate multistability and explains the symmetric "poised" precursor state in which both factors are present in the cell at equal amounts as well as the resolution of this indeterminate state as the cell commits to either cell fate characterized by an asymmetric expression pattern of the two factors. This establishes the two alternative stable attractors that represent the two fate options. It has been debated whether cooperativity of molecular interactions is necessary to produce such multistability.Principal findingsHere we take a general modeling approach and argue that this question is not relevant. We show that non-linearity can arise in two distinct models in which no explicit interaction between the two factors is assumed and that distinct chemical reaction kinetic formalisms can lead to the same (generic) dynamical system form. Moreover, we describe a novel type of bifurcation that produces a degenerate steady state that can explain the metastable state of indeterminacy prior to cell fate decision-making and is consistent with biological observations.ConclusionThe general model presented here thus offers a novel principle for linking regulatory circuits with the state of indeterminacy characteristic of multipotent (stem) cells.

| S-EPMC3098230 | biostudies-literature

Hot carrier multiplication in plasmonic photocatalysis.

Project description:Light-induced hot carriers derived from the surface plasmons of metal nanostructures have been shown to be highly promising agents for photocatalysis. While both nonthermal and thermalized hot carriers can potentially contribute to this process, their specific role in any given chemical reaction has generally not been identified. Here, we report the observation that the H2-D2 exchange reaction photocatalyzed by Cu nanoparticles is driven primarily by thermalized hot carriers. The external quantum yield shows an intriguing S-shaped intensity dependence and exceeds 100% for high light intensities, suggesting that hot carrier multiplication plays a role. A simplified model for the quantum yield of thermalized hot carriers reproduces the observed kinetic features of the reaction, validating our hypothesis of a thermalized hot carrier mechanism. A quantum mechanical study reveals that vibrational excitations of the surface Cu-H bond is the likely activation mechanism, further supporting the effectiveness of low-energy thermalized hot carriers in photocatalyzing this reaction.

| S-EPMC8157927 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data