MediaWiki API result
This is the HTML representation of the JSON format. HTML is good for debugging, but is unsuitable for application use.
Specify the format parameter to change the output format. To see the non-HTML representation of the JSON format, set format=json.
See the complete documentation, or the API help for more information.
{
"batchcomplete": "",
"continue": {
"gapcontinue": "Robby_Friedlander",
"continue": "gapcontinue||"
},
"warnings": {
"main": {
"*": "Subscribe to the mediawiki-api-announce mailing list at <https://lists.wikimedia.org/postorius/lists/mediawiki-api-announce.lists.wikimedia.org/> for notice of API deprecations and breaking changes."
},
"revisions": {
"*": "Because \"rvslots\" was not specified, a legacy format has been used for the output. This format is deprecated, and in the future the new format will always be used."
}
},
"query": {
"pages": {
"11": {
"pageid": 11,
"ns": 0,
"title": "Research",
"revisions": [
{
"contentformat": "text/x-wiki",
"contentmodel": "wikitext",
"*": "\"''You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'\"''\n\n''––'' '''George Bernard Shaw''' (1856 –1950)\n\nOur 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. \n==Storing Data with Molecules==\n''All new ideas pass through three stages:''\n# ''It can't be done.''\n# ''It probably can be done, but it's not worth doing.''\n# ''I knew it was a good idea all along!''\n''––'''''Arthur C. Clarke (1917–2008)'''\n\nEver since Watson and Crick first described the molecular structure of DNA, its information-bearing potential has been apparent. 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. \n* Could we store data for our computer systems in DNA? ''\"Can't be done '''–''''' ''too hard.\"''\n* Is it worth doing? ''\"Definitely not. It will never work as well as our hard drives do.\"''\n* But one can store so much data so efficiently! \"''I knew it was a good idea all along!''\"\n<br>\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" |'''title''':\n| 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]\n|- valign=\"top\"\n|'''authors''':\n|[http://mriedel.ece.umn.edu/wiki/index.php/Ajay_Manicka Ajay Manicka], Andrew Stephan, Sriram Chari, Gemma Mendonsa,\nPeyton Okubo, John Stolzberg-Schray, Anil Reddy, and [http://mriedel.ece.umn.edu/wiki/index.php/Marc_Riedel Marc Riedel]\n|- valign=\"top\"\n|'''appeared in''':\n|[https://pubs.rsc.org/en/content/articlepdf/2023/DD/D3DD00083D?page=search Royal Society of Chemistry – Digital Discovery], Vol. 2, pp. 1436–1451, 2023\n|}\n| 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> \n\n[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]\n| 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> \n\n[https://mriedel.ece.umn.edu/wiki/images/1/11/Dna-storage-and-computing.pptx Slides]\n|}\n<br>\n[[File:Dna-computing-dalle.jpg|center|thumb|Storing data in DNA.]]\n<br>\n\n==Computing with Molecules==\n\n\"''Biology is the most powerful technology ever created. DNA is software, protein are hardware, cells are factories''.\"\n\n––'''Arvind Gupta (1953– )'''\n\nComputing has escaped! It has gone from desktops and data centers into the wild. Embedded microcontrollers \u2013 found in our gadgets, our buildings, and even our bodies \u2013 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 electrical power source. \n\nWe are studying novel types of computing systems that are not foreign, but rather an integral part of their physical and chemical environments: systems that compute ''directly'' with molecules. A simple but radical idea: compute with '''acids''' and '''bases'''. An acidic solution corresponds to a \"1\" and a basic solution to \"0\".\n<br>\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" |'''title''':\n| 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]\n|- valign=\"top\"\n|'''authors''':\n|[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],\n[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]\n|- valign=\"top\"\n|'''appeared in''':\n|[https://www.nature.com/articles/s41467-023-36206-8 '''Nature Communications'''], Vol. 14, No. 496, 2023\n|}\n|}\n<br>\n\n[[File:Computing-with-chemistry.jpg|center|thumb|450x450px|Computing with Acids and Bases]]\n<br>\n\nIt'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'':\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| 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]\n|- valign=\"top\"\n| '''authors''':\n| [[Arnav Solanki]], [[Tonglin Chen]], and [[Marc Riedel]]\n\n|- valign=\"top\"\n| '''appeared in''':\n| [https://link.springer.com/article/10.1007/s11047-023-09964-z Natural Computing], 2023\n|- valign=\"top\" \n| '''presented at''':\n| [https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16207 International Conference on DNA Computing and Molecular Programming], 2021\n|}\n| width=\"70\" align=\"center\" | \n<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>\n<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]\n| width=\"70\" align=\"center\" | \n<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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/d/d5/DNA27_Presentation.pdf Slides]\n|}\nBased on a bistable mechanism for representing bits, we have implemented logic gates such '''AND''', '''OR''', and '''XOR gates''', as well as sequential components such as '''latches''' and '''flip-flops''' with DNA. Using these components, we have built full-fledged digital circuits such as a ''binary counters'' and ''linear feedback shift registers''.\n{|\n| \n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Digital Logic with Molecular Reactions]]\n|- valign=\"top\"\n| '''authors''':\n| [[Hua Jiang]], [[Marc Riedel]], [http://www.ece.umn.edu/users/parhi Keshab Parhi]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2013.\n|}\n| align=\"center\" width=\"70\" | \n<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>\n<br>[[Media:Jiang_Riedel_Parhi_Digital_Logic_with_Molecular_Reactions.pdf | Paper]]\n|}\n\n[[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.]] \nAlso, we have performed signal processing including operations such as '''filtering''' and '''fast-fourier transforms (FFTs)''' with DNA. \n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf | Discrete-Time Signal Processing with DNA]]\n|- valign=\"top\"\n| '''authors''':\n| [[Hua Jiang]], Ahmed Salehi, [[Marc Riedel]] and [http://www.ece.umn.edu/users/parhi Keshab Parhi]\n|- valign=\"top\"\n| '''appeared in''':\n| [http://pubs.acs.org/doi/abs/10.1021/sb300087n ACS Synthetic Biology], Vol. 2 no. 5, pp. 245–254, 2013.<br>[[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA_Appendix.pdf | Supplementary Information: List of Reactions]]\n|- valign=\"top\"\n| '''appeared in''':\n| [http://www.computer.org/portal/web/dt IEEE Design & Test of Computers], Vol. 29, No. 3, pp. 21–31, 2012.\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.iccad.com/ IEEE/ACM International Conference on Computer-Aided Design],<br> San Jose, CA, 2010.\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=7703©ownerid=8242 IEEE Workshop on Signal Processing Systems], San Francisco, 2010\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/3/36/Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf Paper]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/2/2a/Jiang_Kharam_Riedel_Parhi_Digital_Signal_Processing_with_Biomolecular_Reactions.pptx Slides]\n|}\n\n<br>\n\n\n[[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.]]\n\nPlease see our \"[[Papers,_Theses,_and_Presentations |Publications]]\" page for more of our papers on these topics.\n\n==Computational Immunology==\n\n\u201c''Physics is the study of the simple things in the Universe. Biology is the study of the complex ones.'' \u201d \n\n–– '''Richard Dawkins''' (1941– )\n\nWe are studying a problem that computer science currently judges to be very difficult: '''''predicting cellular immunity'''''. It centers on the question of how strongly molecules binds to one another. The molecules in question are ''peptides'' \u2013 fragments of proteins from a virus \u2013 binding to cell-surface receptors. A peptide will only bind if it fits like a key into a lock. \n{| align=\"center\"\n||\n[[Image:Peptide1.PNG|center|thumb|500px|A peptide (in blue) bound to a MHC Class I protein (in yellow).]]\n||\n||\n|}\n\nThe 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; full-blown disease results. Given a novel pathogen, such as SARS-Cov-2, predicting whether the immune system of an individual will do its job at fighting off the disease comes down to predicting how well the viral peptides bind to the cell-surface receptors of that person. We are tackling the problem with cloud computing resources, donated by [https://blogs.oracle.com/research/post/announcing-inaugural-cohort-oracle-research-fellows Oracle]:\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| 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]\n|- valign=\"top\" \n| '''Investigator''':\n| [[Marc Riedel]]\n|- valign=\"top\"\n| '''Agency''':\n| [https://www.oracle.com/research/ Oracle]\n|- valign=\"top\"\n| '''Program''':\n| [https://blogs.oracle.com/research/post/announcing-inaugural-cohort-oracle-research-fellows Oracle Research Fellowship]\n|- valign=\"top\"\n| '''Award''':\n| $200,000\n|- valign=\"top\"\n| '''Duration''':\n| 2022 – 2024\n|}\n| width=\"70\" align=\"center\" | \n<span class=\"plainlinks\">\n[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>\n<br>[https://mriedel.ece.umn.edu/wiki/images/d/d5/UMN_Mayo_CHIP_Center.pdf Proposal]\n|}\n\n==Computing with Random Bit Streams==\n\n\"''To invent, all you need is a pile of junk and a good imagination.''\" –– '''Thomas A. Edison''' (1847–1931)\n\nHumans are accustomed to counting in a positional number system – [http://en.wikipedia.org/wiki/Decimal decimal] radix. Nearly all computer systems operate on another – [http://en.wikipedia.org/wiki/Binary_numeral_system binary] radix. We are so accustomed to these systems that it counterintuitive to ask: ''can we compute using a different representatio''n? and ''why would we want to''? \n\n==== Stochastic Logic ====\n\nWe advocate an alternative representation: computing on random bit streams, where the signal value is encoded by the probability of obtaining a one versus a zero. Why compute this way? Using '''stochastic logic''', we can compute complex functions with very, very simple circuits. For instance, we can perform multiplication with a single AND gate and addition with a single MUX: \n\n{| align=\"center\"\n| [[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>.]]\n|| \n|| [[Image:stochastic-adder.png|thumb|320px|'''Scaled addition''' with a multiplexer (MUX). \nGiven 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>.]]\n|} \n\nUsing conventional binary, building a circuit that computes, say a polynomial approximation to a trigonometric function such as ''tanh(x)'' or ''cos(x),'' requires ''thousands'' of logic gates. With stochastic logic, we have shown that we can compute such functions with about a ''dozen'' logic gates, so a '''100X reduction in gate count'''. Our most important contribution is a '''general methodology for synthesizing polynomial functions''' with stochastic logic, one of the seminal contributions to the field: \n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| 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]\n|- valign=\"top\"\n| '''authors''':\n| [[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]\n|- valign=\"top\" \n| '''appeared in''':\n| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], Vol. 60, No. 1, pp. 93–105, 2011\n|}\n| width=\"70\" align=\"center\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[//mriedel.ece.umn.edu/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf Paper]\n|}\n\n====Logic that Generates Probabilities====\n\nWe have also shown how to synthesize logic that transforms a set of ''source'' probabilities into different ''target'' probabilities. \n[[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.]]\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]\n|- valign=\"top\"\n| '''authors''':\n| [[Weikang Qian]], [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]\n|- valign=\"top\"\n| '''will appear in''':\n| [http://tcad.polito.it/ IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems], 2012.\n|- valign=\"top\"\n| '''presented at''':\n| [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''').\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<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>\n<br> [http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]\n|}\n\n'''<big>A Deterministic Approach</big>'''\n\nHaving championed stochastic logic for many years, we decided to reexamine its foundations. Why can complex functions be computed with such simple circuits when we compute on probabilities? Intuition might suggest that somehow we are harnessing deep aspects of probability theory. ''This intuition is <u>wrong</u>''.\n\nThe keys is that we operate on uniform representation rather than a positional one. We showed that '''we can compute deterministically using the same structures that we use when computing stochastically.''' ''There is no need to do anything randomly!'' This upended the field that we had pioneered.\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [//mriedel.ece.umn.edu/wiki/images/c/c9/Najafi_Jenson_Lilja_Riedel_Performing_Stochastic_Computation_Deterministically.pdf Performing Stochastic Computation Deterministically]\n|- valign=\"top\"\n| '''authors''':\n| [[Devon Jenson]], [[M. Hassan Najafi]], [https://ece.umn.edu/directory/lilja-david/ David Lilja], and [[Marc Riedel]]\n|- valign=\"top\"\n| '''appeared in''':\n| [https://ieeexplore.ieee.org/document/8793244 IEEE Trans. on Very Large Scale Integration Systems],<br>Vol. 27, No. 29, pp. 2925–2938, 2019\n|- valign=\"top\"\n| '''presented at''':\n| [https://iscas2020.org IEEE International Symposium of Circuits and Systems], 2020\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.ieee.org/conferences_events/conferences/conferencedetails/index.html?Conf_ID=38629 IEEE/ACM International Conference on Computer-Aided Design], 2016\n|}\n| width=\"70\" align=\"center\" |\n<span class=\"plainlinks\">\n[http://mriedel.ece.umn.edu/wiki/images/c/c9/Najafi_Jenson_Lilja_Riedel_Performing_Stochastic_Computation_Deterministically.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[//mriedel.ece.umn.edu/wiki/images/c/c9/Najafi_Jenson_Lilja_Riedel_Performing_Stochastic_Computation_Deterministically.pdf Paper]\n| width=\"70\" align=\"center\" |\n<span class=\"plainlinks\">[http://cadbio.com/wiki/images/4/4f/Jenson_Riedel_A_Deterministic_Approach_to_Stochastic_Computing.pptx http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br>[http://cadbio.com/wiki/images/4/4f/Jenson_Riedel_A_Deterministic_Approach_to_Stochastic_Computing.pptx Slides]\n|}\n\n====Time-Encoded Computing====\n\nComputing deterministically on bit streams really means that, instead of encoding data in '''''space''''', we encode them '''''time'''''. The time-encoding consists of periodic signals, with the value encoded as the fraction of the time that the signal is in the high (on) state compared to the low (off) state in each cycle.\n\n{| align=\"center\"\n|[[File:Analog-in-time.jpg|center|thumb|500px|Encoding a value in time. The value represented is the fraction of the time that the signal is high in each cycle, in this case 0.687.]]\n|\n||[[File:Multiplicaiton-on-time-encoding-signals.jpg|thumb|500px|Multiplication with a single AND gate, operating on deterministic periodic signals. ]]\n|}\nAs technology has scaled and device sizes have gotten smaller, the supply voltages have dropped while the device speeds have improved. Control of the dynamic range in the voltage domain is limited; however, control of the length of pulses in the time domain can be precise. Encoding data in the time domain can be done more accurately and more efficiently than converting signals into binary radix. So we can compute ''more precisely,'' ''faster'', and with ''fewer logic gates:''\n{|\n|-\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [//mriedel.ece.umn.edu/wiki/images/b/b0/Najafi_Jamali_Zavareh_Lilja_Riedel_Bazargan_Harjani_Time_Encoded_Values_for_Highly_Efficient_Stochastic_Circuits.pdf Time-Encoded Values for Highly Efficient Stochastic Circuits]\n|- valign=\"top\"\n| '''authors''':\n| [[M. Hassan Najafi]], S. Jamali-Zavareh, [http://www.arctic.umn.edu/lilja.shtml David Lilja], [[Marc Riedel]], [http://people.ece.umn.edu/~kia Kia Bazargan] and<br>[http://people.ece.umn.edu/~harjani/ Ramesh Harjani]\n|- valign=\"top\"\n| '''appeared in''':\n| [http://ieeexplore.ieee.org/xpl/aboutJournal.jsp?punumber=92 IEEE Trans. on Very Large Scale Integration Systems],<br>Vol. 25, No. 5, pp. 1644–1657, 2017\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.ieee.org/conferences_events/conferences/conferencedetails/index.html?Conf_ID=33621 IEEE International Symposium on Circuits and Systems], 2017\n|}\n| width=\"70\" align=\"center\" |\n<span class=\"plainlinks\">\n[http://www.mriedel.ece.umn.edu/wiki/images/b/b0/Najafi_Jamali_Zavareh_Lilja_Riedel_Bazargan_Harjani_Time_Encoded_Values_for_Highly_Efficient_Stochastic_Circuits.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[//mriedel.ece.umn.edu/wiki/images/b/b0/Najafi_Jamali_Zavareh_Lilja_Riedel_Bazargan_Harjani_Time_Encoded_Values_for_Highly_Efficient_Stochastic_Circuits.pdf Paper]\n|}Please see our \"[[Papers,_Theses,_and_Presentations |Publications]]\" page for more of our papers on these topics.\n\n==Computing with Feedback==\n\n\"''A person with a new idea is a crank until the idea succeeds.''\" –– '''Mark Twain''' (1835–1910)\n\nThe 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. \n[[Image:cyclic-combinational-circuit.gif|center|thumb|none|550px|A circuit that has feedback and yet is combinational.]]\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Cyclic Boolean Circuits]]\n|- valign=\"top\"\n| '''authors''':\n| [[Marc Riedel]] and [http://paradise.caltech.edu/bruck.html Shuki Bruck]\n|- valign=\"top\"\n| '''appeared in''':\n| [http://www.elsevier.com/wps/find/journaldescription.cws_home/505609/description#description Discrete Applied Mathematics], Vol. 160, No. 13–14, pp. 1877–1900, 2011.\n\n|- valign=\"top\"\n| '''dissertation''':\n| 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).\n\n|- valign=\"top\"\n| '''presented at''':\n| [http://www2.dac.com/40th/index.html Design Automation Conference], Anahiem, CA, 2003<br>(winner of '''DAC Best Paper Award''').\n\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Riedel_Bruck_Cyclic_Boolean_Circuits.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Riedel_Cyclic_Combinational_Circuits.pdf | PhD Dissertation]]\n| align=\"center\" width=\"70\" | \n<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>\n<br> [http://mriedel.ece.umn.edu/files/Riedel_Cyclic_Combinational_Circuits.ppt Slides]\n|}\nPlease see our [[Papers,_Theses,_and_Presentations | Publications]] page for more of our papers on this topic.\n\n\n==Computing with Nanoscale Lattices==\n\n\"''Listen to the technology; find out what it\u2019s telling you.''\u201d –– '''Carver Mead''' (1934– )\n\nIn 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].\n{| align=\"center\"\n|\n[[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.]]\n|| \n|| [[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.]] \n|}\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" |'''title''':\n| width=\"500\" |[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Logic Synthesis for Switching Lattices]]\n|- valign=\"top\"\n| '''authors''':\n| [[Mustafa Altun]] and [[Marc Riedel]]\n|- valign=\"top\"\n| '''will appear in''':\n| [http://www.computer.org/portal/web/tc IEEE Transactions on Computers], 2011.\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.dac.com/47th/index.aspx Design Automation Conference], Anaheim, CA, 2010.\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/2/28/Altun_Riedel_Lattice-Based_Computation_of_Boolean_Functions.ppt Slides]\n|}\n\nThe 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. \n{| align=\"center\"\n|\n[[Image:nano-crossbar.gif|center|thumb|315px|A nanowire crossbar switch. \nThe connections between horizontal and vertical\nwires are FET-like junctions. When high or low voltages are applied to input nanowires, the\nFET-like junctions that cross these develop a high or low impedance, respectively.\n]]\n|| \n|| [[Image:percolation.gif|center|thumb|260.994x260.994px| In a switching network with defects, percolation can be exploited to produce robust Boolean functionality. ]]\n|}\nWe 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.\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" |'''title''':\n| width=\"500\" |[[Media:Altun_Riedel_Robust_Computation_through_Percolation_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Synthesizing Logic with Percolation in Nanoscale Lattices]]\n|- valign=\"top\"\n| '''authors''':\n| [[Mustafa Altun]] and [[Marc Riedel]]\n|- valign=\"top\"\n| '''appeared in''':\n| [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–30, 2011.\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.dac.com/46th/index.aspx Design Automation Conference], San Francisco, CA, 2009.\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/f/fe/Altun_Riedel_Neuhauser_Nanoscale_Digital_Computation_Through_Percolation.ppt Slides]\n|}\nPlease see our \"[[Papers,_Theses,_and_Presentations |Publications]]\" page for more of our papers on these topics.\n\n==Algorithms and Data Structures==\n\n\"''There are two kinds of people in the world: those who divide the world into two kinds of people, and those who don't.''\" –– '''Robert Charles Benchley''' (1889–1945)\n\nConsider 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] – <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. \n\nCircuit 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. \n{| align=\"center\"\n| [[Image:sat-squid.jpg|center|thumb|350px|A circuit construct for SAT-based verification.]]\n|| \n|| [[Image:squid.jpg|thumb|350px|A squid.]]\n|}\n{|\n| \n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf | Reduction of Interpolants For Logic Synthesis]]\n|- valign=\"top\"\n| '''authors''':\n| [[John Backes]] and [[Marc Riedel]]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.iccad.com The International Conference on Computer-Aided Design], San Jose, CA, 2010.\n|}\n| align=\"center\" width=\"70\" | \n<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>\n<br>[[Media:Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<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>\n<br> [http://mriedel.ece.umn.edu/wiki/images/0/00/Backes_Riedel_Reduction_Of_Interpolants_For_Logic_Synthesis.ppt Slides]\n|}\nPlease 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.)\n\n==Mathematics==\n\n\"''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.''\" –– '''Bertrand Russell''' (1872–1970)\n\n[[Image:xkcd_disciplines_by_purity.png|center|thumb|740x740px]]\n\n\nThe 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].\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| 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]]\n|- valign=\"top\" \n| '''authors''':\n| [[Weikang Qian]], [[Marc Riedel]], and [http://dms.umontreal.ca/Professeurs/rosenb/index.html Ivo Rosenberg]\n|- valign=\"top\"\n| '''appeared in''':\n| [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–463, 2011.\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[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>\n<br>\n[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Paper]]\n|}\n\nPlease see our \"[[Papers,_Theses,_and_Presentations |Publications]]\" page for more of our papers on this topic."
}
]
},
"535": {
"pageid": 535,
"ns": 0,
"title": "Research of Weikang Qian",
"revisions": [
{
"contentformat": "text/x-wiki",
"contentmodel": "wikitext",
"*": "(My research while at UMN.)\n\nMost digital circuits are designed to map ''deterministic'' inputs of zero and one to deterministic outputs of zero and one. In my research, I consider an alternative paradigm: digital circuits that operate on '''random Boolean variables'''. A random Boolean variable with probability ''p''\n(0 ≤ ''p'' ≤ 1) of being one represents a real-valued number ''p''. Thus, circuits can be viewed as constructs that accept real-valued probabilities as inputs and compute real-valued probabilities as outputs.\n\nI consider three topics pertaining to circuit synthesis in this probabilistic domain. The first is how to synthesize circuits that implement arbitrary arithmetic functions. The second is how to synthesize circuits that transform a set of source probabilities into target probabilities. The third is a special case of the second one, in which the source inputs are independent random Boolean variables with probability 0.5.\n\n<!--We studied several interesting applications that can be implemented by this stochastic paradigm. We first studied how to synthesize arbitrary arithmetic functions through logical computation on stochastic bit stream. We also consider the problem of transforming a set of source input probabilities into a target probability.-->\n\n== The Synthesis of Logical Computation on Random Boolean Variables ==\n\nLogical computation on random Boolean variables implements a function mapping real values into real values. For example, given an input probability ''x'', an inverter will have an output with probability 1-''x''<!--; given input probabilities ''x'' and ''y'', an AND gate will have an output with probability equal to the product of ''x'' and ''y''-->. In this work, I consider a general synthesis problem: how can we implement an arbitrary arithmetic function ''y''=''f''(''x'') by logical computation on random Boolean variables?\n\n[[File:Computation_Random_Boolean_Variable_Example.png|center|frame|Logical computation on random Boolean variables. (a): Given input probability ''x'', an inverter implements the function ''f''(''x'')=1-''x''. (b): A general synthesis problem is how to implement an arbitrary arithmetic function ''y''=''f''(''x'') by logical computation on random Boolean variables.]]\n\n=== Selected Publications ===\n\n{|\n| \n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Synthesizing Logical Computation on Stochastic Bit Streams]]\n|- valign=\"top\" \n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''' and [[Marc Riedel]]\n|- valign=\"top\"\n| '''submitted to''':\n| [http://cacm.acm.org/ Communications of the ACM '''Research Highlight'''].\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://cadbio.com/wiki/images/6/64/Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf | Paper]]\n|}\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf | An Architecture for Fault-Tolerant Computation with Stochastic Logic]]\n|- valign=\"top\"\n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''', [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]\n|- valign=\"top\" \n| '''appeared in''':\n| [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5601694 IEEE Transactions on Computers], vol. 60, no. 1, pp. 93-105, 2011.\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://cadbio.com/wiki/images/2/21/Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[[Media:Qian_Li_Riedel_Bazargan_Lilja_An_Architecture_for_Fault-Tolerant_Computation_with_Stochastic_Logic.pdf | Paper]]\n|}\n\n{|\n| \n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf | The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic]]\n|- valign=\"top\"\n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''' and [[Marc Riedel]]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.dac.com/events/eventdetails.aspx?id=77-37 Design Automation Conference], Anaheim, CA, 2008\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.ece.umn.edu/wiki/images/0/07/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>[[Media:Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt Slides]\n|}\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Uniform Approximation and Bernstein Polynomials with Coefficients in the Unit Interval]]\n|- valign=\"top\" \n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''', [[Marc Riedel]], and [http://dms.umontreal.ca/Professeurs/rosenb/index.html Ivo Rosenberg]\n|- valign=\"top\"\n| '''appeared in''':\n| [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-463, 2011.\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://cadbio.com/wiki/images/a/ab/Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[[Media:Qian_Riedel_Rosenberg_Uniform_Approximation_and_Bernstein_Polynomials_with_Coefficients_in_the_Unit_Interval.pdf | Paper]]\n|}\n\n==The Synthesis of Combinational Logic to Generate Probabilities==\n\nIn probabilistic computation that requires many different probability values, it is expensive to generate all of the probabilities directly from random sources. In this work, I demonstrate novel techniques for synthesizing combinational logic that transforms a set of source\nprobabilities into different target probabilities. \n<!--The problem I consider is: given a set ''S'' of ''n'' probabilistic inputs with probabilities ''p''<sub>1</sub>, ..., ''p''<sub><I>n</I></sub> of being one and a target probability ''q'', how can we synthesize a combinational circuit that takes inputs from the set ''S'' and produces an output with probability ''q'' of being one?-->\n\n[[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 of its input probabilities and each inverter performs a one-minus operation of its input probability.]]\n\n=== Selected Publications ===\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Transforming Probabilities with Combinational Logic]]\n|- valign=\"top\"\n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''', [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]\n|- valign=\"top\"\n| '''will appear in''':\n| [http://tcad.polito.it/ IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems].\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>\n[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf | Paper]]\n|}\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf | The Synthesis of Combinational Logic to Generate Probabilities]]\n|- valign=\"top\" \n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''', [[Marc Riedel]], [http://www.ece.umn.edu/users/kia/ Kia Bazargan], and [http://www.arctic.umn.edu/lilja.shtml David Lilja]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.iccad.com/events/eventdetails.aspx?id=106-5-C International Conference on Computer-Aided Design], San Jose, 2009\n<!--\n|- valign=\"top\"\n|\n|[http://www.sigda.org/iwls/iwls2009/ International Workshop on Logic and Synthesis], Berkeley, CA, 2009\n-->\n|- valign=\"top\"\n| \n| nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award'''\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://www.cctbio.ece.umn.edu/wiki/images/5/5d/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>[[Media:Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br> [http://cctbio.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]\n|}\n\n== Two-Level Logic Synthesis for Probabilistic Computation ==\n\nAssuming that we are given independent copies of probabilistic inputs with probability 0.5 of being one, how can we synthesize a ''two-level'' logic circuit that generates an arbitrary target output probability? This problem is equivalent to finding a Boolean function with ''m'' [[wikipedia:Canonical_form_(Boolean_algebra)#Minterms|minterms]] and having a sum-of-product expression with the minimum number of products. \n\n[[File:Karnaugh_Map.png|center|thumb|none|350px|The [[wikipedia:Karnaugh_map|Karnaugh maps]] of two different Boolean functions both containing 7 minterms. (a): The optimal sum-of-product expression contains 3 product terms. (b): The optimal sum-of-product expression contains 2 product terms. Figure (b) gives a Boolean function with the minimum number of products to cover 7 minterms.]]\n\n=== Selected Publications ===\n{|\n| \n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf |Two-Level Logic Synthesis for Probabilistic Computation]]\n|- valign=\"top\" \n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''' and [[Marc Riedel]]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://www.cctbio.ece.umn.edu/wiki/images/4/4c/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>[[Media:Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.pdf | Paper]]\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br> [http://cctbio.com/wiki/images/4/42/Qian_Riedel_Two_Level_Logic_Synthesis_for_Probabilistic_Computation.ppt Poster]\n|}\n\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf |Synthesizing Cubes to Satisfy a Given Intersection Pattern]]\n|- valign=\"top\" \n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''' and [[Marc Riedel]]\n|- valign=\"top\" \n| '''presented at''':\n| [http://www.sigda.org/iwls/iwls2010/ International Workshop on Logic and Synthesis], Irvine, CA, 2010\n|}\n| align=\"center\" width=\"70\" | \n<span class=\"plainlinks\">\n[http://www.cctbio.ece.umn.edu/wiki/images/2/2f/Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>[[Media:Qian_Riedel_Synthesizing_a_Set_of_Cubes_to_Satisfy_a_Given_Intersection_Pattern.pdf | Paper]]\n| align=\"center\" width=\"70\" |\n<span class=\"plainlinks\">[http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br> [http://cctbio.com/wiki/images/5/5b/Qian_Riedel_Synthesizing_Cubes_to_Satisfy_a_Given_Intersection_Pattern.ppt Slides]\n|}\n<!--== The Synthesis of Stochastic Circuits for Nanoscale Computation ==\n\nNanotechnology offers the promise of scaling beyond the current limit of silicon CMOS. However, many nanoscale constructs suffer from high defect rates. With self-assembly, there is often inherent randomness in the resulting topology or structure. Much effort is expended in controlling or eliminating such randomness. In contrast, we seek to ''exploit'' such randomness in computation.\n\n[[File:Nanowire_Crossbar_AND.png|center|thumb|550px|In a nanowire crossbar array, each vertical nanowire has a randomly located doping region (the red area in the figure). A vertical nanowire and a horizontal nanowire crossing the doping region of that vertical nanowire form a PMOS-like junction. We can build a ''shuffled'' AND based on such array. The shuffled AND randomizes the order of its inputs and implements the multiplication on the probabilities of ones at the input wire bundles.]]\n\n=== Selected Publications ===\n{|\n|\n{| style=\"background:#F0E68C\"\n|- valign=\"top\"\n| width=\"100\" | '''title''':\n| width=\"500\" | [[Media:Qian_Backes_Riedel_The_Synthesis_of_Stochastic_Circuits_for_Nanoscale_Computation.pdf | The Synthesis of Stochastic Circuits for Nanoscale Computation]]\n|- valign=\"top\"\n| '''authors''':\n| '''[[Weikang Qian|<span style=\"color:#000000\">Weikang Qian</span>]]''', [[John Backes]], and [[Marc Riedel]]\n|- valign=\"top\"\n| '''presented at''':\n| [http://www.sigda.org/iwls/iwls2007 International Workshop on Logic and Synthesis], San Diego, CA, 2007.\n|}\n| align=center width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.ece.umn.edu/wiki/images/6/6a/Qian_Backes_Riedel_The_Synthesis_of_Stochastic_Circuits_for_Nanoscale_Computation.pdf http://cctbio.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>\n<br>[[Media:Qian_Backes_Riedel_The_Synthesis_of_Stochastic_Circuits_for_Nanoscale_Computation.pdf | Paper]]\n| align=center width=\"70\" | \n<span class=\"plainlinks\">[http://cctbio.ece.umn.edu/files/Qian_Backes_Riedel_The_Synthesis_of_Stochastic_Circuits_for_Nanoscale_Computation.ppt http://cctbio.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>\n<br> [http://cctbio.ece.umn.edu/files/Qian_Backes_Riedel_The_Synthesis_of_Stochastic_Circuits_for_Nanoscale_Computation.ppt Slides]\n|}\n-->"
}
]
}
}
}
}