Computational Complexity Conference

CCC'25: Call for Papers

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: Papers must be submitted electronically via submission server here, and received by Friday, February 7, 2025, 23:59 AoE. Notification of acceptance will be sent by Friday, May 2, 2025, and final camera-ready copies of accepted papers will be due end of May, 2025.

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 (similar to the content of a brief oral presentation). There is no bound on the total length of a submission, but material other than the abstract, references, and the first 10 pages is considered as 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.

The conference will employ a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. In particular, authors’ names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. (Author and institution information will be uploaded separately on the submission site.) The purpose of this double-blind process is to help PC members and external reviewers come to a judgment about the paper without unconscious bias, and is not intended to make it impossible for them to discover who the authors are. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, important references should not be omitted or anonymized. In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may (and are in fact encouraged to) post their papers to arXiv/ECCC/IACR etc.

Additional remarks: In addition to the submission, authors may optionally send a short email to the program committee (PC) chair at ccc2025chair@gmail.com containing any additional remarks for the PC, such as the relationship with independent/concurrent work, differences from prior versions, conflict of interest statements, or clarifications concerning prior reviews of the work. Submissions involving PC members are not allowed.

Conflict of interest: We expect PC members and reviewers to recuse themselves from the evaluation of any submission, if they would not be able to give an objective opinion due to some conflict of interest (COI). Some examples why a COI may arise are being a thesis advisor, being an immediate family member or close friend, sharing a recent institutional affiliation or being a close collaborator. Any author may write to the PC chair at ccc2025chair@gmail.com if there is a COI that may not be covered by the above measure, such as significant interactions that would suggest the inability to assess a paper objectively. They need only give the names and affiliations of the people with whom a COI exists; no explanation is required. The COI will be held in confidence by the PC chair.

Simultaneous submission policy: Material which has been previously published in a journal or another conference proceedings, or which is scheduled for publication prior to September 2025, will not be considered for acceptance. Simultaneous submission of the same or essentially the same material to another conference with published proceedings is not allowed.

Confidentiality: All submissions will be treated as confidential, and will only be disclosed to the committee and their chosen 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 or the arXiv. It is hoped that authors of accepted papers will make full versions of their papers publicly available by the camera-ready deadline.

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 conference proceedings does not preclude subsequent journal publication.

Presentation: Authors of accepted papers are expected to present their work at the conference. The program committee will determine time allocations for presentations (between 15 and 45 minutes).

Awards

EATCS Luca Trevisan award for the CCC best student paper: This award will be given to the best paper written solely by one or more students as judged by the program committee. A paper is eligible if all authors are full-time students on the day of the submission deadline. Authors should indicate their eligibility by using the check-box for this on the submissions page. The program committee may decline to make the award or may split it among several papers. Funding for the best student paper award is provided by EATCS.

Best paper award: This award will be given to the best paper submitted to the conference as judged by the program committee. The program committee may decline to make the award or may split it among two or more papers. Full versions of the papers chosen by the program committee to receive the best paper award will 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 and location: The conference will be held from Tuesday, August 5 to Friday, August 8, 2025 in Toronto, Canada. The details of the conference format will be posted in due course.

Travel allowances: In order to defray the costs of attending the conference, travel allowances will be offered to students and post-doctoral fellows. More information will be made available on the conference webpage in due time.

Visas: A visa for Canada may be needed for attending the conference, e.g., for citizens of China, India, and Russia. See the visa website of the Canadian government for the exact rules for short-term stay visas. If a visa is needed, please get in touch with your local Canadian consulate as soon as possible; the whole process may take several months. Feel free to contact 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. The open exchange of ideas and the freedom of thought and expression are central to the aims and goals of CCC. These require an environment that recognizes every person and group's inherent worth; fosters dignity, understanding, and mutual respect; and embraces diversity. The CCC'25 organizers are committed to providing an environment free of discrimination and harassment and expect all participants to honor that commitment.

Program Committee

Local Arrangements Committee

Board of Trustees

Questions?

Please contact Srikanth Srinivasan.

[Last modified: December 10, 2024 20:40:31]