Search dblp for Publications

export results for "toc:db/journals/eccc/eccc2024.bht:"

 download as .bib file

@article{DBLP:journals/eccc/00010SV24,
  author       = {Mrinal Kumar and
                  Varun Ramanathan and
                  Ramprasad Saptharishi and
                  Ben Lee Volk},
  title        = {Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth
                  Circuits},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--043},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/043},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/00010SV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/00010Y24,
  author       = {Xi Chen and
                  Yuhao Li and
                  Mihalis Yannakakis},
  title        = {Computing a Fixed Point of Contraction Maps in Polynomial Queries},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--057},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/057},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/00010Y24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/000124,
  author       = {Oded Goldreich},
  title        = {On locally-characterized expander graphs (a survey)},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--013},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/013},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/000124.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/000124a,
  author       = {Oded Goldreich},
  title        = {On the query complexity of testing local graph properties in the bounded-degree
                  graph model},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--047},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/047},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/000124a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/0002LRX24,
  author       = {Siddhartha Jain and
                  Jiawei Li and
                  Robert Robere and
                  Zhiyang Xun},
  title        = {On Pigeonhole Principles and Ramsey in {TFNP}},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--017},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/017},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/0002LRX24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/AlekseevFS24,
  author       = {Yaroslav Alekseev and
                  Yuval Filmus and
                  Alexander Smal},
  title        = {Lifting dichotomies},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--037},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/037},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/AlekseevFS24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/AmireddyBP0024,
  author       = {Prashanth Amireddy and
                  Amik Raj Behera and
                  Manaswi Paraashar and
                  Srikanth Srinivasan and
                  Madhu Sudan},
  title        = {Local Correction of Linear Functions over the Boolean Cube},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--056},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/056},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/AmireddyBP0024.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/ArtecheCG24,
  author       = {Noel Arteche and
                  Gaia Carenini and
                  Matthew Gray},
  title        = {Quantum Automating {\textdollar}{\textbackslash}mathbf\{TC\}0{\textdollar}-Frege
                  Is LWE-Hard},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--029},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/029},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/ArtecheCG24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BafnaLM24,
  author       = {Mitali Bafna and
                  Noam Lifshitz and
                  Dor Minzer},
  title        = {Constant Degree Direct Product Testers with Small Soundness},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--020},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/020},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BafnaLM24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BallLMP24,
  author       = {Marshall Ball and
                  Yanyi Liu and
                  Noam Mazor and
                  Rafael Pass},
  title        = {Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity
                  and Key-Agreement},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--055},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/055},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/BallLMP24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BaraskarD024,
  author       = {Omkar Baraskar and
                  Agrim Dewan and
                  Chandan Saha},
  title        = {Testing equivalence to design polynomials},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--004},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/004},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BaraskarD024.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BeameK24,
  author       = {Paul Beame and
                  Niels Kornerup},
  title        = {Quantum Time-Space Tradeoffs for Matrix Problems},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--011},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/011},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BeameK24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Bedi24,
  author       = {Harpreet Bedi},
  title        = {Degree 2 lower bound for Permanent in arbitrary characteristic},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--015},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/015},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Bedi24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BennettGS24,
  author       = {Huck Bennett and
                  Surendra Ghentiyala and
                  Noah Stephens{-}Davidowitz},
  title        = {The more the merrier! On the complexity of finding multicollisions,
                  with connections to codes and lattices},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--018},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/018},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BennettGS24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BeyersdorffHS24,
  author       = {Olaf Beyersdorff and
                  Tim Hoffmann and
                  Luc Nicolas Spachmann},
  title        = {Proof Complexity of Propositional Model Counting},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--030},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/030},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BeyersdorffHS24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BeyersdorffKS24,
  author       = {Olaf Beyersdorff and
                  Kaspar Kasche and
                  Luc Nicolas Spachmann},
  title        = {Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through
                  Circuits and Degree},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--038},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/038},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BeyersdorffKS24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Bhattacharya24,
  author       = {Sreejata Kishor Bhattacharya},
  title        = {Aaronson-Ambainis Conjecture Is True For Random Restrictions},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--035},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/035},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Bhattacharya24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BhattacharyaCD24,
  author       = {Sreejata Kishor Bhattacharya and
                  Arkadev Chattopadhyay and
                  Pavel Dvorak},
  title        = {Exponential Separation Between Powers of Regular and General Resolution
                  Over Parities},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--022},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/022},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BhattacharyaCD24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Bisht0NV24,
  author       = {Pranav Bisht and
                  Nikhil Gupta and
                  Prajakta Nimbhorkar and
                  Ilya Volkovich},
  title        = {Launching Identity Testing into (Bounded) Space},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--041},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/041},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/Bisht0NV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BonacinaBBL24,
  author       = {Ilario Bonacina and
                  Maria Luisa Bonet and
                  Sam Buss and
                  Massimo Lauria},
  title        = {Redundancy for MaxSAT},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--045},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/045},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/BonacinaBBL24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BoyleKV24,
  author       = {Elette Boyle and
                  Ilan Komargodski and
                  Neekon Vafa},
  title        = {Memory Checking Requires Logarithmic Overhead},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--014},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/014},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BoyleKV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BussT24,
  author       = {Sam Buss and
                  Neil Thapen},
  title        = {A Simple Supercritical Tradeoff between Size and Height in Resolution},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR24-001}},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/001},
  eprinttype    = {ECCC},
  eprint       = {TR24-001},
  timestamp    = {Wed, 10 Jan 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BussT24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/BussY24,
  author       = {Sam Buss and
                  Emre Yolcu},
  title        = {Regular resolution effectively simulates resolution},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--033},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/033},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/BussY24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/ChauguleL24,
  author       = {Prasad Chaugule and
                  Nutan Limaye},
  title        = {On the closures of monotone algebraic classes and variants of the
                  determinant},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--021},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/021},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/ChauguleL24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/ChengW24,
  author       = {Kuan Cheng and
                  Ruiyang Wu},
  title        = {Randomness Extractors in {\textdollar}{\textbackslash}mathrm\{AC\}0{\textdollar}
                  and {\textdollar}{\textbackslash}mathrm\{NC\}1{\textdollar}: Optimal
                  up to Constant Factors},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--040},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/040},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/ChengW24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/ChengW24a,
  author       = {Kuan Cheng and
                  Yichuan Wang},
  title        = {{\textdollar}BPL{\textbackslash}subseteq L-AC1{\textdollar}},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--048},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/048},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/ChengW24a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/CookM24,
  author       = {Joshua Cook and
                  Dana Moshkovitz},
  title        = {Explicit Time and Space Efficient Encoders Exist Only With Random
                  Access},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--032},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/032},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/CookM24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/DiCiccoP024,
  author       = {Mason DiCicco and
                  Vladimir Podolskii and
                  Daniel Reichman},
  title        = {Nearest Neighbor Complexity and Boolean Circuits},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--025},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/025},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/DiCiccoP024.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/DiksteinDL24,
  author       = {Yotam Dikstein and
                  Irit Dinur and
                  Alexander Lubotzky},
  title        = {Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--019},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/019},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/DiksteinDL24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/DwivediGV24,
  author       = {Ashish Dwivedi and
                  Zeyu Guo and
                  Ben Lee Volk},
  title        = {Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately
                  Large Fields},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--028},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/028},
  timestamp    = {Tue, 07 May 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/DwivediGV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/FlemingGPR24,
  author       = {Noah Fleming and
                  Stefan Grosser and
                  Toniann Pitassi and
                  Robert Robere},
  title        = {Black-Box {PPP} is not Turing-Closed},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--010},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/010},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/FlemingGPR24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/GajulapalliGK24,
  author       = {Karthik Gajulapalli and
                  Alexander Golovnev and
                  Samuel King},
  title        = {On the Power of Adaptivity for Function Inversion},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--054},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/054},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/GajulapalliGK24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/GajulapalliLV24,
  author       = {Karthik Gajulapalli and
                  Zeyong Li and
                  Ilya Volkovich},
  title        = {Oblivious Classes Revisited: Lower Bounds and Hierarchies},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--049},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/049},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/GajulapalliLV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Gavinsky24,
  author       = {Dmytro Gavinsky},
  title        = {Unambiguous parity-query complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--009},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/009},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Gavinsky24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/GrewalY24,
  author       = {Sabee Grewal and
                  Justin Yirka},
  title        = {The Entangled Quantum Polynomial Hierarchy Collapses},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--006},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/006},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/GrewalY24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/GurjarOR24,
  author       = {Rohit Gurjar and
                  Taihei Oki and
                  Roshan Raj},
  title        = {Fractional Linear Matroid Matching is in quasi-NC},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--044},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/044},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/GurjarOR24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/HatamiH24,
  author       = {Hamed Hatami and
                  Pooya Hatami},
  title        = {Structure in Communication Complexity and Constant-Cost Complexity
                  Classes},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--012},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/012},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/HatamiH24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/HiraharaO24,
  author       = {Shuichi Hirahara and
                  Naoto Ohsaka},
  title        = {Probabilistically Checkable Reconfiguration Proofs and Inapproximability
                  of Reconfiguration Problems},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--023},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/023},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/HiraharaO24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/HiraharaO24a,
  author       = {Shuichi Hirahara and
                  Naoto Ohsaka},
  title        = {Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--039},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/039},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/HiraharaO24a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/HiraharaS24,
  author       = {Shuichi Hirahara and
                  Nobutaka Shimizu},
  title        = {Planted Clique Conjectures Are Equivalent},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--058},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/058},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/HiraharaS24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Hrubes24,
  author       = {Pavel Hrubes},
  title        = {Hard submatrices for non-negative rank and communication complexity
                  \}},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--008},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/008},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Hrubes24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Hrubes24a,
  author       = {Pavel Hrubes},
  title        = {A subquadratic upper bound on sum-of-squares compostion formulas},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--026},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/026},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Hrubes24a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Ishizuka24,
  author       = {Takashi Ishizuka},
  title        = {{PLS} is contained in {PLC}},
  journal      = {Electron. Colloquium Comput. Complex.},
  volume       = {{TR24-002}},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/002},
  eprinttype    = {ECCC},
  eprint       = {TR24-002},
  timestamp    = {Wed, 10 Jan 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Ishizuka24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/JaserT24,
  author       = {Lisa Jaser and
                  Jacobo Tor{\'{a}}n},
  title        = {Pebble Games and Algebraic Proof Systems Meet Again},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--042},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/042},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/JaserT24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/KaneO024,
  author       = {Daniel M. Kane and
                  Anthony Ostuni and
                  Kewen Wu},
  title        = {Locality Bounds for Sampling Hamming Slices},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--031},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/031},
  timestamp    = {Tue, 09 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/KaneO024.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/LiuP24,
  author       = {Yanyi Liu and
                  Rafael Pass},
  title        = {A Direct {PRF} Construction from Kolmogorov Complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--051},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/051},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/LiuP24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/LoffM24,
  author       = {Bruno Loff and
                  Alexey Milovanov},
  title        = {The hardness of decision tree complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--034},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/034},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/LoffM24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/MazorP24,
  author       = {Noam Mazor and
                  Rafael Pass},
  title        = {Search-to-Decision Reductions for Kolmogorov Complexity},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--003},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/003},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/MazorP24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/MazorP24a,
  author       = {Noam Mazor and
                  Rafael Pass},
  title        = {Gap {MCSP} is not (Levin) NP-complete in Obfustopia},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--053},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/053},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/MazorP24a.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/MinzerZ24,
  author       = {Dor Minzer and
                  Kai Zhe Zheng},
  title        = {Near Optimal Alphabet-Soundness Tradeoff PCPs},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--027},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/027},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/MinzerZ24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Mouli24,
  author       = {Sasank Mouli},
  title        = {Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--046},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/046},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/Mouli24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/MuNRV24,
  author       = {Changrui Mu and
                  Shafik Nassar and
                  Ron Rothblum and
                  Prashant Nalini Vasudevan},
  title        = {Strong Batching for Non-Interactive Statistical Zero-Knowledge},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--024},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/024},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/MuNRV24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/NobleHO24,
  author       = {Daniel Noble and
                  Brett Hemenway and
                  Rafail Ostrovsky},
  title        = {MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--005},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/005},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/NobleHO24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/SM24,
  author       = {{Karthik {C. S.}} and
                  Pasin Manurangsi},
  title        = {On Inapproximability of Reconfiguration Problems: PSPACE-Hardness
                  and some Tight NP-Hardness Results},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--007},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/007},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/SM24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Sanyal24,
  author       = {Swagato Sanyal},
  title        = {Randomized query composition and product distributions},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--016},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/016},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Sanyal24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Shmueli24,
  author       = {Omri Shmueli},
  title        = {Quantum Algorithms in a Superposition of Spacetimes},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--050},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/050},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/Shmueli24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Yankovitz24,
  author       = {Tal Yankovitz},
  title        = {A stronger bound for linear 3-LCC},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--036},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/036},
  timestamp    = {Tue, 05 Mar 2024 00:00:00 +0100},
  biburl       = {https://dblp.org/rec/journals/eccc/Yankovitz24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{DBLP:journals/eccc/Yirka24,
  author       = {Justin Yirka},
  title        = {Even quantum advice is unlikely to solve {PP}},
  journal      = {Electron. Colloquium Comput. Complex.},
  pages        = {TR24--052},
  year         = {2024},
  url          = {https://eccc.weizmann.ac.il/report/2024/052},
  timestamp    = {Tue, 02 Apr 2024 01:00:00 +0200},
  biburl       = {https://dblp.org/rec/journals/eccc/Yirka24.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}
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.