SubsidieMeestersLocal-to-global Expansion and PCPs
This project aims to advance the study of Probabilistically Checkable Proofs using high-dimensional expansion theory to develop simpler PCP constructions and enhance local-to-global encoding understanding.
Projectdetails
Introduction
This proposal aims to delve further into the study of Probabilistically Checkable Proofs (PCPs), a cornerstone of modern theoretical computer science, that exhibits some of the most powerful local to global behavior. Any NP proof can be written in a format that is locally testable, meaning that local pieces of the proof imply very rich global structure. This theory is strongly tied to hardness of approximation and has significant applications in cryptography. A major goal is to develop simpler and more efficient PCP constructions, with better parameters, as well as to deepen our understanding of robust encodings with local to global features, such as PCPs.
Methodology
The main methodology of this exploration will be through harnessing the power of the beautiful emerging theory of high-dimensional expansion (HDX). Generalizing the concept of expander graphs to higher dimensions, HDX emerges as an exciting cross-disciplinary theory with roots in:
- Group theory
- Number theory
- Algebraic topology
- Combinatorics
- Theoretical computer science
The HDX theory is characterized by a local-to-global principle, which allows inferences about the global structure based on local link properties. This principle bears significant potential for areas like property testing and it has already shown its power with the construction of C^3 locally testable codes. As these are very closely connected to PCPs, we seek to harness HDX towards advancing our understanding of more general local-to-global encodings, and potentially paving the way for novel PCP constructions.
Research Directions
The research directions outlined in this proposal cover a wide array of goals, including:
- The exploration of the HDX theory
- The construction of new PCPs
- Inapproximability
- The creation of novel error-correcting codes
These directions seek to bridge various areas of mathematics and computer science, promising to contribute significantly to the field and open up new horizons for further research and applications.
Financiële details & Tijdlijn
Financiële details
| Subsidiebedrag | € 2.105.840 |
| Totale projectbegroting | € 2.105.840 |
Tijdlijn
| Startdatum | 1-1-2025 |
| Einddatum | 31-12-2029 |
| Subsidiejaar | 2025 |
Partners & Locaties
Projectpartners
- WEIZMANN INSTITUTE OF SCIENCEpenvoerder
Land(en)
Vergelijkbare projecten binnen European Research Council
| Project | Regeling | Bedrag | Jaar | Actie |
|---|---|---|---|---|
Parameterized Complexity Through the Lens of Path ProblemsThis project aims to unify the theory of parameterized path problems by connecting various mathematical fields to develop efficient algorithms and answer longstanding questions in NP-hard problem complexity. | ERC Starting... | € 1.499.821 | 2022 | Details |
Concentration and threshold phenomena in random graphs and hypergraphsThis project aims to advance the enumeration of large structures in random graphs and hypergraphs under local constraints, addressing key open problems in combinatorics and probability theory. | ERC Consolid... | € 1.621.875 | 2022 | Details |
CertiFOX: Certified First-Order Model ExpansionThis project aims to develop methodologies for ensuring 100% correctness in combinatorial optimization solutions by providing end-to-end proof logging from user specifications to solver outputs. | ERC Consolid... | € 1.999.928 | 2024 | Details |
New Frontiers in Information-Theoretic Secure ComputationThis project aims to enhance the understanding and efficiency of information-theoretic secure computation through improved secret sharing, secure reductions, and optimized protocols, impacting cryptography and theoretical computer science. | ERC Advanced... | € 2.113.125 | 2023 | Details |
Algebraic Formula Lower Bounds and ApplicationsThis project aims to establish lower bounds for algebraic formulas and improve Polynomial Identity Testing algorithms by leveraging structural and algebraic techniques in theoretical computer science. | ERC Consolid... | € 1.869.055 | 2024 | Details |
Parameterized Complexity Through the Lens of Path Problems
This project aims to unify the theory of parameterized path problems by connecting various mathematical fields to develop efficient algorithms and answer longstanding questions in NP-hard problem complexity.
Concentration and threshold phenomena in random graphs and hypergraphs
This project aims to advance the enumeration of large structures in random graphs and hypergraphs under local constraints, addressing key open problems in combinatorics and probability theory.
CertiFOX: Certified First-Order Model Expansion
This project aims to develop methodologies for ensuring 100% correctness in combinatorial optimization solutions by providing end-to-end proof logging from user specifications to solver outputs.
New Frontiers in Information-Theoretic Secure Computation
This project aims to enhance the understanding and efficiency of information-theoretic secure computation through improved secret sharing, secure reductions, and optimized protocols, impacting cryptography and theoretical computer science.
Algebraic Formula Lower Bounds and Applications
This project aims to establish lower bounds for algebraic formulas and improve Polynomial Identity Testing algorithms by leveraging structural and algebraic techniques in theoretical computer science.