Stop the war!
Остановите войну!
for scientists:
default search action
Search dblp for Publications
export results for "toc:db/journals/eccc/eccc12.bht:"
@article{DBLP:journals/eccc/ECCC-TR05-001, author = {Mario Szegedy}, title = {Near optimality of the priority sampling procedure}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-001}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-001/index.html}, eprinttype = {ECCC}, eprint = {TR05-001}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-001.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-002, author = {Magnus Bordewich and Martin E. Dyer and Marek Karpinski}, title = {Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-002}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-002/index.html}, eprinttype = {ECCC}, eprint = {TR05-002}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-002.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-003, author = {Scott Aaronson}, title = {Quantum Computing, Postselection, and Probabilistic Polynomial-Time}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-003}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-003/index.html}, eprinttype = {ECCC}, eprint = {TR05-003}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-003.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-004, author = {Leslie G. Valiant}, title = {Memorization and Association on a Realistic Neural Model}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-004}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-004/index.html}, eprinttype = {ECCC}, eprint = {TR05-004}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-004.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-005, author = {Tom{\'{a}}s Feder}, title = {Constraint Satisfaction on Finite Groups with Near Subgroups}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-005}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-005/index.html}, eprinttype = {ECCC}, eprint = {TR05-005}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-005.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-006, author = {Edward A. Hirsch and Sergey I. Nikolenko}, title = {Simulating Cutting Plane proofs with restricted degree of falsity by Resolution}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-006}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-006/index.html}, eprinttype = {ECCC}, eprint = {TR05-006}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-006.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-007, author = {Vadim Lyubashevsky}, title = {On Random High Density Subset Sums}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-007}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-007/index.html}, eprinttype = {ECCC}, eprint = {TR05-007}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-007.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-008, author = {Neeraj Kayal}, title = {Recognizing permutation functions in polynomial time}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-008}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-008/index.html}, eprinttype = {ECCC}, eprint = {TR05-008}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-008.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-009, author = {David P. Woodruff and Sergey Yekhanin}, title = {A Geometric Approach to Information-Theoretic Private Information Retrieval}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-009}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-009/index.html}, eprinttype = {ECCC}, eprint = {TR05-009}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-009.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-010, author = {Olivier Powell}, title = {Almost Completeness in Small Complexity Classes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-010}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-010/index.html}, eprinttype = {ECCC}, eprint = {TR05-010}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-010.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-011, author = {Christian Gla{\ss}er and Mitsunori Ogihara and Aduri Pavan and Alan L. Selman and Liyu Zhang}, title = {Autoreducibility, Mitoticity, and Immunity}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-011}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-011/index.html}, eprinttype = {ECCC}, eprint = {TR05-011}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-011.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-012, author = {Luca Trevisan and Salil P. Vadhan and David Zuckerman}, title = {Compression of Samplable Sources}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-012}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-012/index.html}, eprinttype = {ECCC}, eprint = {TR05-012}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-012.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-013, author = {Bin Fu}, title = {Theory and Application of Width Bounded Geometric Separator}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-013}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-013/index.html}, eprinttype = {ECCC}, eprint = {TR05-013}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-013.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-014, author = {Oded Goldreich}, title = {Short Locally Testable Codes and Proofs (Survey)}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-014}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-014/index.html}, eprinttype = {ECCC}, eprint = {TR05-014}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-014.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-015, author = {Andrej Bogdanov and Luca Trevisan}, title = {On Worst-Case to Average-Case Reductions for {NP} Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-015}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-015/index.html}, eprinttype = {ECCC}, eprint = {TR05-015}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-015.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-016, author = {Tom{\'{a}}s Feder and Daniel K. Ford}, title = {Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-016}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-016/index.html}, eprinttype = {ECCC}, eprint = {TR05-016}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-016.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-017, author = {Phuong Nguyen}, title = {Two-Sorted Theories for L, SL, {NL} and {P}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-017}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-017/index.html}, eprinttype = {ECCC}, eprint = {TR05-017}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-017.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-018, author = {Oded Goldreich}, title = {On Promise Problems (a survey in memory of Shimon Even {[1935-2004])}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-018}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-018/index.html}, eprinttype = {ECCC}, eprint = {TR05-018}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-018.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-019, author = {Venkatesan Guruswami and Atri Rudra}, title = {Tolerant Locally Testable Codes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-019}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-019/index.html}, eprinttype = {ECCC}, eprint = {TR05-019}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-019.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-020, author = {Sourav Chakraborty}, title = {On the Sensitivity of Cyclically-Invariant Boolean Functions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-020}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-020/index.html}, eprinttype = {ECCC}, eprint = {TR05-020}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-020.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-021, author = {Stasys Jukna}, title = {Disproving the single level conjecture}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-021}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-021/index.html}, eprinttype = {ECCC}, eprint = {TR05-021}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-021.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-022, author = {Omer Reingold and Luca Trevisan and Salil P. Vadhan}, title = {Pseudorandom Walks in Biregular Graphs and the {RL} vs. {L} Problem}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-022}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-022/index.html}, eprinttype = {ECCC}, eprint = {TR05-022}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-022.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-023, author = {Robert H. Sloan and Bal{\'{a}}zs Sz{\"{o}}r{\'{e}}nyi and Gy{\"{o}}rgy Tur{\'{a}}n}, title = {On k-term {DNF} with largest number of prime implicants}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-023}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-023/index.html}, eprinttype = {ECCC}, eprint = {TR05-023}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-023.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-024, author = {Michael Bauland and Elmar B{\"{o}}hler and Nadia Creignou and Steffen Reith and Henning Schnoor and Heribert Vollmer}, title = {Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-024}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-024/index.html}, eprinttype = {ECCC}, eprint = {TR05-024}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-024.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-025, author = {Zeev Dvir and Ran Raz}, title = {Analyzing Linear Mergers}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-025}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-025/index.html}, eprinttype = {ECCC}, eprint = {TR05-025}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-025.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-026, author = {Scott Aaronson}, title = {NP-complete Problems and Physical Reality}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-026}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-026/index.html}, eprinttype = {ECCC}, eprint = {TR05-026}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-026.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-027, author = {Daniel Rolf}, title = {Derandomization of {PPSZ} for Unique-k-SAT}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-027}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-027/index.html}, eprinttype = {ECCC}, eprint = {TR05-027}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-027.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-028, author = {Elmar B{\"{o}}hler}, title = {On the Lattice of Clones Below the Polynomial Time Functions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-028}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-028/index.html}, eprinttype = {ECCC}, eprint = {TR05-028}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-028.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-029, author = {Frank Neumann and Marco Laumanns}, title = {Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-029}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-029/index.html}, eprinttype = {ECCC}, eprint = {TR05-029}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-029.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-030, author = {Evgeny Dantsin and Alexander Wolpert}, title = {An Improved Upper Bound for {SAT}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-030}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-030/index.html}, eprinttype = {ECCC}, eprint = {TR05-030}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-030.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-031, author = {Carme {\`{A}}lvarez and Joaquim Gabarr{\'{o}} and Maria J. Serna}, title = {Pure Nash equilibria in games with a large number of actions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-031}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-031/index.html}, eprinttype = {ECCC}, eprint = {TR05-031}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-031.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-032, author = {Gudmund Skovbjerg Frandsen and Peter Bro Miltersen}, title = {Reviewing Bounds on the Circuit Size of the Hardest Functions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-032}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-032/index.html}, eprinttype = {ECCC}, eprint = {TR05-032}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-032.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-033, author = {Martin F{\"{u}}rer and Shiva Prasad Kasiviswanathan}, title = {Algorithms for Counting 2-SAT Solutions and Colorings with Applications}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-033}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-033/index.html}, eprinttype = {ECCC}, eprint = {TR05-033}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-033.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-034, author = {Luca Trevisan}, title = {Approximation Algorithms for Unique Games}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-034}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-034/index.html}, eprinttype = {ECCC}, eprint = {TR05-034}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-034.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-035, author = {Christian Gla{\ss}er and Stephen D. Travers and Klaus W. Wagner}, title = {A Reducibility that Corresponds to Unbalanced Leaf-Language Classes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-035}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-035/index.html}, eprinttype = {ECCC}, eprint = {TR05-035}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-035.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-036, author = {Hubie Chen}, title = {Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-036}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-036/index.html}, eprinttype = {ECCC}, eprint = {TR05-036}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-036.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-037, author = {Eric Allender and Peter B{\"{u}}rgisser and Johan Kjeldgaard{-}Pedersen and Peter Bro Miltersen}, title = {On the Complexity of Numerical Analysis}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-037}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-037/index.html}, eprinttype = {ECCC}, eprint = {TR05-037}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-037.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-038, author = {Ran Raz}, title = {Quantum Information and the {PCP} Theorem}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-038}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-038/index.html}, eprinttype = {ECCC}, eprint = {TR05-038}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-038.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-039, author = {Irit Dinur and Elchanan Mossel and Oded Regev}, title = {Conditional Hardness for Approximate Coloring}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-039}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-039/index.html}, eprinttype = {ECCC}, eprint = {TR05-039}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-039.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-040, author = {Scott Aaronson}, title = {Oracles Are Subtle But Not Malicious}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-040}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-040/index.html}, eprinttype = {ECCC}, eprint = {TR05-040}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-040.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-041, author = {Shengyu Zhang}, title = {(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-041}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-041/index.html}, eprinttype = {ECCC}, eprint = {TR05-041}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-041.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-042, author = {Lance Fortnow and Adam R. Klivans}, title = {Linear Advice for Randomized Logarithmic Space}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-042}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-042/index.html}, eprinttype = {ECCC}, eprint = {TR05-042}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-042.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-043, author = {Emanuele Viola}, title = {Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-043}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-043/index.html}, eprinttype = {ECCC}, eprint = {TR05-043}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-043.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-044, author = {Zeev Dvir and Amir Shpilka}, title = {Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-044}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-044/index.html}, eprinttype = {ECCC}, eprint = {TR05-044}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-044.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-045, author = {Philippe Moser}, title = {Martingale Families and Dimension in {P}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-045}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-045/index.html}, eprinttype = {ECCC}, eprint = {TR05-045}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-045.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-046, author = {Irit Dinur}, title = {The {PCP} theorem by gap amplification}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-046}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-046/index.html}, eprinttype = {ECCC}, eprint = {TR05-046}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-046.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-047, author = {Kooshiar Azimian and Mahmoud Salmasizadeh and Javad Mohajeri}, title = {Weak Composite Diffie-Hellman is not Weaker than Factoring}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-047}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-047/index.html}, eprinttype = {ECCC}, eprint = {TR05-047}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-047.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-048, author = {Moti Yung and Yunlei Zhao}, title = {Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-048}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-048/index.html}, eprinttype = {ECCC}, eprint = {TR05-048}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-048.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-049, author = {Joan Boyar and Ren{\'{e}} Peralta}, title = {The Exact Multiplicative Complexity of the Hamming Weight Function}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-049}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-049/index.html}, eprinttype = {ECCC}, eprint = {TR05-049}, timestamp = {Fri, 03 Feb 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-049.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-050, author = {Uriel Feige and Eran Ofek}, title = {Finding a Maximum Independent Set in a Sparse Random Graph}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-050}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-050/index.html}, eprinttype = {ECCC}, eprint = {TR05-050}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-050.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-051, author = {Predrag T. Tosic}, title = {On Complexity of Counting Fixed Points in Certain Classes of Graph Automata}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-051}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-051/index.html}, eprinttype = {ECCC}, eprint = {TR05-051}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-051.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-052, author = {Grant Schoenebeck and Salil P. Vadhan}, title = {The Computational Complexity of Nash Equilibria in Concisely Represented Games}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-052}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-052/index.html}, eprinttype = {ECCC}, eprint = {TR05-052}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-052.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-053, author = {Paul Beame and Toniann Pitassi and Nathan Segerlind}, title = {Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-053}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-053/index.html}, eprinttype = {ECCC}, eprint = {TR05-053}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-053.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-054, author = {Konstantin Pervyshev}, title = {Time Hierarchies for Computations with a Bit of Advice}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-054}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-054/index.html}, eprinttype = {ECCC}, eprint = {TR05-054}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-054.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-055, author = {Bruno Codenotti and Amin Saberi and Kasturi R. Varadarajan and Yinyu Ye}, title = {Leontief Economies Encode Nonzero Sum Two-Player Games}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-055}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-055/index.html}, eprinttype = {ECCC}, eprint = {TR05-055}, timestamp = {Sun, 18 Dec 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-055.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-056, author = {Alexis C. Kaporis and Efpraxia I. Politopoulou and Paul G. Spirakis}, title = {The Price of Optimum in Stackelberg Games}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-056}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-056/index.html}, eprinttype = {ECCC}, eprint = {TR05-056}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-056.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-057, author = {Venkatesan Guruswami and Valentine Kabanets}, title = {Hardness amplification via space-efficient direct products}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-057}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-057/index.html}, eprinttype = {ECCC}, eprint = {TR05-057}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-057.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-058, author = {Sanjeev Arora and Eli Berger and Elad Hazan and Guy Kindler and Muli Safra}, title = {On Non-Approximability for Quadratic Programs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-058}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-058/index.html}, eprinttype = {ECCC}, eprint = {TR05-058}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-058.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-059, author = {V{\'{\i}}ctor Dalmau and Ricard Gavald{\`{a}} and Pascal Tesson and Denis Th{\'{e}}rien}, title = {Tractable Clones of Polynomials over Semigroups}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-059}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-059/index.html}, eprinttype = {ECCC}, eprint = {TR05-059}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-059.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-060, author = {Philippe Moser}, title = {Generic Density and Small Span Theorem}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-060}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-060/index.html}, eprinttype = {ECCC}, eprint = {TR05-060}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-060.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-061, author = {Ronen Gradwohl and Guy Kindler and Omer Reingold and Amnon Ta{-}Shma}, title = {On the Error Parameter of Dispersers}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-061}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-061/index.html}, eprinttype = {ECCC}, eprint = {TR05-061}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-061.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-062, author = {Aduri Pavan and N. V. Vinodchandran}, title = {2-Local Random Reductions to 3-Valued Functions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-062}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-062/index.html}, eprinttype = {ECCC}, eprint = {TR05-062}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-062.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-063, author = {Bodo Manthey and R{\"{u}}diger Reischuk}, title = {Smoothed Analysis of the Height of Binary Search Trees}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-063}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-063/index.html}, eprinttype = {ECCC}, eprint = {TR05-063}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-063.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-064, author = {Howard J. Karloff and Subhash Khot and Aranyak Mehta and Yuval Rabani}, title = {On earthmover distance, metric labeling, and 0-extension}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-064}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-064/index.html}, eprinttype = {ECCC}, eprint = {TR05-064}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-064.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-065, author = {Alexander I. Barvinok and Alex Samorodnitsky}, title = {Random Weighting, Asymptotic Counting, and Inverse Isoperimetry}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-065}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-065/index.html}, eprinttype = {ECCC}, eprint = {TR05-065}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-065.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-066, author = {Jakob Nordstr{\"{o}}m}, title = {Narrow Proofs May Be Spacious: Separating Space and Width in Resolution}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-066}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-066/index.html}, eprinttype = {ECCC}, eprint = {TR05-066}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-066.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-067, author = {Zeev Dvir and Amir Shpilka}, title = {An Improved Analysis of Mergers}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-067}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-067/index.html}, eprinttype = {ECCC}, eprint = {TR05-067}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-067.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-068, author = {Christian Gla{\ss}er and Aduri Pavan and Alan L. Selman and Liyu Zhang}, title = {Redundancy in Complete Sets}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-068}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-068/index.html}, eprinttype = {ECCC}, eprint = {TR05-068}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-068.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-069, author = {Piotr Berman and Marek Karpinski}, title = {8/7-Approximation Algorithm for (1,2)-TSP}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-069}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-069/index.html}, eprinttype = {ECCC}, eprint = {TR05-069}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-069.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-070, author = {Mahdi Cheraghchi}, title = {On Matrix Rigidity and the Complexity of Linear Forms}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-070}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-070/index.html}, eprinttype = {ECCC}, eprint = {TR05-070}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-070.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-071, author = {Marius Zimand}, title = {Simple extractors via constructions of cryptographic pseudo-random generators}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-071}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-071/index.html}, eprinttype = {ECCC}, eprint = {TR05-071}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-071.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-072, author = {Christian Gla{\ss}er and Alan L. Selman and Liyu Zhang}, title = {Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-072}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-072/index.html}, eprinttype = {ECCC}, eprint = {TR05-072}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-072.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-073, author = {Oded Goldreich and Dana Ron}, title = {Approximating Average Parameters of Graphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-073}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-073/index.html}, eprinttype = {ECCC}, eprint = {TR05-073}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-073.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-074, author = {Li{-}Sha Huang and Xiaotie Deng}, title = {On Complexity of Market Equilibria with Maximum Social Welfare}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-074}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-074/index.html}, eprinttype = {ECCC}, eprint = {TR05-074}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-074.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-075, author = {Martin E. Dyer and Leslie Ann Goldberg and Mark Jerrum}, title = {Dobrushin conditions and Systematic Scan}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-075}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-075/index.html}, eprinttype = {ECCC}, eprint = {TR05-075}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-075.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-076, author = {Dima Grigoriev and Edward A. Hirsch and Konstantin Pervyshev}, title = {Time hierarchies for cryptographic function inversion with advice}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-076}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-076/index.html}, eprinttype = {ECCC}, eprint = {TR05-076}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-076.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-077, author = {Zenon Sadowski}, title = {On a D-N-optimal acceptor for {TAUT}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-077}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-077/index.html}, eprinttype = {ECCC}, eprint = {TR05-077}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-077.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-078, author = {Kooshiar Azimian and Javad Mohajeri and Mahmoud Salmasizadeh and Siamak Fayyaz Shahandashti}, title = {A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-078}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-078/index.html}, eprinttype = {ECCC}, eprint = {TR05-078}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-078.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-079, author = {Stasys Jukna}, title = {Expanders and time-restricted branching programs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-079}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-079/index.html}, eprinttype = {ECCC}, eprint = {TR05-079}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-079.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-080, author = {Michael R. Fellows and Frances A. Rosamond and Udi Rotics and Stefan Szeider}, title = {Proving NP-hardness for clique-width {I:} non-approximability of sequential clique-width}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-080}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-080/index.html}, eprinttype = {ECCC}, eprint = {TR05-080}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-080.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-081, author = {Michael R. Fellows and Frances A. Rosamond and Udi Rotics and Stefan Szeider}, title = {Proving NP-hardness for clique-width {II:} non-approximability of clique-width}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-081}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-081/index.html}, eprinttype = {ECCC}, eprint = {TR05-081}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-081.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-082, author = {Jorge Castro}, title = {On the Query Complexity of Quantum Learners}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-082}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-082/index.html}, eprinttype = {ECCC}, eprint = {TR05-082}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-082.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-083, author = {Olaf Beyersdorff}, title = {Disjoint NP-Pairs from Propositional Proof Systems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-083}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-083/index.html}, eprinttype = {ECCC}, eprint = {TR05-083}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-083.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-084, author = {Mickey Brautbar and Alex Samorodnitsky}, title = {Approximating the entropy of large alphabets}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-084}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-084/index.html}, eprinttype = {ECCC}, eprint = {TR05-084}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-084.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-085, author = {Asaf Shapira and Noga Alon}, title = {Homomorphisms in Graph Property Testing - {A} Survey}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-085}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-085/index.html}, eprinttype = {ECCC}, eprint = {TR05-085}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-085.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-086, author = {Dana Moshkovitz and Ran Raz}, title = {Sub-Constant Error Low Degree Test of Almost Linear Size}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-086}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-086/index.html}, eprinttype = {ECCC}, eprint = {TR05-086}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-086.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-087, author = {Alexander Healy and Emanuele Viola}, title = {Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-087}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-087/index.html}, eprinttype = {ECCC}, eprint = {TR05-087}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-087.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-088, author = {Jan Arpe}, title = {Learning Juntas in the Presence of Noise}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-088}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-088/index.html}, eprinttype = {ECCC}, eprint = {TR05-088}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-088.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-089, author = {Xiaoyang Gu and Jack H. Lutz and Philippe Moser}, title = {Dimensions of Copeland-Erd{\"{o}}s Sequences}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-089}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-089/index.html}, eprinttype = {ECCC}, eprint = {TR05-089}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-089.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-090, author = {Paul W. Goldberg and Christos H. Papadimitriou}, title = {Reducibility Among Equilibrium Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-090}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-090/index.html}, eprinttype = {ECCC}, eprint = {TR05-090}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-090.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-091, author = {Predrag T. Tosic}, title = {Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-091}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-091/index.html}, eprinttype = {ECCC}, eprint = {TR05-091}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-091.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-092, author = {Eyal Rozenman and Salil P. Vadhan}, title = {Derandomized Squaring of Graphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-092}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-092/index.html}, eprinttype = {ECCC}, eprint = {TR05-092}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-092.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-093, author = {Daniele Micciancio and Shien Jin Ong and Amit Sahai and Salil P. Vadhan}, title = {Concurrent Zero Knowledge without Complexity Assumptions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-093}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-093/index.html}, eprinttype = {ECCC}, eprint = {TR05-093}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-093.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-094, author = {Michal Parnas and Dana Ron}, title = {On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-094}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-094/index.html}, eprinttype = {ECCC}, eprint = {TR05-094}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-094.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-095, author = {Noga Alon and Ilan Newman and Alexander Shen and G{\'{a}}bor Tardos and Nikolai K. Vereshchagin}, title = {Partitioning multi-dimensional sets in a small number of "uniform" parts}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-095}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-095/index.html}, eprinttype = {ECCC}, eprint = {TR05-095}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-095.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-096, author = {Boaz Barak and Amit Sahai}, title = {How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-096}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-096/index.html}, eprinttype = {ECCC}, eprint = {TR05-096}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-096.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-097, author = {Jens Groth and Rafail Ostrovsky and Amit Sahai}, title = {Perfect Non-Interactive Zero Knowledge for {NP}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-097}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-097/index.html}, eprinttype = {ECCC}, eprint = {TR05-097}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-097.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-098, author = {Oded Goldreich}, title = {Bravely, Moderately: {A} Common Theme in Four Recent Results}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-098}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-098/index.html}, eprinttype = {ECCC}, eprint = {TR05-098}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-098.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-099, author = {Leslie G. Valiant}, title = {Holographic Algorithms}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-099}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-099/index.html}, eprinttype = {ECCC}, eprint = {TR05-099}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-099.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-100, author = {David Zuckerman}, title = {Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-100}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-100/index.html}, eprinttype = {ECCC}, eprint = {TR05-100}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-100.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-101, author = {Guy Kindler and Ryan O'Donnell and Subhash Khot and Elchanan Mossel}, title = {Optimal Inapproximability Results for {MAX-CUT} and Other 2-Variable CSPs?}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-101}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-101/index.html}, eprinttype = {ECCC}, eprint = {TR05-101}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-101.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-102, author = {Evgeny Dantsin and Edward A. Hirsch and Alexander Wolpert}, title = {Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic {SAT} Algorithms}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-102}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-102/index.html}, eprinttype = {ECCC}, eprint = {TR05-102}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-102.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-103, author = {Leonid Gurvits}, title = {A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-103}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-103/index.html}, eprinttype = {ECCC}, eprint = {TR05-103}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-103.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-104, author = {Don Coppersmith and Atri Rudra}, title = {On the Robust Testability of Product of Codes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-104}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-104/index.html}, eprinttype = {ECCC}, eprint = {TR05-104}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-104.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-105, author = {Lance Fortnow and John M. Hitchcock and Aduri Pavan and N. V. Vinodchandran and Fengming Wang}, title = {Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-105}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-105/index.html}, eprinttype = {ECCC}, eprint = {TR05-105}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-105.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-106, author = {Anup Rao}, title = {Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-106}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-106/index.html}, eprinttype = {ECCC}, eprint = {TR05-106}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-106.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-107, author = {Avi Wigderson and David Xiao}, title = {A Randomness-Efficient Sampler for Matrix-valued Functions and Applications}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-107}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-107/index.html}, eprinttype = {ECCC}, eprint = {TR05-107}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-107.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-108, author = {Ariel Gabizon and Ran Raz}, title = {Deterministic Extractors for Affine Sources over Large Fields}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-108}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-108/index.html}, eprinttype = {ECCC}, eprint = {TR05-108}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-108.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-109, author = {Ariel Gabizon and Ran Raz and Ronen Shaltiel}, title = {Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-109}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-109/index.html}, eprinttype = {ECCC}, eprint = {TR05-109}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-109.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-110, author = {Saurabh Sanghvi and Salil P. Vadhan}, title = {The Round Complexity of Two-Party Random Selection}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-110}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-110/index.html}, eprinttype = {ECCC}, eprint = {TR05-110}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-110.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-111, author = {Dieter van Melkebeek and Konstantin Pervyshev}, title = {A Generic Time Hierarchy for Semantic Models With One Bit of Advice}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-111}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-111/index.html}, eprinttype = {ECCC}, eprint = {TR05-111}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-111.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-112, author = {Eran Ofek}, title = {On the expansion of the giant component in percolated (n,d,lambda) graphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-112}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-112/index.html}, eprinttype = {ECCC}, eprint = {TR05-112}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-112.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-113, author = {Bernhard Fuchs}, title = {On the Hardness of Range Assignment Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-113}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-113/index.html}, eprinttype = {ECCC}, eprint = {TR05-113}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-113.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-114, author = {Boaz Barak and Shien Jin Ong and Salil P. Vadhan}, title = {Derandomization in Cryptography}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-114}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-114/index.html}, eprinttype = {ECCC}, eprint = {TR05-114}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-114.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-115, author = {Konstantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou}, title = {The complexity of computing a Nash equilibrium}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-115}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-115/index.html}, eprinttype = {ECCC}, eprint = {TR05-115}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-115.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-116, author = {Alex Samorodnitsky and Luca Trevisan}, title = {Gowers Uniformity, Influence of Variables, and PCPs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-116}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-116/index.html}, eprinttype = {ECCC}, eprint = {TR05-116}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-116.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-117, author = {Piotr Indyk and David P. Woodruff}, title = {Polylogarithmic Private Approximations and Efficient Matching}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-117}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-117/index.html}, eprinttype = {ECCC}, eprint = {TR05-117}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-117.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-118, author = {Jin{-}yi Cai and Vinay Choudhary}, title = {Valiant's Holant Theorem and Matchgate Tensors}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-118}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-118/index.html}, eprinttype = {ECCC}, eprint = {TR05-118}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-118.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-119, author = {Nadia Creignou and Phokion G. Kolaitis and Bruno Zanuttini}, title = {Preferred representations of Boolean relations}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-119}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-119/index.html}, eprinttype = {ECCC}, eprint = {TR05-119}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-119.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-120, author = {Sashka Davis and Russell Impagliazzo}, title = {Models of Greedy Algorithms for Graph Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-120}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-120/index.html}, eprinttype = {ECCC}, eprint = {TR05-120}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-120.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-121, author = {Martin E. Dyer and Leslie Ann Goldberg and Mike Paterson}, title = {On counting homomorphisms to directed acyclic graphs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-121}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-121/index.html}, eprinttype = {ECCC}, eprint = {TR05-121}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-121.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-122, author = {Pavel Pudl{\'{a}}k}, title = {A nonlinear bound on the number of wires in bounded depth circuits}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-122}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-122/index.html}, eprinttype = {ECCC}, eprint = {TR05-122}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-122.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-123, author = {Olaf Beyersdorff}, title = {Tuples of Disjoint NP-Sets}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-123}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-123/index.html}, eprinttype = {ECCC}, eprint = {TR05-123}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-123.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-124, author = {Kooshiar Azimian}, title = {Breaking Diffie-Hellman is no Easier than Root Finding}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-124}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-124/index.html}, eprinttype = {ECCC}, eprint = {TR05-124}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-124.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-125, author = {Sofya Raskhodnikova and Dana Ron and Ronitt Rubinfeld and Amir Shpilka and Adam D. Smith}, title = {Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-125}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-125/index.html}, eprinttype = {ECCC}, eprint = {TR05-125}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-125.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-126, author = {Eric Allender and Lisa Hellerstein and Paul McCabe and Toniann Pitassi and Michael E. Saks}, title = {Minimizing {DNF} Formulas and {AC0} Circuits Given a Truth Table}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-126}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-126/index.html}, eprinttype = {ECCC}, eprint = {TR05-126}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-126.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-127, author = {Vitaly Feldman}, title = {Hardness of Approximate Two-level Logic Minimization and {PAC} Learning with Membership Queries}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-127}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-127/index.html}, eprinttype = {ECCC}, eprint = {TR05-127}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-127.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-128, author = {Miroslava Sot{\'{a}}kov{\'{a}}}, title = {The normal form of reversible circuits consisting of {CNOT} and {NOT} gates}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-128}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-128/index.html}, eprinttype = {ECCC}, eprint = {TR05-128}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-128.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-129, author = {Scott Aaronson}, title = {QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-129}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-129/index.html}, eprinttype = {ECCC}, eprint = {TR05-129}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-129.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-130, author = {Ahuva Mu'alem}, title = {A Note on Testing Truthfulness}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-130}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-130/index.html}, eprinttype = {ECCC}, eprint = {TR05-130}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-130.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-131, author = {Don Coppersmith and Lisa Fleischer and Atri Rudra}, title = {Ordering by weighted number of wins gives a good ranking for weighted tournaments}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-131}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-131/index.html}, eprinttype = {ECCC}, eprint = {TR05-131}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-131.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-132, author = {Venkatesan Guruswami}, title = {Algebraic-geometric generalizations of the Parvaresh-Vardy codes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-132}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-132/index.html}, eprinttype = {ECCC}, eprint = {TR05-132}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-132.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-133, author = {Venkatesan Guruswami and Atri Rudra}, title = {Explicit Capacity-Achieving List-Decodable Codes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-133}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-133/index.html}, eprinttype = {ECCC}, eprint = {TR05-133}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-133.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-134, author = {Xi Chen and Xiaotie Deng}, title = {3-NASH is PPAD-Complete}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-134}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-134/index.html}, eprinttype = {ECCC}, eprint = {TR05-134}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-134.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-135, author = {Iftach Haitner and Danny Harnik and Omer Reingold}, title = {On the Power of the Randomized Iterate}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-135}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-135/index.html}, eprinttype = {ECCC}, eprint = {TR05-135}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-135.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-136, author = {Anna G{\'{a}}l and Michal Kouck{\'{y}} and Pierre McKenzie}, title = {Incremental branching programs}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-136}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-136/index.html}, eprinttype = {ECCC}, eprint = {TR05-136}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-136.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-137, author = {Emanuele Viola}, title = {On Probabilistic Time versus Alternating Time}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-137}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-137/index.html}, eprinttype = {ECCC}, eprint = {TR05-137}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-137.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-138, author = {Peter B{\"{u}}rgisser and Felipe Cucker}, title = {Exotic quantifiers, complexity classes, and complete problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-138}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-138/index.html}, eprinttype = {ECCC}, eprint = {TR05-138}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-138.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-139, author = {Konstantinos Daskalakis and Christos H. Papadimitriou}, title = {Three-Player Games Are Hard}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-139}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-139/index.html}, eprinttype = {ECCC}, eprint = {TR05-139}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-139.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-140, author = {Xi Chen and Xiaotie Deng}, title = {Settling the Complexity of 2-Player Nash-Equilibrium}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-140}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-140/index.html}, eprinttype = {ECCC}, eprint = {TR05-140}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-140.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-141, author = {Amos Beimel and Paz Carmi and Kobbi Nissim and Enav Weinreb}, title = {Private Approximation of Search Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-141}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-141/index.html}, eprinttype = {ECCC}, eprint = {TR05-141}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-141.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-142, author = {Vadim Lyubashevsky and Daniele Micciancio}, title = {Generalized Compact Knapsacks are Collision Resistant}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-142}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-142/index.html}, eprinttype = {ECCC}, eprint = {TR05-142}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-142.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-143, author = {Parikshit Gopalan}, title = {Constructing Ramsey Graphs from Boolean Function Representations}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-143}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-143/index.html}, eprinttype = {ECCC}, eprint = {TR05-143}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-143.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-144, author = {Lance Fortnow and Luis Antunes}, title = {Time-Bounded Universal Distributions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-144}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-144/index.html}, eprinttype = {ECCC}, eprint = {TR05-144}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-144.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-145, author = {Ronen Shaltiel}, title = {How to get more mileage from randomness extractors}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-145}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-145/index.html}, eprinttype = {ECCC}, eprint = {TR05-145}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-145.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-146, author = {G{\'{a}}bor Erd{\'{e}}lyi and Tobias Riege and J{\"{o}}rg Rothe}, title = {Quantum Cryptography: {A} Survey}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-146}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-146/index.html}, eprinttype = {ECCC}, eprint = {TR05-146}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-146.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-147, author = {Christian Gla{\ss}er and Stephen D. Travers}, title = {Machines that can Output Empty Words}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-147}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-147/index.html}, eprinttype = {ECCC}, eprint = {TR05-147}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-147.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-148, author = {Eric Allender and Samir Datta and Sambuddha Roy}, title = {The Directed Planar Reachability Problem}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-148}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-148/index.html}, eprinttype = {ECCC}, eprint = {TR05-148}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-148.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-149, author = {Eric Allender and David A. Mix Barrington and Tanmoy Chakraborty and Samir Datta and Sambuddha Roy}, title = {Grid Graph Reachability Problems}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-149}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-149/index.html}, eprinttype = {ECCC}, eprint = {TR05-149}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-149.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-150, author = {Neeraj Kayal and Nitin Saxena}, title = {Polynomial Identity Testing for Depth 3 Circuits}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-150}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-150/index.html}, eprinttype = {ECCC}, eprint = {TR05-150}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-150.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-151, author = {Magnus Bordewich and Martin E. Dyer and Marek Karpinski}, title = {Metric Construction, Stopping Times and Path Coupling}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-151}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-151/index.html}, eprinttype = {ECCC}, eprint = {TR05-151}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-151.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-152, author = {Oded Lachish and Ilan Newman}, title = {Languages that are Recognized by Simple Counter Automata are not necessarily Testable}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-152}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-152/index.html}, eprinttype = {ECCC}, eprint = {TR05-152}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-152.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-153, author = {Shirley Halevy and Oded Lachish and Ilan Newman and Dekel Tsur}, title = {Testing Orientation Properties}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-153}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-153/index.html}, eprinttype = {ECCC}, eprint = {TR05-153}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-153.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-154, author = {Albert Atserias}, title = {Non-Uniform Hardness for {NP} via Black-Box Adversaries}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-154}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-154/index.html}, eprinttype = {ECCC}, eprint = {TR05-154}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-154.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-155, author = {Amir Shpilka}, title = {Constructions of low-degree and error-correcting epsilon-biased sets}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-155}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-155/index.html}, eprinttype = {ECCC}, eprint = {TR05-155}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-155.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-156, author = {Jonathan A. Kelner and Daniel A. Spielman}, title = {A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-156}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-156/index.html}, eprinttype = {ECCC}, eprint = {TR05-156}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-156.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-157, author = {Xiaoyang Gu and Jack H. Lutz and Elvira Mayordomo}, title = {Points on Computable Curves}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-157}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-157/index.html}, eprinttype = {ECCC}, eprint = {TR05-157}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-157.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-158, author = {Chris Peikert and Alon Rosen}, title = {Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-158}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-158/index.html}, eprinttype = {ECCC}, eprint = {TR05-158}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-158.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-159, author = {Daniel Rolf}, title = {Improved Bound for the PPSZ/Sch{\"{o}}ning-Algorithm for 3-SAT}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-159}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-159/index.html}, eprinttype = {ECCC}, eprint = {TR05-159}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-159.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-160, author = {Xiaoyang Gu and Jack H. Lutz}, title = {Dimension Characterizations of Complexity Classes}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-160}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-160/index.html}, eprinttype = {ECCC}, eprint = {TR05-160}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-160.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-161, author = {John M. Hitchcock}, title = {Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-161}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-161/index.html}, eprinttype = {ECCC}, eprint = {TR05-161}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-161.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-162, author = {Yunlei Zhao and Jesper Buus Nielsen and Robert H. Deng and Dengguo Feng}, title = {Generic yet Practical {ZK} Arguments from any Public-Coin {HVZK}}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-162}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-162/index.html}, eprinttype = {ECCC}, eprint = {TR05-162}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-162.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/ECCC-TR05-163, author = {Dvir Falik and Alex Samorodnitsky}, title = {Edge-isoperimetric inequalities and influences}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR05-163}}, year = {2005}, url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-163/index.html}, eprinttype = {ECCC}, eprint = {TR05-163}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-163.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
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.