skip to main content
  • ACM Home
  • ACM A.M. Turing Award
  • Turing 50
  • Digital Library
  • CACM
  • Queue
  • TechNews
ACM Logo
ACM Logo
ACM recognizes excellence
  • Home
  • Award Recipients
  • Contact Us
Home Award Recipients Contact Us
  • ACM Awards
    • Awards Home
      • Spotlight on Turing Laureates
      • ACM A.M. Turing Award
      • ACM Prize in Computing
      • ACM Charles P. "Chuck" Thacker Breakthrough in Computing Award
      • ACM Frances E. Allen Award
      • ACM Luiz André Barroso Award
      • ACM Distinguished Service Award
      • ACM Doctoral Dissertation Award
      • ACM-IEEE CS Eckert-Mauchly Award
      • ACM Grace Murray Hopper Award
      • ACM Gordon Bell Prize
      • ACM Gordon Bell Prize for Climate Modelling
      • International Science and Engineering Fair
      • ACM Paris Kanellakis Theory and Practice Award
      • ACM Karl V. Karlstrom Outstanding Educator Award
      • ACM-IEEE CS Ken Kennedy Award
      • ACM Eugene L. Lawler Award
      • ACM-IEEE CS George Michael Memorial HPC Fellowships
      • ACM AAAI Allen Newell Award
      • Outstanding Contribution to ACM Award
      • ACM Policy Award
      • ACM Presidential Award
      • SIAM/ACM Prize in Computational Science and Engineering
      • ACM Software System Award
      • ACM Athena Lecturer Award
      • ACM/CSTA Cutler-Bell Prize for High School Computing
      • Sponsors of ACM Awards

    • About ACM Awards

      Giving Credit where Credit Is Due

      ACM recognizes excellence through its eminent awards for technical and professional achievements and contributions in computer science and information technology. It also names as Fellows and Distinguished Members those members who, in addition to professional accomplishments, have made significant contributions to ACM's mission. ACM awards recognize achievements by young computing professionals, educators, theoretical computer scientists, software systems innovators, and pioneers who have made humanitarian and cross-discipline contributions.

    • 2024 Nobel Prize in Physics recipient Geoffrey Hinton
      Geoffrey Hinton Awarded the 2024 Nobel Prize in Physics
      Image promoting the ACM Luiz André Barroso Award
      ACM Announces Luiz André Barroso Award
      acm-fellows-member-badge.jpg
      ACM Names 2023 Fellows
  • Advanced Member Grades
    • Advanced Grades of Membership
      • ACM Fellows
      • ACM Distinguished Members
      • ACM Senior Members
      • ACM Fellows FAQ
      • ACM Distinguished Members FAQ
      • ACM Senior Members FAQ
      • ACM Fellows Committee
      • ACM Distinguished Member Committee

    • ACM Advanced Grades of Membership

      The ACM Advanced Grades of Membership program recognizes the achievements of ACM members through all stages of their career.

    • acm-fellows-member-badge.jpg
      ACM Names 2023 Fellows
      acm-distinguished-member-badge.jpg
      ACM Names 2023 Distinguished Members
  • SIG Awards
    • About SIG Awards
      • SIGACCESS
      • SIGACT
      • SIGAda
      • SIGAI
      • SIGAPP
      • SIGARCH
      • SIGBED
      • SIGBio
      • SIGCAS
      • SIGCHI
      • SIGCOMM
      • SIGCSE
      • SIGDA
      • SIGDOC
      • SIGEcom
      • SIGEVO
      • SIGIR
      • SIGGRAPH
      • SIGHPC
      • SIGKDD
      • SIGLOG
      • SIGMETRICS
      • SIGMICRO
      • SIGMIS
      • SIGMM
      • SIGMOBILE
      • SIGMOD
      • SIGOPS
      • SIGPLAN
      • SIGSAC
      • SIGSAM
      • SIGSIM
      • SIGSOFT
      • SIGUCCS
      • SIGWEB

    • About SIG Awards

      ACM's Special Interest Groups (SIGs) regularly cite outstanding individuals for their contributions in more than 30 distinct technological fields.

  • Regional Awards
    • About Regional Awards
      • ACM India Doctoral Dissertation
      • ACM India Early Career Researcher
      • ACM India Outstanding Contributions in Computing by a Woman
      • ACM India Outstanding Contribution to Computing Education
      • IPSJ/ACM Award for Early Career Contributions to Global Research
      • CCF-ACM Award for Artificial Intelligence

    • About ACM Regional Awards

      ACM recognizes the contributions of individuals working primarily within specific regions of the world through awards given by its regional councils, and through partnerships with international societies.

    • siddharth-barman.jpg
      ACM India ECR 2023 Award
      nutan-limaye.jpg
      ACM India OCCW 2023 Award
      OCCE 2024 award recipient Meenakshi D'Souza
      ACM India OCCE 2024 Award
  • Nominations
    • Award Nominations
      • ACM A.M. Turing Award
      • ACM Prize in Computing
      • ACM Charles P. "Chuck" Thacker Breakthrough in Computing Award
      • ACM Frances E. Allen Award
      • ACM Luiz André Barroso Award
      • ACM Distinguished Service Award
      • ACM Doctoral Dissertation Award
      • ACM-IEEE CS Eckert-Mauchly Award
      • ACM Gordon Bell Prize
      • ACM Grace Murray Hopper Award
      • ACM Paris Kanellakis Theory and Practice Award
      • ACM Karl V. Karlstrom Outstanding Educator Award
      • ACM-IEEE CS Ken Kennedy Award
      • ACM Eugene L. Lawler Award
      • ACM-IEEE CS George Michael Memorial HPC Fellowships
      • Outstanding Contribution to ACM Award
      • ACM AAAI Allen Newell Award
      • ACM Policy Award
      • SIAM/ACM Prize in Computational Science and Engineering
      • ACM Software System Award
      • ACM Athena Lecturer Award
      • ACM/CSTA Cutler-Bell Prize in High School Computing
      • ACM Fellows
      • ACM Distinguished Members
      • ACM Senior Members

    • Awards Nominating Process

      How to Nominate

      Award nominations deadlines occur throughout the year, with a heavy concentration in January. Please refer to the Nomination Process page for each award, which includes not only information about the deadline but also guidance for preparing each type of nomination.  ACM's conflict-of-interest guidelines apply to all award nominations.

    • acm-w-rising-star-award.jpg
      Call for ACM-W Rising Star Award Nominations
      og-awards.jpg
      ACM Honors & Ethics
  • Honors and Ethics
    • Policy for Honors Conferred by ACM
      • Policies and Procedures for Honors Conferred by ACM

    • ACM Honors and Ethics

      ACM formally recognizes individuals for significant contributions to the field, ACM, or its interests. ACM expects individuals it honors to abide by the ACM Code of Ethics and Professional Conduct. Learn about ACM's policies and procedures for integrating expectations of ethical behaviour and ACM Awards.

    • acm-w-rising-star-award.jpg
      Call for ACM-W Rising Star Award Nominations
      og-awards.jpg
      ACM Honors & Ethics
  • Awards Committees
    • ACM Awards Committee
      • ACM A.M. Turing Award Committee
      • ACM Prize in Computing Committee
      • ACM Charles P. "Chuck" Thacker Breakthrough in Computing Committee
      • ACM Frances E. Allen Award
      • ACM Distinguished Service Award Committee
      • ACM Doctoral Dissertation Award Committee
      • ACM-IEEE CS Eckert Mauchley Award Committee
      • ACM Gordon Bell Prize Committee
      • ACM Grace Murray Hopper Award Committee
      • ACM Paris Kanellakis Theory and Practice Award Committee
      • ACM Karl V. Karlstrom Outstanding Educator Award Committee
      • ACM-IEEE CS Ken Kennedy Award Committee
      • ACM Eugene L. Lawler Award Committee
      • ACM-IEEE CS George Michael Memorial HPC Fellowships Committee
      • ACM AAAI Allen Newell Award Committee
      • Outstanding Contribution to ACM Award Committee
      • ACM Policy Award Committee
      • SIAM/ACM Prize in Computational Science and Engineering Committee
      • ACM Software System Award Committee
      • ACM Athena Lecturer Award Committee
      • ACM India Doctoral Dissertation Award Committee
      • ACM Fellows Committee
      • ACM Distinguished Member Committee
      • ACM Senior Member Committee
      • Conflict of Interest Guidelines

    • About ACM Awards Committees

      At the core of the ACM Awards program is a dedicated group of volunteers who serve on the committees of the ACM Awards to recognize individuals for their excellence in the computing fields

    • awards-ctte-co-chairs.jpg
  • Establishing an Award
    • Policies and Guide for Establishing an ACM Award
      • ACM Publications Board Guidelines for Establishing a Best Paper Award for ACM Periodicals

    • Policies and Guide

      ACM welcomes proposals for the establishment of new awards, to recognize contributions based on merit, service, or for an outstanding paper.

    • acm-w-rising-star-award.jpg
      Call for ACM-W Rising Star Award Nominations
      og-awards.jpg
      ACM Honors & Ethics
  • Home
  • Award Recipients
  • Dieter van Melkebeek

Dieter van Melkebeek

Digital Library
  • ACM Doctoral Dissertation Award (1999)

ACM Doctoral Dissertation Award

USA - 1999

citation

For his dissertation, "Randomness and Completeness in Computational Complexity."

  • About ACM
  • About ACM
  • Volunteer
  • Membership
  • Join ACM
  • Renew My Membership
  • Membership Options
  • Membership Benefits
  • MyACM Sign In
  • Publications
  • About Publications
  • Digital Library
  • Submit a Paper
  • Chapters
  • Chapter Admin Interface
  • Chapter Activities Calendar
  • Start a Chapter
  • Awards
  • About ACM's Awards
  • Conferences
  • ACM's Conferences
  • Code of Ethics
  • ACM's Code of Ethics
  • Enforcement Procedures
  • Media Center
  • ACM Media Center
ACM Logo
  • Facebook logo
  • Twitter logo
  • LinkedIn logo
  • Reddit
  • YouTube logo
  • Instagram
  • Flickr
  • Mastodon
  • Home
  • Sitemap
  • Contact Us
  • Member Service
  • Privacy Policy
  • Accessibility
  • Cookie Declaration
  • Copyright © 2024, ACM, Inc