Applicable and Computational Algebra Lab

Research

 ACA Lab Research Topics Publications ADM Seminar Resources

Coding Theory

Algebraic Geometry Codes An introduction to the first research area.
Results and Papers

Fast Decoding Algorithms for Algebraic Codes An introduction to the research area.
Results and Papers

Good Codes from Number Fields and Towers of Function Fields An introduction to the research area.
Results and Papers

Groebner Bases and Linear Codes An introduction to the research area.
Results and Papers

Low-Density Parity-Check Codes An introduction to the research area.
Results and Papers

Computational Algebra

Irreducibility and Factorization of Polynomials Factoring polynomials is important in algebra and number theory and is a crucial step in computing primary decomposition. It is a basic routine in most computer algebra systems (e.g. Maple, Mathematica, Magma), and has been extensively studied in the past few decades by mathematicians and computer scientists. While many dramatic progresses have been made, this research area is still active today due its fundamental importance in computational algebra.
Results and Papers

Primary Decomposition

There is a rich literature for primary decomposition. While computability issues are addressed in the early works (e.g. Hermann (1926) and Seidenberg (1984)), efficient algorithms are proposed only quite recently, see for example the papers due to Gianni, Trager and Zacharias (1988), Eisenbud, Huneke and Vasconcelos (1992), Shimoyama and Yokoyama (1992), and Steel (2005). Decker, Greuel and Pfister (1998) give an excellent survey of algorithms for primary decomposition, and their computer experiments on 34 benchmark examples indicate that, quoting from their paper, ... there is no unique strategy for the computation of primary decompositions'' and ... providing efficient algorithms for primary decomposition of an ideal $I \subset K[x_1,\ldots,x_n]$, $K$ a field, is also a difficult task and still one of the big challenges for computational algebra and computational algebraic geometry''. This remains to be true today!

Our research goal is to study more efficient algorithms for primary decomposition.

Papers and Results

Groebner Bases and Solving Polynomial Systems An introduction to the first research area.
Results and Papers

Numerical Algorithms for Solving Polynomial Systems An introduction to the first research area.
Results and Papers

Computing Integral Closures of Rings An introduction to the first research area.
Results and Papers

Computation of de Rham Cohomology An introduction to the first research area.
Results and Papers

Computational Biology

Systems Biology The essence of a system lies in its dynamics that can not be described merely by enumerating the components of the system. The field of systems biology aims at system-level understanding of biological systems, namely their functional activity. Quantum advances in biological measurement technology have created the need for computational and analytical means in order to utilize high-throughput measurements. Mathematical modeling is a natural tool to fulfill this need. Mathematical models provide generalization through abstraction, for instance, a gene regulatory network is described in terms of equations. Their formal study allows us to investigate generic properties and to test hypotheses. Perhaps equally importantly, the modeling process itself teaches us a lot about the functional activity of the system and the dynamic interactions of its components. The natural collaboration between systems biology and mathematics has given rise to a large array of powerful modeling methods. We are particularly interested in using polynomial dynamical systems over finite fields.
Results and Papers

Reverse Engineering of Gene Regulatory Networks Informally, reverse engineering is the process of discovering the behavior and connectivity of parts of a system, given observations of the system over time. Local behavior of a node in a system, when described in relation to other nodes, may give rise to other relationships or interactions between them. Therefore, reconstructing local interactions may lead to identification of global, system-level behavior. We focus on the reverse engineering of biochemical systems using discrete models, where the models are discrete-time discrete-state dynamical systems.
Results and Papers

Discrete Dynamical Systems: Theory and Modeling A discrete dynamical system consists of a system of finitely many nodes and each nodes takes values from a finite set, called states. The system evolves over time. The time step is discrete and the value of each node at the next time step is determined by the current states of all the nodes via some transition functions. When the states of each node take values from a finite field, all transition functions are polynomials. Systems comprised of such transition functions are called polynomial dynamical systems. Many biological networks can be viewed as discrete dynamical systems due to their discrete threshold operation mode. We study the theoretical aspects of discrete dynamical systems and their application to gene regulatory networks from deterministic and stochastic point of view.
Results and Papers

Compressive Sensing, Image Reconstruction and Coding Theory It's now well understood that sampling at the Nyquist rate isn't strictly necessary if the signal is sparse in some domain. One can sample non-adaptively and proceed to recover an approximation to the original signal off-line. The easiest method to describe is to find the sparsest signal (vector or image) that is consistent with the measured data. This brute force, that of minimizing a Hamming distance as above, algorithm is quite intractable, so other approaches have been shown to perform quite well. When the above algorithm is relaxed slightly, we are able to use Linear Programming. In addition, several greedy algorithms perform very well. We would like to apply some of the methods of Coding Theory to provide other options for recovering the vector.

Computational Number Theory

Finite Fields An introduction to the first research area.
Results and Papers

Point Counting on Curves An introduction to the first research area.
Results and Papers

Factoring Integers and Number Fields An introduction to the first research area.
Results and Papers

Discrete Logarithms in Finite Fields and on Elliptic Curves An introduction to the first research area.
Results and Papers

Cryptography

Multivariate Public-key Cryptosystems An introduction to the first research area.
Results and Papers

Coding Theory in Cryptography An introduction to the first research area.
Results and Papers

Secure Computation and Linear Codes An introduction to the first research area.
Results and Papers

 ACA Lab Research Topics Publications ADM Seminar Resources