View source for Research

"''You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'"''

''&ndash;&ndash;'' '''George Bernard Shaw''' (1856 &ndash;1950)

Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be ''inductive'' (as opposed to ''deductive'') and ''conceptual'' (as opposed to ''applied''). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of ''analyzing'' the way things work in a new technology is straightforward; however the task of ''synthesizing'' new computational constructs is more challenging &ndash; and more interesting! 

Please see our [[Papers, Theses, and Presentations|Publications]] page for a full list of our papers. Here we highlight some  of our research'''''&ndash;''''' some it recent, some of it not. 
==Storing Data with Molecules==
''All new ideas pass through three stages:''
# ''It can't be done.''
# ''It probably can be done, but it's not worth doing.''
# ''I knew it was a good idea all along!''
''&ndash;&ndash;'''''Arthur C. Clarke (1917&ndash;2008)'''

Ever since Watson and Crick first described the molecular structure of DNA, its information-bearing potential has been apparent to computer scientists. With each nucleotide in the sequence drawn from the four-valued alphabet of {A, T , C, G}, a molecule of DNA with ''n'' nucleotides stores ''2n'' bits of data. Indeed, this information storage underpins life as we know it: all the instructions on how to build and operate a life form are stored in its DNA, honed over eons of evolutionary time. 

Could humans store data in DNA? ''"Can't be done '''&ndash;''''' ''too hard."'' 

Is it worth doing? ''"Definitely not. It will never work as well as our hard drives do."'' 

But one can store so much data so efficiently! "''I knew it was a good idea all along!''"
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" |'''title''':
| width="500" |[http://mriedel.ece.umn.edu/wiki/images/8/8f/Manicka_Stephan_Chari_Mendonsa_Okubo_Stolzberg-Schray_Reddy_Riedel_Automated_Routing_of_Droplets_for_DNA_Storage_on_a_Digital_Microfluidics_Platform.pdf Automated Routing of Droplets for DNA Storage on a Digital Microfluidics Platform]
|- valign="top"
|'''authors''':
|[http://mriedel.ece.umn.edu/wiki/index.php/Ajay_Manicka Ajay Manicka], Andrew Stephan, Sriram Chari, Gemma Mendonsa,
Peyton Okubo, John Stolzberg-Schray, Anil Reddy, and [http://mriedel.ece.umn.edu/wiki/index.php/Marc_Riedel Marc Riedel]
|- valign="top"
|'''under revision''':
|[https://arxiv.org/abs/2211.15494 Royal Society of Chemistry &ndash; Digital Discovery], 2023
|}
| width="70" align="center" |<span class="plainlinks"> [https://mriedel.ece.umn.edu/wiki/images/8/8f/Manicka_Stephan_Chari_Mendonsa_Okubo_Stolzberg-Schray_Reddy_Riedel_Automated_Routing_of_Droplets_for_DNA_Storage_on_a_Digital_Microfluidics_Platform.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span> 

[http://mriedel.ece.umn.edu/wiki/images/8/8f/Manicka_Stephan_Chari_Mendonsa_Okubo_Stolzberg-Schray_Reddy_Riedel_Automated_Routing_of_Droplets_for_DNA_Storage_on_a_Digital_Microfluidics_Platform.pdf Paper]
| width="70" align="center" |<span class="plainlinks">[https://mriedel.ece.umn.edu/wiki/images/1/11/Dna-storage-and-computing.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span> 

[https://mriedel.ece.umn.edu/wiki/images/1/11/Dna-storage-and-computing.pptx Slides]
|}

==Computing with Molecules==

“''If I can’t create it, I don’t understand it.''” &ndash;&ndash; '''Richard Feynman''' (1918&ndash;1988)

Computing has escaped – from desktops and data centers into the wild. Embedded microchips – found in our gadgets, our tools, our buildings, our soils, and even our bodies – are transforming our lives. And yet, there are limits to where silicon can go and where it can compute effectively. It is a foreign object that requires a power source (a battery or an AC plug). We are studying novel types of computing systems that are not foreign, but rather an integral part of their physical and chemical environment: systems that compute ''directly'' with molecules. A simple but radical idea: compute with '''acids''' and '''bases'''. An acidic solution corresponds to a "1", while a basic solution to "0":
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" |'''title''':
| width="500" |[http://mriedel.ece.umn.edu/wiki/images/0/02/Agiza_Oakley_Rosenstein_Rubenstein_Kim_Riedel_Reda_Digital_Circuits_and_Neural_Networks_Based_on_Acid-Base_Chemistry_Implemented_by_Robotic_Fluid_Handling.pdf Digital Circuits and Neural Networks Based on Acid-Base Chemistry Implemented by Robotic Fluid Handling]
|- valign="top"
|'''authors''':
|[https://cs.brown.edu/people/grad/aagiza/ Ahmed Agiza], [https://www.linkedin.com/in/kady-oakley-5b05a75b Kady Oakley], [http://rosenstein.engin.brown.edu/ Jacob Rosenstein], [https://rubenstein.group/authors/brenda-rubenstein/ Brenda Rubenstein],
[https://sites.brown.edu/kim-chemistry/eunsuk-kim/ Eunsuk Kim], [http://mriedel.ece.umn.edu/wiki/index.php/Marc_Riedel Marc Riedel], and [https://vivo.brown.edu/display/sreda Sherief Reda]
|- valign="top"
|'''appeared in''':
|[https://www.nature.com/articles/s41467-023-36206-8 '''Nature Communications'''], Vol. 14, No. 496, 2023
|}
|}

It's more complex that acids and bases, but DNA is a terrific chassis for computing. We have developed "CS 101" algorithms with DNA: Sorting, Shifting and Searching:
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [https://mriedel.ece.umn.edu/wiki/images/b/b2/Solanki-chen-riedel-parallel-pairwise-operations-on-data-stored-in-dna-sorting-xor-shifting-and-searching.pdf Parallel Pairwise Operations on Data Stored in DNA: Sorting, XOR, Shifting, and Searching]
|- valign="top"
| '''authors''':
| [[Arnav Solanki]], [[Tonglin Chen]], and [[Marc Riedel]]

|- valign="top"
| '''under review in''':
| [https://www.springer.com/journal/11047 Natural Computing], 2023
|- valign="top" 
| '''presented&nbsp;at''':
| [https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16207 International Conference on DNA Computing and Molecular Programming], 2021
|}
| width="70" align="center" | 
<span class="plainlinks">[https://mriedel.ece.umn.edu/wiki/images/b/b2/Solanki-chen-riedel-parallel-pairwise-operations-on-data-stored-in-dna-sorting-xor-shifting-and-searching.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>[https://mriedel.ece.umn.edu/wiki/images/b/b2/Solanki-chen-riedel-parallel-pairwise-operations-on-data-stored-in-dna-sorting-xor-shifting-and-searching.pdf Paper]
| width="70" align="center" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/d/d5/DNA27_Presentation.pdf http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/d/d5/DNA27_Presentation.pdf Slides]
|}

Just as electronic systems implement computation in terms of '''voltage''' (''energy per unit charge''), molecular systems  compute in terms of '''chemical concentrations''' (''molecules per unit volume''). We have developed digital logic that operates on molecules:<br>
{| align="center"
||
[[Image:molecular-reactions-are-rules.gif|center|thumb|300px|Molecular reactions define ''rules'' according to which reactants form products. Here molecules of type A combine with molecules of type B to form molecules of type C, at a rate proportional to the molecular concentrations of A and B as well as a rate constant ''k''.]]
||
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
||
[[Image:branch-migration.png|center|thumb|300px|We map abstract molecular reactions to DNA reactions. Through a process
called [http://pubs.acs.org/doi/pdfplus/10.1021/ja906987s DNA strand displacement], single strands of DNA displace parts of double strands, releasing other single strands.]] 
|}

'''Computational Constructs'''

Based on a bistable mechanism for representing bits, we implement a constituent set of logical components, including combinational components such as '''AND''', '''OR''', and '''XOR gates''', as well as sequential components such as '''D latches''' and '''D flip-flops'''. Using these components, we build full-fledged digital circuits such as a ''binary counters'' and ''linear feedback shift registers''. 

{|
| 
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Digital Logic with Molecular Reactions]]
|- valign="top"
| '''authors''':
| [[Hua Jiang]], [[Marc Riedel]], [http://www.ece.umn.edu/users/parhi Keshab Parhi]
|- valign="top"
| '''presented&nbsp;at''':
| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2013.
|}
| align="center" width="70" | 
<span class="plainlinks">[http://cctbio.ece.umn.edu/wiki/images/c/cf/Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>[[Media:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Paper]]
|}

We have developed a strategy for implementing signal processing with molecular reactions including operations such as '''filtering'''. We have demonstrated robust designs for [http://en.wikipedia.org/wiki/Finite_impulse_response Finite-Impulse Response (FIR)], [http://en.wikipedia.org/wiki/Infinite_impulse_response Infinite-Impulse Response (IIR)] filters, and [http://en.wikipedia.org/wiki/Fast_Fourier_transform Fast Fourier Transforms (FFTs)]. 

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf | Discrete-Time Signal Processing with DNA]]
|- valign="top"
| '''authors''':
| [[Hua Jiang]], Ahmed Salehi, [[Marc Riedel]] and [http://www.ece.umn.edu/users/parhi Keshab Parhi]
|- valign="top"
| '''appeared&nbsp;in''':
| [http://pubs.acs.org/doi/abs/10.1021/sb300087n ACS Synthetic Biology], Vol. 2 no. 5, pp. 245&ndash;254, 2013.<br>[[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA_Appendix.pdf | Supplementary Information: List of Reactions]]
|- valign="top"
| '''appeared&nbsp;in''':
| [http://www.computer.org/portal/web/dt IEEE Design & Test of Computers], Vol. 29, No. 3, pp. 21&ndash;31, 2012.
|- valign="top"
| '''presented at''':
| [http://www.iccad.com/ IEEE/ACM International Conference on Computer-Aided Design],<br> San Jose, CA, 2010.
|- valign="top"
| '''presented at''':
| [http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=7703&copyownerid=8242 IEEE Workshop on Signal Processing Systems], San Francisco, 2010
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf Paper]
| align="center" width="70" | 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx Slides]
|}

<br>
{| align="center"

|
[[Image:dna-logic-gates.gif|center|thumb|450px| Simulations of DNA implementation of logic gates. The input signals are molecular concentrations X and Y; the output signal is a molecular concentration Z. (A) AND gate. (B) OR gate. (C) NOR gate. (D) XOR gate.]] 
||
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
||
[[Image:moving-average-filter-simulation.gif|center|thumb|400px|Simulations of DNA implementation of a '''moving-average FIR filter'''. This filter removes the high-frequency component from an input signal, producing an output signal consisting of only the low-frequency component. Here the "signals" are molecular concentrations.]]
|| 
|}
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.

==Computational Immunology==

“''Biology is the study of the complex things in the Universe. Physics is the study of the simple ones.''” &ndash;&ndash; '''Richard Dawkins''' (1941&ndash; )

We are studying a problem that computer science currently judges to be very difficult: to predict cellular immunity. It centers on the question of how strongly a given molecule binds to another. The given molecule is a peptide – a fragment of a protein derived from a pathogen, such as a virus. The other is a molecule called Major Histocompatibility Class I (MHC I) that is expressed on the surface of most of our cells. MHC I molecules have a cleft into which a peptide can bind. A peptide will only bind if it fits into the cleft like a key into a lock. 

<br>
{| align="center"
||
[[Image:Peptide1.PNG|center|thumb|300px|A peptide (in blue) bound to a MHC Class I protein (in yellow).]]
||
||
|}

The binding is a critical step in a critical component of the immune system: it allows circulating T-cells to kill off infected cells.  If this mechanism succeeds, an infection is stopped in its tracks. If it fails, then infected cells become factories for reproducing copies of the virus and full-blown disease results. Most aspects of the chemistry are well understood. The difficulty lies with the combinatorial scale . There are 38,000 peptides for a virus like SARS- Cov-2 each paired with 21,000 variants of MHC I molecules in the human population. This translates to three-quarters of a billion distinct pairings. Simulating them all would take billions of days, of computing time – clearly an intractable proposition. But we are turning billions of days of computing time into just a few weeks of cloud computing time, donated by [https://blogs.oracle.com/research/post/announcing-inaugural-cohort-oracle-research-fellows Oracle]:
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [https://mriedel.ece.umn.edu/wiki/images/d/d5/UMN_Mayo_CHIP_Center.pdf The UMN/Mayo Computational Human Immuno-Peptidome (CHIP) Project]
|- valign="top" 
| '''Investigator''':
|  [[Marc Riedel]]
|- valign="top"
| '''Agency''':
| [https://www.oracle.com/research/ Oracle]
|- valign="top"
| '''Program''':
| [https://blogs.oracle.com/research/post/announcing-inaugural-cohort-oracle-research-fellows Oracle Research Fellowship]
|- valign="top"
| '''Award''':
| $200,000
|- valign="top"
| '''Duration''':
| 2022 &ndash; 2024
|}
| width="70" align="center" | 
<span class="plainlinks">
[https://mriedel.ece.umn.edu/wiki/images/d/d5/UMN_Mayo_CHIP_Center.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>[https://mriedel.ece.umn.edu/wiki/images/d/d5/UMN_Mayo_CHIP_Center.pdf Proposal]
|}

The first step is to solve the problem of hydrophobicity:
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Solanki Riedel Cornette Udell Vasmatzis Hydrophobicity Identifies False Positives and False Negatives in Peptide-MHC Binding.pdf|Hydrophobicity Identifies False Positives and False Negatives in Peptide-MHC Binding]]
|- valign="top"
| '''authors''':
| [[Arnav Solanki]], [[Marc Riedel]], [https://orion.math.iastate.edu/cornette/ James Cornette], [[Julia Udell]], and [https://www.mayo.edu/research/faculty/vasmatzis-george-ph-d/bio-00027811 George Vasmatzis] 
|- valign="top"
| '''appeared in''':
| [https://www.frontiersin.org/journals/oncology/articles/10.3389/fonc.2022.1034810/full Frontiers in Oncology], Vol. 12, No. 1034810, 2022 
|- valign="top"
| '''presented&nbsp;at''':
| [http://ismco.net/ 3rd International Symposium on Mathematical and Computational Oncology], 2021
|}
| align="center" width="70" |
<span class="plainlinks">
[https://mriedel.ece.umn.edu/wiki/images/1/1b/Solanki_Riedel_Cornette_Udell_Vasmatzis_Hydrophobicity_Identifies_False_Positives_and_False_Negatives_in_Peptide-MHC_Binding.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Solanki_Riedel_Cornette_Udell_Vasmatzis_Hydrophobicity_Identifies_False_Positives_and_False_Negatives_in_Peptide-MHC_Binding.pdf | Paper]]
| align="center" width="70" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/8/8b/ISMCO2021.pdf http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br>[http://mriedel.ece.umn.edu/wiki/images/8/8b/ISMCO2021.pdf Slides]
|}
The next is to understand the role of variants:
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Solanki Riedel Cornette Udell Vasmatzis Evasive Spike Variants Elucidate the Preservation of T cell Immune Response to the SARS-CoV-2 Omicron Variant.pdf|Evasive Spike Variants Elucidate the Preservation of T cell Immune Response to the SARS-CoV-2 Omicron Variant]]
|- valign="top"
| '''authors''':
| [[Arnav Solanki]], [[Marc Riedel]], [https://orion.math.iastate.edu/cornette/ James Cornette], [[Julia Udell]], and [https://www.mayo.edu/research/faculty/vasmatzis-george-ph-d/bio-00027811 George Vasmatzis] 
|- valign="top"
| '''under review''':
| [https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=8857 IEEE/ACM Trans. on Computational Biology and Bioinformatics], 2023 
|}
| align="center" width="70" |
<span class="plainlinks">
[https://mriedel.ece.umn.edu/wiki/images/1/17/Solanki_Riedel_Cornette_Udell_Vasmatzis_Evasive_Spike_Variants_Elucidate_the_Preservation_of_T_cell_Immune_Response_to_the_SARS-CoV-2_Omicron_Variant.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Solanki_Riedel_Cornette_Udell_Vasmatzis_Evasive_Spike_Variants_Elucidate_the_Preservation_of_T_cell_Immune_Response_to_the_SARS-CoV-2_Omicron_Variant.pdf | Paper]]
|}

==Computing with Random Bit Streams==

"''To invent, all you need is a pile of junk and a good imagination.''"  &ndash;&ndash; '''Thomas A. Edison''' (1847&ndash;1931)

Humans are accustomed to counting in a positional number system &ndash; [http://en.wikipedia.org/wiki/Decimal decimal] radix.  Nearly all computer systems operate on another positional number system &ndash; [http://en.wikipedia.org/wiki/Binary_numeral_system binary] radix. From the standpoint of ''representation'', such positional systems are compact: given a radix ''b'', one can represent ''b<sup>n</sup>'' distinct numbers with ''n'' digits. However, from the standpoint of ''computation'', positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "''decoded''", with each digit weighted according to its position. The result must be "''encoded''" back in positional form. Any student who has designed a [http://en.wikipedia.org/wiki/Binary_multiplier binary multiplier] in a course on [[EE2301 | logic design]] can appreciate all the complexity that goes into wiring up such an operation.

==== Logic that Operates on Probabilities ====

We advocate an alternative representation: random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX).  

{| align="center"
| [[Image:stochastic-multiplier.png|center|thumb|350px|'''Multiplication''' with an AND gate. Here the variables represents the ''probabilities'' of obtaining a 1 versus a 0 in stochastic bit streams. The AND gate produces an output probability <math>c</math> that is the product of the of the input probabilities <math>a</math> and <math>b</math>.]]
||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|| [[Image:stochastic-adder.png|thumb|320px|'''Scaled addition''' with a multiplexer (MUX). 
Given input probabilities <math>a</math>, <math>b</math> and <math>s</math>, the MUX produces an output probability <math>c = a s + (1 - s) b</math>.]]
|}

We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams.    

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [//mriedel.ece.umn.edu/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf An Architecture for Fault-Tolerant Computation with Stochastic Logic]
|- valign="top"
| '''authors''':
| [[Weikang Qian]], [http://www.arctic.umn.edu/people.shtml Xin Li], [[Marc Riedel]], [http://www.ece.umn.edu/users/kia/ Kia Bazargan], and [http://www.arctic.umn.edu/lilja.shtml David Lilja]
|- valign="top" 
| '''appeared in''':
| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], Vol. 60, No. 1, pp. 93&ndash;105, 2011
|}
| width="70" align="center" | 
<span class="plainlinks">
[http://cadbio.com/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[//mriedel.ece.umn.edu/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf Paper]
|}
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf | Logical Computation on Stochastic Bit Streams with Linear Finite State Machines]]
|- valign="top"
| '''authors''':
| [http://www.ece.umn.edu/~lipeng/ Peng Li], [http://www.arctic.umn.edu/lilja.shtml David Lilja], [[Weikang Qian]],[http://www.ece.umn.edu/users/kia/ Kia Bazargan] and [[Marc Riedel]] 
|- valign="top" 
| '''appeared in''':
| [http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6307798 IEEE Transactions on Computers], Vol. 63, No. 6., pp. 1474&ndash;1486, 2014
|- valign="top" 
| '''presented at''':
| [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6165056 IEEE/ACM Asia and South Pacific Design Automation Conference],<br>Sydney, Australia, 2012
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cctbio.ece.umn.edu/wiki/images/7/7c/Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Li_Lilja_Qian_Riedel_Bazargan_Logical_Computation_on_Stochastic_Bit_Streams_with_Linear_Finite_State_Machines.pdf | Paper]]
|}

====Logic that Generates Probabilities====

Schemes for probabilistic computation can exploit physical sources to generate random values in the form of bit streams. Generally, each source has a fixed bias and so provides bits that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we demonstrate novel techniques for synthesizing combinational logic that transforms a set of ''source'' probabilities into different ''target'' probabilities. 
[[File:Generate_Probabilities_Example.png|center|frame|Given a set ''S'' of source probabilities {0.4, 0.5}, we can synthesize a combinational circuit to generate an arbitrary ''decimal'' output probability. The example shows how to generate 0.119. Each AND gate performs a multiplication and each inverter performs a "one-minus" operation.]]

{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]
|- valign="top"
| '''authors''':
| [[Weikang Qian]], [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]
|- valign="top"
| '''will appear in''':
| [http://tcad.polito.it/ IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems], 2012.
|- valign="top"
| '''presented&nbsp;at''':
| [http://www.iccad.com/events/eventdetails.aspx?id=106-5-C International Conference on Computer-Aided Design], San Jose, 2009<br>(nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award''').
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf  | Paper]]
| align="center" width="70" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]
|}

====Computing with Crappy Clocks====

Clock distribution networks are a significant source of power consumption and a major design bottleneck for high-performance circuits. We have proposed a radically new approach: splitting clock domains at a very fine level, with domains consisting of only a handful of gates each. These domains are synchrnonized by "crappy clocks", generated locally with inverter rings. This is feasible if one adopts the paradigm of computing on randomized bit streams. 
[[File:polysynchronous-and.png|center|frame|thumb|Stochastic multiplication using an AND gate with unsynchronized random bit streams. The stochastic paradigm can tolerate arbitrarly high clock skew. Accordingly, one can replace an expensive global clock distribution network with cheap local clocks, generated by inverter rings &ndash; "crappy clocks".]]
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media: Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf | Polysynchronous Stochastic Circuits]]
|- valign="top"
| '''authors''':
| [[M. Hassan_Najafi]], [http://www.arctic.umn.edu/lilja.shtml David Lilja], [[Marc Riedel]], and [http://www.ece.umn.edu/users/kia/ Kia Bazargan]
|- valign="top" 
| '''to appear in''':
| [http://www.amsv.umac.mo/aspdac2016/ IEEE/ACM Asia and South Pacific Design Automation Conference], 2016 
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cctbio.ece.umn.edu/wiki/images/e/ec/Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Najafi_Lilja_Riedel_Bazargan_Polysynchronous_Stochastic_Circuits.pdf | Paper]]
|}

Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.

==Computing with Feedback==

"''A person with a new idea is a crank until the idea succeeds.''" &ndash;&ndash; '''Mark Twain''' (1835&ndash;1910)

The accepted wisdom is that [http://en.wikipedia.org/wiki/Combinational_logic combinational circuits] (i.e., memoryless circuits) must have ''acyclic'' (i.e., loop-free or feed-forward) topologies.  And yet simple examples suggest that this need not be so.  We advocate the design of '''cyclic''' combinational circuits (i.e., circuits with loops or feedback paths). We have proposed a methodology for synthesizing such circuits and demonstrated that it produces significant improvements in area and in delay. 
[[Image:cyclic-combinational-circuit.gif|center|thumb|none|550px|A circuit that has feedback and yet is combinational.]]
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Cyclic Boolean Circuits]]
|- valign="top"
| '''authors''':
| [[Marc Riedel]] and [http://paradise.caltech.edu/bruck.html Shuki Bruck]
|- valign="top"
| '''appeared &nbsp;in''':
| [http://www.elsevier.com/wps/find/journaldescription.cws_home/505609/description#description Discrete Applied Mathematics], Vol. 160, No. 13&ndash;14, pp. 1877&ndash;1900, 2011.

|- valign="top"
| '''dissertation''':
| Ph.D., [http://www.ee.caltech.edu Electrical Engineering], [http://www.caltech.edu Caltech], 2004<br>(winner of [http://www.ee2.caltech.edu/charles_wilts.html Charles H. Wilts Prize] for the '''Best Ph.D. Dissertation''' in EE at Caltech).

|- valign="top"
| '''presented&nbsp;at''':
| [http://www2.dac.com/40th/index.html Design Automation Conference], Anahiem, CA, 2003<br>(winner of '''DAC Best Paper Award''').

|}
| align="center" width="70" | 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/9/94/Riedel_Bruck_Cyclic_Boolean_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Paper]]
| align="center" width="70" | 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/7/7a/Riedel_Cyclic_Combinational_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Riedel_Cyclic_Combinational_Circuits.pdf | PhD Dissertation]]
| align="center" width="70" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt Slides]
|}
Please see our [[Papers,_Theses,_and_Presentations | Publications]] page for more of our papers on this topic.


==Computing with Nanoscale Lattices==

"''Listen to the technology; find out what it’s telling you.''” &ndash;&ndash; '''Carver Mead''' (1934&ndash;&nbsp;&nbsp;)

In his seminal Master's Thesis, [http://en.wikipedia.org/wiki/Claude_Shannon Claude Shannon] made the connection between Boolean algebra and switching circuits. He considered '''two-terminal''' switches corresponding to electromagnetic relays. A Boolean function can be implemented in terms of connectivity across a network of switches, often arranged in a series/parallel configuration.  We have developed a method for synthesizing Boolean functions with networks of '''four-terminal switches'''.  Our model is applicable for variety of nanoscale technologies, such as [http://www.sciencemag.org/content/302/5649/1377.short nanowire crossbar arrays], as [http://en.wikipedia.org/wiki/Molecular_switch molecular switch-based structures].
{| align="center"
|
[[Image:two-terminal.gif|center|thumb|none|315px|Shannon's model: '''two-terminal switches'''.  Each switch is either ON (closed) or OFF (open). A Boolean function is implemented in terms of connectivity across a network of switches, between the source S and the drain D.]]
|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|| [[Image:four-terminal.gif|center|thumb|none|315px|Our model: '''four-terminal switches'''. Each switch is either mutually connected to its neighbors (ON) or disconnected (OFF). A Boolean function is implemented in terms of connectivity between the top and bottom plates. This network implements the same function as the two-terminal network on the left.]] 
|}
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" |'''title''':
| width="500" |[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Logic Synthesis for Switching Lattices]]
|- valign="top"
| '''authors''':
| [[Mustafa Altun]] and [[Marc Riedel]]
|- valign="top"
| '''will appear&nbsp;in''':
| [http://www.computer.org/portal/web/tc IEEE Transactions on Computers], 2011.
|- valign="top"
| '''presented&nbsp;at''':
| [http://www.dac.com/47th/index.aspx Design Automation Conference], Anaheim, CA, 2010.
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cadbio.com/wiki/images/c/ca/Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Paper]]
| align="center" width="70" | 
<span class="plainlinks">
[http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt Slides]
|}

The impetus for nanowire-based technology is the potential density, scalability and manufacturability.  Many other novel and emerging technologies fit the general model of four-terminal switches.  For instance, researchers are investigating [http://en.wikipedia.org/wiki/Spin_wave spin waves]. A common feature of many emerging technologies for switching networks is that they exhibit high defect rates. 
{| align="center"
|
[[Image:nano-crossbar.gif|center|thumb|315px|A nanowire crossbar switch. 
The connections between horizontal and vertical
wires are FET-like junctions.  When high or low voltages are applied to input nanowires, the
FET-like junctions that cross these develop a high or low impedance, respectively.
]]
|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|| [[Image:percolation.gif|center|thumb|315px| In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. Unless the defect rate exceeds an error margin, with high probability no connection forms between the top and bottom plates for logical zero ("OFF"); with high probability, a connection forms for logical one ("ON").]]
|}
We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of [http://en.wikipedia.org/wiki/Percolation_theory percolation]. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly in the presence of defects.
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" |'''title''':
| width="500" |[[Media:Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Synthesizing Logic with Percolation in Nanoscale Lattices]]
|- valign="top"
| '''authors''':
| [[Mustafa Altun]] and [[Marc Riedel]]
|- valign="top"
| '''appeared&nbsp;in''':
| [http://www.igi-global.com/Bookstore/TitleDetails.aspx?TitleId=1117&DetailsType=Description/ International Journal of Nanotechnology and Molecular Computation], <br>Vol. 3, No. 2, pp. 12&ndash;30, 2011.
|- valign="top"
| '''presented&nbsp;at''':
| [http://www.dac.com/46th/index.aspx Design Automation Conference], San Francisco, CA, 2009.
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cadbio.com/wiki/images/3/3b/Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Paper]]
| align="center" width="70" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt Slides]
|}
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on these topics.

==Algorithms and Data Structures==

"''There are two kinds of people in the world: those who divide the world into two kinds of people, and those who don't.''" &ndash;&ndash; '''Robert Charles Benchley''' (1889&ndash;1945)

Consider the task of designing a digital circuit with 256  inputs. From a mathematical standpoint, such a circuit performs mappings from a space of <math>2^{256}</math> Boolean input values to Boolean output values. (The number of rows in a [http://en.wikipedia.org/wiki/Truth_table truth table] for such a function is approximately equal to [http://en.wikipedia.org/wiki/Observable_universe#Matter_content the number of atoms in the universe] &ndash; <math>10^{77}</math> rows versus <math>10^{79}</math> atoms!) Verifying such a function, let alone designing the corresponding circuit, would seem to be an intractable problem. Circuit designers have succeeded in their endeavor largely as a result of innovations in the data structures and algorithms used to represent and manipulate [http://en.wikipedia.org/wiki/Boolean_function Boolean functions].  We have developed novel, efficient techniques for synthesizing functional dependencies based on so-called [http://en.wikipedia.org/wiki/Boolean_satisfiability_problem SAT-solving algorithms]. We use [http://en.wikipedia.org/wiki/Craig_interpolation Craig Interpolation] to generate circuits from the corresponding Boolean functions. 
{| align="center"
| [[Image:sat-squid.jpg|center|thumb|350px|A circuit construct for SAT-based verification.]]
||&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
|| [[Image:squid.jpg|thumb|350px|A squid.]]
|}
{|
| 
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf | Reduction of Interpolants For Logic Synthesis]]
|- valign="top"
| '''authors''':
| [[John Backes]] and [[Marc Riedel]]
|- valign="top"
| '''presented&nbsp;at''':
| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2010.
|}
| align="center" width="70" | 
<span class="plainlinks">[http://cadbio.com/wiki/images/b/b6/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>[[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf  | Paper]]
| align="center" width="70" | 
<span class="plainlinks">[http://mriedel.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>
<br> [http://mriedel.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt Slides]
|}
Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on this topic. (Papers on SAT-based circuit verification, that is, not on squids.)

==Mathematics==

"''Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true.''" &ndash;&ndash; '''Bertrand Russell''' (1872&ndash;1970)

[[Image:xkcd_disciplines_by_purity.png|center|thumb|none|550px|Mathematics, before the era of [http://en.wikipedia.org/wiki/LaTeX LaTeX].]]


The great mathematician [http://en.wikipedia.org/wiki/John_von_Neumann John von Neumann] articulated the view that research should never meander too far down theoretical paths; it should always be guided by potential applications. This view was not based on concerns about the relevance of his profession; rather, in his judgment, real-world applications give rise to the most ''interesting'' problems for mathematicians to tackle. At their core, most of our research contributions are mathematical contributions. The tools of our trade are [http://en.wikipedia.org/wiki/Discrete_mathematics discrete math], including [http://en.wikipedia.org/wiki/Combinatorics combinatorics] and [http://en.wikipedia.org/wiki/Probability probability theory].
[[Image:papa-handwriting.gif|center|thumb|none|550px|Mathematics, before the era of [http://en.wikipedia.org/wiki/LaTeX LaTeX].]]
{|
|
{| style="background:#F0E68C"
|- valign="top"
| width="100" | '''title''':
| width="500" | [[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Uniform Approximation and Bernstein Polynomials with<br>Coefficients in the Unit Interval]]
|- valign="top" 
| '''authors''':
| [[Weikang Qian]], [[Marc Riedel]], and [http://dms.umontreal.ca/Professeurs/rosenb/index.html Ivo Rosenberg]
|- valign="top"
| '''appeared in''':
| [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-51WP38J-1&_user=10&_coverDate=04%2F30%2F2011&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1678369105&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=057c5b37ffe293c8c2fa1d00b17d26c7&searchtype=a European Journal of Combinatorics], Vol. 32, No. 3, pp. 448&ndash;463, 2011.
|}
| align="center" width="70" | 
<span class="plainlinks">
[http://cadbio.com/wiki/images/a/ab/Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>
<br>
[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf  | Paper]]
|}

Please see our "[[Papers,_Theses,_and_Presentations |Publications]]" page for more of our papers on this topic.