Call for Papers: CCC 2025

Submission Deadline

Friday, February 7, 2025, 23:59 AoE

Scope

The conference seeks original research papers in all areas of computational complexity theory, studying the absolute and relative power of computational models under resource constraints. We welcome contributions from all topics with connections to or motivated by questions in complexity theory, broadly construed. We especially encourage submissions that address complexity-theoretic issues in complexity-adjacent areas such as coding theory, cryptography, game theory, learning, logic and privacy.

Possible topics include but are not limited to:

• Complexity classes
• Reducibility and completeness
• Circuit complexity
• Communication complexity
• Algebraic complexity
• Proof complexity
• Complexity in other concrete computational models
• Interactive and probabilistic proof systems
• Logic and descriptive complexity
• Pseudorandomness and derandomization
• Average case complexity
• Quantum computation
• Parametrized complexity
• Fine-grained complexity
• Complexity-theoretic aspects of:
  • coding theory
  • cryptography
  • optimization (including inapproximability, continuous optimization)
  • property testing
  • streaming and sublinear computation
  • distributed computation
  • game theory
  • machine learning
  • privacy

Submission

Deadlines

• Submission Deadline: Friday, February 7, 2025, 23:59 AoE
• Notification of Acceptance: Friday, May 2, 2025
• Camera-ready Copy Due: End of May, 2025

Submission Server

Papers must be submitted electronically via the submission server: ccc2025.hotcrp.com

Format

• Submissions should start with a title page consisting of the title of the paper and an abstract of 1-2 paragraphs summarizing the paper's contributions.
• A submission must contain within its first 10 pages a clear presentation of the merits of the paper, including discussion of its importance, prior work, and an outline of key technical ideas and methods used to achieve the main claims.
• Material other than the abstract, references, and the first 10 pages is considered supplementary and will be read at the committee's discretion.
• Submissions should include proofs of all central claims.
• The submission should be in single-column format, use at least 11-point font, at least 1-inch margins, and at least single-spacing between lines. Submissions deviating significantly from these guidelines risk rejection without consideration of their merits.
• Instructions for formatting camera-ready versions will be communicated to the authors of accepted papers.

Review Process

The conference will employ a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. Authors' names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors are encouraged to post their papers to arXiv/ECCC/IACR etc. Important references should not be omitted or anonymized.

Additional Remarks

Authors may optionally send a short email to the program committee (PC) chair at ccc2025chair@gmail.com containing any additional remarks for the PC. Submissions involving PC members are not allowed.

Conflict of Interest (COI)

PC members and reviewers are expected to recuse themselves from evaluating submissions if they have a conflict of interest (e.g., thesis advisor, close collaborator, recent shared affiliation). Authors can write to the PC chair at ccc2025chair@gmail.com if there is a COI that may not be covered.

Simultaneous Submission Policy

Material previously published or scheduled for publication prior to September 2025, or simultaneously submitted to another conference with published proceedings, will not be considered.

Confidentiality

All submissions will be treated as confidential and disclosed only to the committee and their sub-referees.

Publication

Online Posting

Authors are encouraged to post full versions of their submissions in a freely accessible on-line repository such as the Electronic Colloquium on Computational Complexity (ECCC) or the arXiv.

Proceedings

The conference proceedings will be published under a Creative Commons BY license in the Leibniz International Proceedings in Informatics (LIPIcs) series. Publication in the proceedings does not preclude subsequent journal publication.

Presentation

Authors of accepted papers are expected to present their work at the conference. Time allocations for presentations will be between 15 and 45 minutes.

Awards

• EATCS Luca Trevisan award for the CCC best student paper: Awarded to the best paper written solely by one or more students. Authors must indicate eligibility via the submission page.
• Best paper award: Awarded to the best paper submitted. Full versions of these papers may be invited for submission to the Journal of the ACM.

Special Journal Issue

The program committee will invite full versions of a select number of conference submissions to a special issue of the journal Computational Complexity.

Conference Information

• Dates: Tuesday, August 5 to Friday, August 8, 2025
• Location: Toronto, Canada
• Travel Allowances: Travel allowances will be offered to students and post-doctoral fellows. More information will be available on the conference webpage.
• Visas: A visa for Canada may be needed for some citizens. Please contact your local Canadian consulate as soon as possible and the local arrangements committee if you need a letter to obtain your visa.
• Code of Conduct: CCC 2025 is a participant in the SafeTOC initiative and is committed to providing an environment free of discrimination and harassment.

Program Committee

• Paul Beame, University of Washington
• Anna Gál, University of Texas at Austin
• Sumegha Garg, Rutgers University
• Joshua Grochow, University of Colorado Boulder
• Shuichi Hirahara, National Institute of Informatics
• Holger Dell, Goethe-Universität Frankfurt and IT University of Copenhagen
• Igor Carboni Oliveira, University of Warwick
• Amir Shpilka, Tel Aviv University
• Makrand Sinha, University of Illinois at Urbana-Champaign
• Srikanth Srinivasan (Chair), University of Copenhagen and IIT Bombay
• Avishay Tal, University of California Berkeley
• Madhur Tulsiani, Toyota Technological Institute at Chicago

Local Arrangements Committee

• Swastik Kopparty (Chair), University of Toronto
• Benjamin Rossman, Duke University

Board of Trustees

• Amit Chakrabarti, Dartmouth College
• Mahdi Cheraghchi, University of Michigan
• Valentine Kabanets, Simon Fraser University
• Antonina Kolokolova, Memorial University of Newfoundland
• Nutan Limaye, IT-University of Copenhagen
• Shachar Lovett (President), University of California San Diego
• Raghu Meka, University of California Los Angeles
• Susanna de Rezende, Lund University
• Benjamin Rossman, Duke University
• Shubhangi Saraf, University of Toronto

Questions?

Please contact Srikanth Srinivasan at ccc2025chair@gmail.com.