Search dblp for Publications

export results for "worst-case hardness"

 download as .bib file

@article{DBLP:journals/iacr/AggarwalMV24,
  author       = {Divesh Aggarwal and
                  Leong Jin Ming and
                  Alexandra Veliche},
  title        = {Worst-Case to Average-Case Hardness of {LWE:} {A} Simple and Practical
                  Perspective},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {603},
  year         = {2024}
}

@inproceedings{DBLP:conf/colt/Tiegel23,
  author       = {Stefan Tiegel},
  title        = {Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice
                  Problems},
  booktitle    = {{COLT}},
  series       = {Proceedings of Machine Learning Research},
  volume       = {195},
  pages        = {3029--3064},
  publisher    = {{PMLR}},
  year         = {2023}
}

@article{DBLP:journals/eccc/LiuP23,
  author       = {Yanyi Liu and
                  Rafael Pass},
  title        = {On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov
                  Complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR23-103}},
  year         = {2023}
}

@article{DBLP:journals/iacr/LiuP23,
  author       = {Yanyi Liu and
                  Rafael Pass},
  title        = {On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov
                  Complexity},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {1086},
  year         = {2023}
}

@inproceedings{DBLP:conf/innovations/0001HV22,
  author       = {Lijie Chen and
                  Shuichi Hirahara and
                  Neekon Vafa},
  title        = {Average-Case Hardness of {NP} and {PH} from Worst-Case Fine-Grained
                  Assumptions},
  booktitle    = {{ITCS}},
  series       = {LIPIcs},
  volume       = {215},
  pages        = {45:1--45:16},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2022}
}

@article{DBLP:journals/corr/abs-2207-14030,
  author       = {Stefan Tiegel},
  title        = {Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice
                  Problems},
  journal      = {CoRR},
  volume       = {abs/2207.14030},
  year         = {2022}
}

@article{DBLP:journals/iacr/Debris-AlazardR22,
  author       = {Thomas Debris{-}Alazard and
                  Nicolas Resch},
  title        = {Worst and Average Case Hardness of Decoding via Smoothing Bounds},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {1744},
  year         = {2022}
}

@inproceedings{DBLP:conf/crypto/YuZ21,
  author       = {Yu Yu and
                  Jiang Zhang},
  title        = {Smoothing Out Binary Linear Codes and Worst-Case Sub-exponential Hardness
                  for {LPN}},
  booktitle    = {{CRYPTO} {(3)}},
  series       = {Lecture Notes in Computer Science},
  volume       = {12827},
  pages        = {473--501},
  publisher    = {Springer},
  year         = {2021}
}

@inproceedings{DBLP:conf/stoc/Hirahara21,
  author       = {Shuichi Hirahara},
  title        = {Average-case hardness of {NP} from exponential worst-case hardness
                  assumptions},
  booktitle    = {{STOC}},
  pages        = {292--302},
  publisher    = {{ACM}},
  year         = {2021}
}

@article{DBLP:journals/eccc/ChenHV21,
  author       = {Lijie Chen and
                  Shuichi Hirahara and
                  Neekon Vafa},
  title        = {Average-case Hardness of {NP} and {PH} from Worst-case Fine-grained
                  Assumptions},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR21-166}},
  year         = {2021}
}

@article{DBLP:journals/eccc/Hirahara21,
  author       = {Shuichi Hirahara},
  title        = {Average-Case Hardness of {NP} from Exponential Worst-Case Hardness
                  Assumptions},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR21-058}},
  year         = {2021}
}

@article{DBLP:journals/iet-ifs/DasSB20,
  author       = {Dipayan Das and
                  Vishal Saraswat and
                  Kajla Basu},
  title        = {Lattice signatures using {NTRU} on the hardness of worst-case ideal
                  lattice problems},
  journal      = {{IET} Inf. Secur.},
  volume       = {14},
  number       = {5},
  pages        = {496--504},
  year         = {2020}
}

@inproceedings{DBLP:conf/gecco/Yingchareonthawornchai20,
  author       = {Sorrachai Yingchareonthawornchai and
                  Proteek Chandan Roy and
                  Bundit Laekhanukit and
                  Eric Torng and
                  Kalyanmoy Deb},
  title        = {Worst-case conditional hardness and fast algorithms with random inputs
                  for non-dominated sorting},
  booktitle    = {{GECCO} Companion},
  pages        = {185--186},
  publisher    = {{ACM}},
  year         = {2020}
}

@article{DBLP:journals/iacr/YuZ20,
  author       = {Yu Yu and
                  Jiang Zhang},
  title        = {Smoothing Out Binary Linear Codes and Worst-case Sub-exponential Hardness
                  for {LPN}},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {870},
  year         = {2020}
}

@inproceedings{DBLP:conf/eurocrypt/BrakerskiLVW19,
  author       = {Zvika Brakerski and
                  Vadim Lyubashevsky and
                  Vinod Vaikuntanathan and
                  Daniel Wichs},
  title        = {Worst-Case Hardness for {LPN} and Cryptographic Hashing via Code Smoothing},
  booktitle    = {{EUROCRYPT} {(3)}},
  series       = {Lecture Notes in Computer Science},
  volume       = {11478},
  pages        = {619--635},
  publisher    = {Springer},
  year         = {2019}
}

@article{DBLP:journals/eccc/BrakerskiLVW18,
  author       = {Zvika Brakerski and
                  Vadim Lyubashevsky and
                  Vinod Vaikuntanathan and
                  Daniel Wichs},
  title        = {Worst-Case Hardness for {LPN} and Cryptographic Hashing via Code Smoothing},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR18-056}},
  year         = {2018}
}

@article{DBLP:journals/iacr/BrakerskiLVW18,
  author       = {Zvika Brakerski and
                  Vadim Lyubashevsky and
                  Vinod Vaikuntanathan and
                  Daniel Wichs},
  title        = {Worst-Case Hardness for {LPN} and Cryptographic Hashing via Code Smoothing},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {279},
  year         = {2018}
}

@inproceedings{DBLP:conf/fsttcs/MandalPV14,
  author       = {Debasis Mandal and
                  Aduri Pavan and
                  Rajeswari Venugopalan},
  title        = {Separating Cook Completeness from Karp-Levin Completeness Under a
                  Worst-Case Hardness Hypothesis},
  booktitle    = {{FSTTCS}},
  series       = {LIPIcs},
  volume       = {29},
  pages        = {445--456},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2014}
}

@article{DBLP:journals/eccc/MandalPV14,
  author       = {Debasis Mandal and
                  Aduri Pavan and
                  Rajeswari Venugopalan},
  title        = {Separating Cook Completeness from Karp-Levin Completeness under a
                  Worst-Case Hardness Hypothesis},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR14-126}},
  year         = {2014}
}

@article{DBLP:journals/iacr/MelchorBGH11,
  author       = {Carlos Aguilar Melchor and
                  Slim Bettaieb and
                  Philippe Gaborit and
                  Javier Herranz},
  title        = {Improving Additive and Multiplicative Homomorphic Encryption Schemes
                  Based on Worst-Case Hardness Assumptions\}},
  journal      = {{IACR} Cryptol. ePrint Arch.},
  pages        = {607},
  year         = {2011}
}

@inproceedings{DBLP:conf/crypto/Gentry10,
  author       = {Craig Gentry},
  title        = {Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness},
  booktitle    = {{CRYPTO}},
  series       = {Lecture Notes in Computer Science},
  volume       = {6223},
  pages        = {116--137},
  publisher    = {Springer},
  year         = {2010}
}

@inproceedings{DBLP:conf/asiacrypt/KawachiTX08,
  author       = {Akinori Kawachi and
                  Keisuke Tanaka and
                  Keita Xagawa},
  title        = {Concurrently Secure Identification Schemes Based on the Worst-Case
                  Hardness of Lattice Problems},
  booktitle    = {{ASIACRYPT}},
  series       = {Lecture Notes in Computer Science},
  volume       = {5350},
  pages        = {372--389},
  publisher    = {Springer},
  year         = {2008}
}

@article{DBLP:journals/tcs/AndreevCR99,
  author       = {Alexander E. Andreev and
                  Andrea E. F. Clementi and
                  Jos{\'{e}} D. P. Rolim},
  title        = {Worst-Case Hardness Suffices for Derandomization: {A} New Method for
                  Hardness-Randomness Trade-offs},
  journal      = {Theor. Comput. Sci.},
  volume       = {221},
  number       = {1-2},
  pages        = {3--18},
  year         = {1999}
}

@inproceedings{DBLP:conf/icalp/AndreevCR97,
  author       = {Alexander E. Andreev and
                  Andrea E. F. Clementi and
                  Jos{\'{e}} D. P. Rolim},
  title        = {Worst-Case Hardness Suffices for Derandomization: {A} New Method for
                  Hardness-Randomness Trade-Offs},
  booktitle    = {{ICALP}},
  series       = {Lecture Notes in Computer Science},
  volume       = {1256},
  pages        = {177--187},
  publisher    = {Springer},
  year         = {1997}
}
a service of  Schloss Dagstuhl - Leibniz Center for Informatics

manage site settings

To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.