The goals of this project are in the development of new algorithms, analysis of theoretical properties, and implementation of hardware prototypes that compute approximate solutions to high-dimensional discrete programs. Before this project, it was commonly believed that approximate or relaxation-based methods for discrete programming exhibit prohibitive complexity, which prevents their deployment in practical systems or achieve poor solution quality. However, the reference algorithms and hardware designs developed in this project have demonstrated that relatively large discrete programs can be solved at high throughput, low area, and low power, while achieving best-in-class solution accuracy. Specifically, the PIs have developed three distinct algorithm frameworks for approximately solving a wide range of discrete program classes: (i) triangular approximate semidefinite relaxation (TASER), (ii) biconvex relaxation (BCR), and (iii) l-infinity-norm relaxation. In addition, theoretical results addressing convergence properties and solution quality have been devised. To demonstrate the efficacy of these algorithm frameworks in real-world applications, the PIs have developed reference very-large scale integration (VLSI) designs for next-generation wireless communication systems, including near-maximum-likelihood data detection, joint channel estimation and data detection, and precoding for low-resolution multi-antenna transmitters. These reference hardware designs achieve best-in-class throughput, area, and power, while surpassing the performance of existing algorithms in wireless systems. Furthermore, the algorithm frameworks developed in this project have been applied to a range of applications in other fields, such as imaging, signal processing, computer vision, and machine learning.

Broader Impacts

The PIs have been actively collaborating with industry partners in the areas of field-programmable gate arrays and wireless network infrastructure. In the ever-growing area of wireless systems, the achieved results have the potential to enable higher data rates or more devices (or sensors) connected to the base stations. In addition, some of the developed methods enables base-station designs that consume orders of magnitude lower power than traditional solutions. On the mobile handheld side, the developed methods enable the solution to combinatorial data detection problems at significantly lower power and with fewer errors; this has an immediate impact on a society that becomes increasingly interested in energy efficiency computing. The achieved results have also potential benefit for people in areas of underserved communication infrastructure as they enable reliable communication over longer distances.  

The PIs have integrated undergraduate students directly into the research of this project and have included results in new communications and optimization courses at Cornell University and University of Maryland. In addition, the project outreach activities culminated in a week-long research activity for underrepresented minority (URM) high-school students under Cornell?s CATALYST Academy, in which the students were developing an acoustic wireless communication system.

Last Modified: 01/10/2020
Modified by: Christoph Studer