# 2016 Pat Goldberg Memorial Best Paper Awards

*Winning Papers Focus on Compressed Linear Algebraic Techniques for Machine Learning, Stochastic Neural Systems, Quantum Circuit Simulations, Real-valued Function Approximations, and Nanoscale Arrays*

Research papers in Computer Science, Electrical Engineering, and Mathematical Sciences, published in refereed conference proceedings and journals in 2016, were submitted by IBM Research authors worldwide to the Pat Goldberg Memorial 2016 Best Paper in CS, EE and Math Competition. From among these submissions, a team of domain experts nominated papers based on their technical significance (depth and breadth) and expected long-term impact. Top scientists representing the worldwide IBM Research Professional Interest Communities (PICs) reviewed the papers in late 2017 and chose these five winning papers.

__Compressed Linear Algebra for Large Scale Machine Learning__

**Authors**: Ahmed Elgohary (University of Maryland, College Park), Matthias Boehm (IBM Research - Almaden), Peter J. Haas (IBM Research - Almaden), Frederick R. Reiss (IBM Research - Almaden), Berthold Reinwald (IBM Research - Almaden)

**Published In:** PROCEEDINGS OF THE VLDB ENDOWMENT, Vol. 9, No. 12

**Abstract**: The paper introduces a novel compression approach to apply machine learning effectively on large data sets. The authors develop a compressed representation for matrices, as well as compressed linear algebra operations that work directly over the compressed matrix data. Together, these reduce the bandwidth required to perform computations, thus speeding performance dramatically. Compression techniques are developed for single columns in a matrix, and for “column grouping” techniques that capitalize on correlations between columns. In addition, the paper develops cache-conscious algorithms for matrix multiplication and other operations. Finally, the paper shows how to estimate the sizes of compressed matrices and to choose an effective compression strategy. Together, these techniques illustrate how database systems concepts can be adapted to great benefit in the machine learning space. The paper received the VLDB-16 best paper award.

__Stochastic phase-change neurons__

**Authors**: Tomas Tuma (IBM Research - Zurich), Angeliki Pantazi (IBM Research - Zurich), Manuel Le Gallo (IBM Research - Zurich, ETH Zurich), Abu Sebastian (IBM Research - Zurich), and Evangelos Eleftheriou (IBM Research - Zurich)

**Published In:** NATURE NANOTECHNOLOGY, 16 MAY 2016, DOI: 10.138/NNANO.2016.70

**Abstract**: This work demonstrates that chalcogenide-based phase-change materials can be used to create an artificial neuron in which the membrane potential is represented by the phase configuration of the nanoscale phase-change device. By exploiting the physics of reversible amorphous-to-crystal phase transitions, the authors show that the temporal integration of postsynaptic potentials can be achieved on a nanosecond timescale. In addition, the authors show that this is inherently stochastic because of the melt-quench-induced reconfiguration of the atomic structure occurring when the neuron is reset. The authors demonstrate the use of these phase-change neurons, and their populations, in the detection of temporal correlations in parallel data streams and in the sub-Nyquist representation of high-bandwidth signals.

__Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates__

**Authors**: Sergey Bravyi (IBM Thomas J. Watson Research Center) and David Gosset (California Institute of Technology)

**Published In:** PHYSICAL REVIEW LETTERS, 116, 250501, 20 JUNE 2016

**Abstract**: The authors provide an excellent classical algorithm that stretches the ability of a classical computer to emulate a quantum computer. The runtime of the algorithm is polynomial in the number of qubits and the number of Clifford gates in the circuit but exponential in the number of T gates. The exponential scaling is sufficiently mild that the algorithm can be used in practice to simulate medium-sized quantum circuits dominated by Clifford gates. To demonstrate the power of the proposed method, the authors performed a classical simulation of a hidden shift quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50 T gates. The proposed algorithm is highly relevant for benchmarking and verification purposes of early quantum computers, since it provides a way to test whether a quantum computer is performing as advertised, where such quantum computers cannot in practice be simulated by other means.

__Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas__

**Authors**: Vitaly Feldman (IBM Research - Almaden), Jan Vondrak (IBM Research - Almaden).

**Published In:** SIAM JOURNAL OF COMPUTING, 45(3), pp. 1129–1170, 2016.

**Abstract**: The paper studies the approximations of natural classes of real valued boolean functions by juntas - functions of a small number of variables. This is a well-studied problem and various results - notably Friedgut's theorem - have had applications ranging from computational learning to complexity. The paper provides optimal and near-optimal bounds for the size of juntas approximating the (large) class of submodular functions and the (larger) class of fractionally subadditive (XOS) functions. These functions arise naturally in game theory and machine learning and their junta-approximations are of considerable interest.

__Nanoscale lateral displacement arrays for the separation of exosomes and colloids down to 20 nm__

**Authors**: Benjamin H. Wunsch (IBM Thomas J. Watson Research Center), Joshua T. Smith (IBM Thomas J. Watson Research Center), Stacey M. Gifford (IBM Thomas J. Watson Research Center), ChaoWang ( IBM Thomas J. Watson Research Center), Markus Brink (IBM Thomas J. Watson Research Center), Robert L. Bruce (IBM Thomas J. Watson Research Center), Robert H. Austin (Princeton University), Gustavo Stolovitzky (IBM Thomas J. Watson Research Center, Icahn School of Medicine at Mount Sinai, New York), and Yann Astier (IBM Thomas J. Watson Research Center)

**Published In:** NATURE NANOTECHNOLOGY, 1 AUGUST 2016, DOI: 10.1038/NNANO.2016.134

**Abstract**: The paper describes the experimental demonstration and an efficient technology to rapidly sort, separate, and enrich promising biological biomarkers of scales as small as 20nm. One of the innovations of this technology is that it is a continuous flow “Lab-on-a-chip” microfluidics chip technology that has many advantages over traditional “batch” methods of separation. This paper opens the door to access on-chip separation of a rich set of biomaterials, including exosome vesicles and opening the potential for on-chip biomolecule separation and diagnostics using a scalable and manufacturable technology. Exosomes are of strong interest to the scientific community for non-invasive liquid biopsy. This technology paves the way for early detection of cancer, at stages where the treatment renders this disease curable.

Congratulations to all the winners. Special thanks to the IBM Research selection team: Venkat Chakravarthy, Ehud Karnin, Kostas Katrinis, Phokion Kolaitis, Dilip Krishnaswamy (committee chair), Tamiya Onodera, Anna Phan, Mark N Wegman, and Justin D Weisz

**Related links**

Pat Goldberg Memorial Best Paper Awards [previous award recipients]

Professional Interest Communities at IBM Research

*Last updated on July 10, 2018*