Difference between revisions of "Mustafa Altun"

From The Circuits and Biology Lab at UMN
Jump to navigationJump to search
Line 11: Line 11:


=== Self-Duality ===
=== Self-Duality ===
The problem of testing whether a monotone Boolean function in irredundant disjuntive normal form (IDNF) is self-dual is one of few problems in circuit complexity whose precise tractability status is unknown. We have focused on this famous problem. We have shown that monotone self-dual Boolean functions in IDNF do not have more variables than disjuncts. We have proposed an algorithm to test whether a self-dual Boolean function in IDNF with ''n'' variables and ''n'' disjuncts is self-dual. The algorithm runs in <math>O(n^4)</math> time.
The problem of testing whether a monotone Boolean function in irredundant disjuntive normal form (IDNF) is self-dual is one of few problems in circuit complexity whose precise tractability status is unknown. We have focused on this famous problem. We have shown that monotone self-dual Boolean functions in IDNF do not have more variables than disjuncts. We have proposed an algorithm to test whether a monotone Boolean function in IDNF with ''n'' variables and ''n'' disjuncts is self-dual. The algorithm runs in <math>O(n^4)</math> time.


{|
{|

Revision as of 19:37, 28 February 2012

Mustafa Altun.jpg

I am a Ph.D. candidate in the Dept. of Electrical and Computer Engineering at the University of Minnesota, Twin Cities Campus.

Current Research

I am pursuing research in the area of logic synthesis for emerging technologies. I also have a particular interest in combinatorics, more specifically hypergraphs.

Self-Duality

The problem of testing whether a monotone Boolean function in irredundant disjuntive normal form (IDNF) is self-dual is one of few problems in circuit complexity whose precise tractability status is unknown. We have focused on this famous problem. We have shown that monotone self-dual Boolean functions in IDNF do not have more variables than disjuncts. We have proposed an algorithm to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The algorithm runs in time.

title: A Study on Monotone Self-dual Boolean Functions
authors: Mustafa Altun and Marc Riedel
submitted  to: SIAM Journal on Discrete Mathematics, 2012.

Pdf.jpg
Paper

Switching Lattices

In his seminal Master's Thesis, 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 nanowire crossbar arrays, as molecular switch-based structures.

title: Logic Synthesis for Switching Lattices
authors: Mustafa Altun and Marc Riedel
will appear in: IEEE Transactions on Computers, 2011.

Pdf.jpg
Paper

title: Lattice-Based Computation of Boolean Functions
authors: Mustafa Altun and Marc Riedel
presented at: Design Automation Conference, Anaheim, CA, 2010.

Pdf.jpg
Paper

Ppt.jpg
Slides

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, arranged in a series/parallel configuration. This network implements the function .
               
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, .

Percolation for Robust Computation

We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of 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. This phenomenon is exploited to compute Boolean functions robustly, in the presence of defects.

title: Synthesizing Logic with Percolation in Nanoscale Lattices
authors: Mustafa Altun and Marc Riedel
will appear in: International Journal of Nanotechnology and Molecular Computation, 2011.

Pdf.jpg
Paper

title: Nanoscale Digital Computation Through Percolation
authors: Mustafa Altun, Marc Riedel, and Claudia Neuhauser
presented at: Design Automation Conference, San Francisco, CA, 2009.

Pdf.jpg
Abstract

Ppt.jpg
Slides

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").


Contact Information

  • Email Address: altu0006@umn.edu
  • Cell Phone: 612-978-2955
  • Address: 200 Union St. S.E., Room 4-136, Minneapolis, MN 55455