Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "toc:db/journals/eccc/eccc11.bht:"
download as .bib file
@article{DBLP:journals/eccc/ECCC-TR04-001,
author = {Lance Fortnow and
Russell Impagliazzo and
Valentine Kabanets and
Christopher Umans},
title = {On the complexity of succinct zero-sum games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-001}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-001/index.html},
eprinttype = {ECCC},
eprint = {TR04-001},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-001.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-002,
author = {Troy Lee and
Dieter van Melkebeek and
Harry Buhrman},
title = {Language Compression and Pseudorandom Generators},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-002}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-002/index.html},
eprinttype = {ECCC},
eprint = {TR04-002},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-002.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-003,
author = {Pascal Koiran},
title = {Valiant's model and the cost of computing integers},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-003}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-003/index.html},
eprinttype = {ECCC},
eprint = {TR04-003},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-003.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-004,
author = {Ramamohan Paturi and
Pavel Pudl{\'{a}}k},
title = {Circuit lower bounds and linear codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-004}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-004/index.html},
eprinttype = {ECCC},
eprint = {TR04-004},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-004.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-005,
author = {Stasys Jukna},
title = {On Graph Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-005}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-005/index.html},
eprinttype = {ECCC},
eprint = {TR04-005},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-005.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-006,
author = {G{\"{u}}nter Hotz},
title = {A remark on nondecidabilities of the initial value problem of ODEs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-006}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-006/index.html},
eprinttype = {ECCC},
eprint = {TR04-006},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-006.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-007,
author = {Alan L. Selman and
Samik Sengupta},
title = {Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential
Hierarchy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-007}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-007/index.html},
eprinttype = {ECCC},
eprint = {TR04-007},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-007.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-008,
author = {Vikraman Arvind and
Jacobo Tor{\'{a}}n},
title = {Solvable Group Isomorphism is (almost) in NP{\textbackslash}cap coNP},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-008}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-008/index.html},
eprinttype = {ECCC},
eprint = {TR04-008},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-008.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-009,
author = {Martin E. Dyer and
Alan M. Frieze and
Thomas P. Hayes and
Eric Vigoda},
title = {Randomly coloring constant degree graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-009}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-009/index.html},
eprinttype = {ECCC},
eprint = {TR04-009},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-009.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-010,
author = {Michal Parnas and
Dana Ron and
Ronitt Rubinfeld},
title = {Tolerant Property Testing and Distance Approximation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-010}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-010/index.html},
eprinttype = {ECCC},
eprint = {TR04-010},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-010.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-011,
author = {Christian Gla{\ss}er},
title = {Counting with Counterfree Automata},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-011}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-011/index.html},
eprinttype = {ECCC},
eprint = {TR04-011},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-011.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-012,
author = {Paul Beame and
Joseph C. Culberson and
David G. Mitchell and
Cristopher Moore},
title = {The Resolution Complexity of Random Graph k-Colorability},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-012}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-012/index.html},
eprinttype = {ECCC},
eprint = {TR04-012},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-012.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-013,
author = {Oded Goldreich and
Dana Ron},
title = {On Estimating the Average Degree of a Graph},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-013}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-013/index.html},
eprinttype = {ECCC},
eprint = {TR04-013},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-013.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-014,
author = {Chris Pollett},
title = {Languages to diagonalize against advice classes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-014}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-014/index.html},
eprinttype = {ECCC},
eprint = {TR04-014},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-014.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-015,
author = {Richard Beigel and
Harry Buhrman and
Peter A. Fejer and
Lance Fortnow and
Piotr Grabowski and
Luc Longpr{\'{e}} and
Andrei A. Muchnik and
Frank Stephan and
Leen Torenvliet},
title = {Enumerations of the Kolmogorov Function},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-015}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-015/index.html},
eprinttype = {ECCC},
eprint = {TR04-015},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-015.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-016,
author = {Michael Alekhnovich and
Eli Ben{-}Sasson},
title = {Linear Upper Bounds for Random Walk on Small Density Random 3CNFs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-016}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-016/index.html},
eprinttype = {ECCC},
eprint = {TR04-016},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-017,
author = {Evgeny Dantsin and
Alexander Wolpert},
title = {Derandomization of Schuler's Algorithm for {SAT}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-017}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-017/index.html},
eprinttype = {ECCC},
eprint = {TR04-017},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-017.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-018,
author = {Jan Kraj{\'{\i}}cek},
title = {Diagonalization in proof complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-018}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-018/index.html},
eprinttype = {ECCC},
eprint = {TR04-018},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-019,
author = {Christian Gla{\ss}er and
Aduri Pavan and
Alan L. Selman and
Samik Sengupta},
title = {Properties of NP-Complete Sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-019}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-019/index.html},
eprinttype = {ECCC},
eprint = {TR04-019},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-020,
author = {Emanuele Viola},
title = {The Complexity of Constructing Pseudorandom Generators from Hard Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-020}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-020/index.html},
eprinttype = {ECCC},
eprint = {TR04-020},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-021,
author = {Eli Ben{-}Sasson and
Oded Goldreich and
Prahladh Harsha and
Madhu Sudan and
Salil P. Vadhan},
title = {Robust PCPs of Proximity, Shorter PCPs and Applications to Coding},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-021}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-021/index.html},
eprinttype = {ECCC},
eprint = {TR04-021},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-021.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-022,
author = {Nayantara Bhatnagar and
Parikshit Gopalan and
Richard J. Lipton},
title = {The Degree of Threshold Mod 6 and Diophantine Equations},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-022}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-022/index.html},
eprinttype = {ECCC},
eprint = {TR04-022},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-023,
author = {Yaoyun Shi},
title = {Quantum and Classical Tradeoffs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-023}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-023/index.html},
eprinttype = {ECCC},
eprint = {TR04-023},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-024,
author = {Thomas Thierauf and
Thanh Minh Hoang},
title = {On Closure Properties of GapL},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-024}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-024/index.html},
eprinttype = {ECCC},
eprint = {TR04-024},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-024.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-025,
author = {John M. Hitchcock and
Aduri Pavan and
Pramodchandran N. Variyam},
title = {Partial Bi-Immunity and NP-Completeness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-025}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-025/index.html},
eprinttype = {ECCC},
eprint = {TR04-025},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-025.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-026,
author = {Scott Aaronson},
title = {Limitations of Quantum Advice and One-Way Communication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-026}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-026/index.html},
eprinttype = {ECCC},
eprint = {TR04-026},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-026.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-027,
author = {Henning Fernau},
title = {Parametric Duality: Kernel Sizes and Algorithmics},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-027}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-027/index.html},
eprinttype = {ECCC},
eprint = {TR04-027},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-027.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-028,
author = {Arfst Nickelsen and
Till Tantau and
Lorenz Weizs{\"{a}}cker},
title = {Aggregates with Component Size One Characterize Polynomial Space},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-028}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-028/index.html},
eprinttype = {ECCC},
eprint = {TR04-028},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-028.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-029,
author = {John M. Hitchcock and
Mar{\'{\i}}a L{\'{o}}pez{-}Vald{\'{e}}s and
Elvira Mayordomo},
title = {Scaled dimension and the Kolmogorov complexity of Turing hard sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-029}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-029/index.html},
eprinttype = {ECCC},
eprint = {TR04-029},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-029.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-030,
author = {Nikolai K. Vereshchagin},
title = {Kolmogorov complexity of enumerating finite sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-030}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-030/index.html},
eprinttype = {ECCC},
eprint = {TR04-030},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-030.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-031,
author = {Troy Lee and
Andrei E. Romashchenko},
title = {On Polynomially Time Bounded Symmetry of Information},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-031}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-031/index.html},
eprinttype = {ECCC},
eprint = {TR04-031},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-031.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-032,
author = {Ryan Williams},
title = {A new algorithm for optimal constraint satisfaction and its implications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-032}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-032/index.html},
eprinttype = {ECCC},
eprint = {TR04-032},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-032.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-033,
author = {Michael Schmitt},
title = {On the sample complexity of learning for networks of spiking neurons
with nonlinear synaptic interactions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-033}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-033/index.html},
eprinttype = {ECCC},
eprint = {TR04-033},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-033.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-034,
author = {April Rasala Lehman and
Eric Lehman},
title = {Network Coding: Does the Model Need Tuning?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-034}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-034/index.html},
eprinttype = {ECCC},
eprint = {TR04-034},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-034.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-035,
author = {Scott Contini and
Ernie Croot and
Igor E. Shparlinski},
title = {Complexity of Inverting the Euler Function},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-035}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-035/index.html},
eprinttype = {ECCC},
eprint = {TR04-035},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-035.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-036,
author = {Ziv Bar{-}Yossef and
T. S. Jayram and
Iordanis Kerenidis},
title = {Exponential Separation of Quantum and Classical One-Way Communication
Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-036}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-036/index.html},
eprinttype = {ECCC},
eprint = {TR04-036},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-036.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-037,
author = {Elmar B{\"{o}}hler and
Christian Gla{\ss}er and
Bernhard Schwarz and
Klaus W. Wagner},
title = {Generation Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-037}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-037/index.html},
eprinttype = {ECCC},
eprint = {TR04-037},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-037.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-038,
author = {John Case and
Sanjay Jain and
R{\"{u}}diger Reischuk and
Frank Stephan and
Thomas Zeugmann},
title = {A Polynomial Time Learner for a Subclass of Regular Patterns},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-038}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-038/index.html},
eprinttype = {ECCC},
eprint = {TR04-038},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-038.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-039,
author = {Andrzej Lingas and
Martin Wahlen},
title = {On approximation of the maximum clique minor containment problem and
some subgraph homeomorphism problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-039}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-039/index.html},
eprinttype = {ECCC},
eprint = {TR04-039},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-039.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-040,
author = {Venkatesan Guruswami and
Alexander Vardy},
title = {Maximum-likelihood decoding of Reed-Solomon codes is NP-hard},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-040}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-040/index.html},
eprinttype = {ECCC},
eprint = {TR04-040},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-040.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-041,
author = {Michael Alekhnovich and
Edward A. Hirsch and
Dmitry Itsykson},
title = {Exponential lower bounds for the running time of {DPLL} algorithms
on satisfiable formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-041}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-041/index.html},
eprinttype = {ECCC},
eprint = {TR04-041},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-041.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-042,
author = {Ran Raz},
title = {Multilinear-NC\({}_{\mbox{1}}\) != Multilinear-NC\({}_{\mbox{2}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-042}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-042/index.html},
eprinttype = {ECCC},
eprint = {TR04-042},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-042.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-043,
author = {Luca Trevisan},
title = {Some Applications of Coding Theory in Computational Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-043}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-043/index.html},
eprinttype = {ECCC},
eprint = {TR04-043},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-043.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-044,
author = {Eric Allender and
Harry Buhrman and
Michal Kouck{\'{y}}},
title = {What Can be Efficiently Reduced to the Kolmogorov-Random Strings?},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-044}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-044/index.html},
eprinttype = {ECCC},
eprint = {TR04-044},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-044.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-045,
author = {Hartmut Klauck and
Robert Spalek and
Ronald de Wolf},
title = {Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space
Tradeoffs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-045}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-045/index.html},
eprinttype = {ECCC},
eprint = {TR04-045},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-045.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-046,
author = {Eli Ben{-}Sasson and
Madhu Sudan},
title = {Robust Locally Testable Codes and Products of Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-046}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-046/index.html},
eprinttype = {ECCC},
eprint = {TR04-046},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-046.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-047,
author = {Xiaoyang Gu},
title = {A note on dimensions of polynomial size circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-047}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-047/index.html},
eprinttype = {ECCC},
eprint = {TR04-047},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-047.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-048,
author = {Andr{\'{e}} Lanka and
Andreas Goerdt},
title = {An approximation hardness result for bipartite Clique},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-048}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-048/index.html},
eprinttype = {ECCC},
eprint = {TR04-048},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-048.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-049,
author = {Piotr Berman and
Marek Karpinski and
Yakov Nekrich},
title = {Optimal Trade-Off for Merkle Tree Traversal},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-049}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-049/index.html},
eprinttype = {ECCC},
eprint = {TR04-049},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-049.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-050,
author = {Michelle Effros and
Leonard J. Schulman},
title = {Deterministic clustering with data nets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-050}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-050/index.html},
eprinttype = {ECCC},
eprint = {TR04-050},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-050.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-051,
author = {Zdenek Dvor{\'{a}}k and
Daniel Kr{\'{a}}l and
Ondrej Pangr{\'{a}}c},
title = {Locally consistent constraint satisfaction problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-051}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-051/index.html},
eprinttype = {ECCC},
eprint = {TR04-051},
timestamp = {Fri, 01 Dec 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-051.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-052,
author = {Michael Ben{-}Or and
Don Coppersmith and
Michael Luby and
Ronitt Rubinfeld},
title = {Non-Abelian Homomorphism Testing, and Distributions Close to their
Self-Convolutions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-052}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-052/index.html},
eprinttype = {ECCC},
eprint = {TR04-052},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-052.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-053,
author = {Aduri Pavan and
N. V. Vinodchandran},
title = {Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-053}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-053/index.html},
eprinttype = {ECCC},
eprint = {TR04-053},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-053.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-054,
author = {Andrei A. Muchnik and
Alexander Shen and
Nikolai K. Vereshchagin and
Michael V. Vyugin},
title = {Non-reducible descriptions for conditional Kolmogorov complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-054}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-054/index.html},
eprinttype = {ECCC},
eprint = {TR04-054},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-054.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-055,
author = {Kousha Etessami and
Andreas Lochbihler},
title = {The computational complexity of Evolutionarily Stable Strategies},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-055}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-055/index.html},
eprinttype = {ECCC},
eprint = {TR04-055},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-055.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-056,
author = {N. V. Vinodchandran},
title = {A note on the circuit complexity of {PP}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-056}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-056/index.html},
eprinttype = {ECCC},
eprint = {TR04-056},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-056.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-057,
author = {M{\'{o}}nica del Pilar Canales Chacon and
Michael Vielhaber},
title = {Structural and Computational Complexity of Isometries and their Shift
Commutators},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-057}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-057/index.html},
eprinttype = {ECCC},
eprint = {TR04-057},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-057.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-058,
author = {John Case and
Sanjay Jain and
Eric Martin and
Arun Sharma and
Frank Stephan},
title = {Identifying Clusters from Positive Data},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-058}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-058/index.html},
eprinttype = {ECCC},
eprint = {TR04-058},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-058.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-059,
author = {Beatrice List and
Markus Maucher and
Uwe Sch{\"{o}}ning and
Rainer Schuler},
title = {Randomized Quicksort and the Entropy of the Random Number Generator},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-059}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-059/index.html},
eprinttype = {ECCC},
eprint = {TR04-059},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-059.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-060,
author = {Eli Ben{-}Sasson and
Madhu Sudan},
title = {Simple PCPs with Poly-log Rate and Query Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-060}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-060/index.html},
eprinttype = {ECCC},
eprint = {TR04-060},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-060.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-061,
author = {Scott Aaronson},
title = {The Complexity of Agreement},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-061}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-061/index.html},
eprinttype = {ECCC},
eprint = {TR04-061},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-061.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-062,
author = {Stasys Jukna},
title = {A note on the {P} versus {NP} intersected with co-NP question in communication
complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-062}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-062/index.html},
eprinttype = {ECCC},
eprint = {TR04-062},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-062.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-063,
author = {Yehuda Lindell and
Benny Pinkas},
title = {A Proof of Yao's Protocol for Secure Two-Party Computation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-063}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-063/index.html},
eprinttype = {ECCC},
eprint = {TR04-063},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-063.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-064,
author = {Piotr Faliszewski},
title = {Exponential time reductions and sparse languages in {NEXP}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-064}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-064/index.html},
eprinttype = {ECCC},
eprint = {TR04-064},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-064.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-065,
author = {Luca Trevisan},
title = {Inapproximability of Combinatorial Optimization Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-065}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-065/index.html},
eprinttype = {ECCC},
eprint = {TR04-065},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-065.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-066,
author = {Tomoyuki Yamakami and
Toshio Suzuki},
title = {Resource Bounded Immunity and Simplicity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-066}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-066/index.html},
eprinttype = {ECCC},
eprint = {TR04-066},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-066.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-067,
author = {Hadi Salmasian and
Ravindran Kannan and
Santosh S. Vempala},
title = {The Spectral Method for Mixture Models},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-067}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-067/index.html},
eprinttype = {ECCC},
eprint = {TR04-067},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-067.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-068,
author = {Nir Ailon and
Bernard Chazelle},
title = {Information Theory in Property Testing and Monotonicity Testing in
Higher Dimension},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-068}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-068/index.html},
eprinttype = {ECCC},
eprint = {TR04-068},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-068.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-069,
author = {Eran Rom and
Amnon Ta{-}Shma},
title = {Improveing the alphabet size in high noise, almost optimal rate list
decodable codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-069}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-069/index.html},
eprinttype = {ECCC},
eprint = {TR04-069},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-069.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-070,
author = {Leonid Gurvits},
title = {Combinatorial and algorithmic aspects of hyperbolic polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-070}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-070/index.html},
eprinttype = {ECCC},
eprint = {TR04-070},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-070.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-071,
author = {Marcus Schaefer and
Stephen A. Fenner},
title = {Simplicity and Strong Reductions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-071}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-071/index.html},
eprinttype = {ECCC},
eprint = {TR04-071},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-071.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-072,
author = {John M. Hitchcock},
title = {Hausdorff Dimension and Oracle Constructions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-072}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-072/index.html},
eprinttype = {ECCC},
eprint = {TR04-072},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-072.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-073,
author = {Henning Fernau},
title = {A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting
Set},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-073}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-073/index.html},
eprinttype = {ECCC},
eprint = {TR04-073},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-073.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-074,
author = {Emanuele Viola},
title = {On Parallel Pseudorandom Generators},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-074}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-074/index.html},
eprinttype = {ECCC},
eprint = {TR04-074},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-074.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-075,
author = {Michael Schmitt},
title = {Some dichotomy theorems for neural learning problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-075}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-075/index.html},
eprinttype = {ECCC},
eprint = {TR04-075},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-075.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-076,
author = {Oliver Giel and
Ingo Wegener},
title = {Searching Randomly for Maximum Matchings},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-076}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-076/index.html},
eprinttype = {ECCC},
eprint = {TR04-076},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-076.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-077,
author = {Alina Beygelzimer and
Varsha Dani and
Thomas P. Hayes and
John Langford},
title = {Reductions Between Classification Tasks},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-077}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-077/index.html},
eprinttype = {ECCC},
eprint = {TR04-077},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-077.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-078,
author = {Henning Fernau},
title = {Two-Layer Planarization: Improving on Parameterized Algorithmics},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-078}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-078/index.html},
eprinttype = {ECCC},
eprint = {TR04-078},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-078.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-079,
author = {John M. Hitchcock and
Jack H. Lutz and
Sebastiaan Terwijn},
title = {The Arithmetical Complexity of Dimension and Randomness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-079}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-079/index.html},
eprinttype = {ECCC},
eprint = {TR04-079},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-079.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-080,
author = {Lance Fortnow and
Troy Lee and
Nikolai K. Vereshchagin},
title = {Kolmogorov Complexity with Error},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-080}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-080/index.html},
eprinttype = {ECCC},
eprint = {TR04-080},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-080.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-081,
author = {Harry Buhrman and
Lance Fortnow and
Ilan Newman and
Nikolai K. Vereshchagin},
title = {Increasing Kolmogorov Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-081}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-081/index.html},
eprinttype = {ECCC},
eprint = {TR04-081},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-081.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-082,
author = {Olaf Beyersdorff},
title = {Representable Disjoint NP-Pairs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-082}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-082/index.html},
eprinttype = {ECCC},
eprint = {TR04-082},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-082.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-083,
author = {Boaz Barak and
Yehuda Lindell and
Salil P. Vadhan},
title = {Lower Bounds for Non-Black-Box Zero Knowledge},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-083}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-083/index.html},
eprinttype = {ECCC},
eprint = {TR04-083},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-083.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-084,
author = {George Karakostas},
title = {A better approximation ratio for the Vertex Cover problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-084}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-084/index.html},
eprinttype = {ECCC},
eprint = {TR04-084},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-084.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-085,
author = {Erez Petrank and
Guy N. Rothblum},
title = {Selection from Structured Data Sets},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-085}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-085/index.html},
eprinttype = {ECCC},
eprint = {TR04-085},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-085.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-086,
author = {Ronen Shaltiel and
Christopher Umans},
title = {Pseudorandomness for Approximate Counting and Sampling},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-086}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-086/index.html},
eprinttype = {ECCC},
eprint = {TR04-086},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-086.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-087,
author = {Alexander Healy and
Salil P. Vadhan and
Emanuele Viola},
title = {Using Nondeterminism to Amplify Hardness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-087}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-087/index.html},
eprinttype = {ECCC},
eprint = {TR04-087},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-087.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-088,
author = {Emanuele Viola and
Dan Gutfreund},
title = {Fooling Parity Tests with Parity Gates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-088}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-088/index.html},
eprinttype = {ECCC},
eprint = {TR04-088},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-088.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-089,
author = {Ingo Wegener},
title = {Simulated Annealing Beats Metropolis in Combinatorial Optimization},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-089}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-089/index.html},
eprinttype = {ECCC},
eprint = {TR04-089},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-089.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-090,
author = {Kazuyuki Amano and
Akira Maruoka},
title = {Better Simulation of Exponential Threshold Weights by Polynomial Weights},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-090}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-090/index.html},
eprinttype = {ECCC},
eprint = {TR04-090},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-090.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-091,
author = {Ondrej Kl{\'{\i}}ma and
Pascal Tesson and
Denis Th{\'{e}}rien},
title = {Dichotomies in the Complexity of Solving Systems of Equations over
Finite Semigroups},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-091}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-091/index.html},
eprinttype = {ECCC},
eprint = {TR04-091},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-091.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-092,
author = {Oded Lachish and
Ilan Newman},
title = {Testing Periodicity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-092}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-092/index.html},
eprinttype = {ECCC},
eprint = {TR04-092},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-092.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-093,
author = {Oded Goldreich and
Madhu Sudan and
Luca Trevisan},
title = {From logarithmic advice to single-bit advice},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-093}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-093/index.html},
eprinttype = {ECCC},
eprint = {TR04-093},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-093.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-094,
author = {Omer Reingold},
title = {Undirected ST-Connectivity in Log-Space},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-094}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-094/index.html},
eprinttype = {ECCC},
eprint = {TR04-094},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-094.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-095,
author = {Daniele Micciancio},
title = {Generalized compact knapsacks, cyclic lattices, and efficient one-way
functions from worst-case complexity assumptions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-095}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-095/index.html},
eprinttype = {ECCC},
eprint = {TR04-095},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-095.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-096,
author = {Eldar Fischer and
Fr{\'{e}}d{\'{e}}ric Magniez and
Michel de Rougemont},
title = {Property and Equivalence Testing on Strings},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-096}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-096/index.html},
eprinttype = {ECCC},
eprint = {TR04-096},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-096.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-097,
author = {V{\'{\i}}ctor Dalmau},
title = {Malt'sev Constraints made Simple},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-097}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-097/index.html},
eprinttype = {ECCC},
eprint = {TR04-097},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-097.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-098,
author = {Lance Fortnow and
Rahul Santhanam and
Luca Trevisan},
title = {Promise Hierarchies},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-098}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-098/index.html},
eprinttype = {ECCC},
eprint = {TR04-098},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-098.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-099,
author = {Ran Raz},
title = {Extractors with Weak Random Seeds},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-099}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-099/index.html},
eprinttype = {ECCC},
eprint = {TR04-099},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-099.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-100,
author = {Eric Allender and
Michael Bauland and
Neil Immerman and
Henning Schnoor and
Heribert Vollmer},
title = {The Complexity of Satisfiability Problems: Refining Schaefer's Theorem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-100}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-100/index.html},
eprinttype = {ECCC},
eprint = {TR04-100},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-100.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-101,
author = {Miroslav Chleb{\'{\i}}k and
Janka Chleb{\'{\i}}kov{\'{a}}},
title = {Crown reductions for the Minimum Weighted Vertex Cover problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-101}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-101/index.html},
eprinttype = {ECCC},
eprint = {TR04-101},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-101.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-102,
author = {Thomas Holenstein},
title = {Key Agreement from Weak Bit Agreement},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-102}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-102/index.html},
eprinttype = {ECCC},
eprint = {TR04-102},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-102.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-103,
author = {Lance Fortnow and
Adam R. Klivans},
title = {{NP} with Small Advice},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-103}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-103/index.html},
eprinttype = {ECCC},
eprint = {TR04-103},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-103.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-104,
author = {Mar{\'{\i}}a L{\'{o}}pez{-}Vald{\'{e}}s and
Elvira Mayordomo},
title = {Dimension is compression},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-104}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-104/index.html},
eprinttype = {ECCC},
eprint = {TR04-104},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-104.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-105,
author = {Eldar Fischer and
Lance Fortnow},
title = {Tolerant Versus Intolerant Testing for Boolean Properties},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-105}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-105/index.html},
eprinttype = {ECCC},
eprint = {TR04-105},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-105.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-106,
author = {Christian Gla{\ss}er and
Alan L. Selman and
Liyu Zhang},
title = {Canonical Disjoint NP-Pairs of Propositional Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-106}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-106/index.html},
eprinttype = {ECCC},
eprint = {TR04-106},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-106.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-107,
author = {Ingo Wegener and
Philipp Woelfel},
title = {New Results on the Complexity of the Middle Bit of Multiplication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-107}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-107/index.html},
eprinttype = {ECCC},
eprint = {TR04-107},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-107.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-108,
author = {Eric Allender and
Samir Datta and
Sambuddha Roy},
title = {Topology inside NC\({}^{\mbox{1}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-108}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-108/index.html},
eprinttype = {ECCC},
eprint = {TR04-108},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-108.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-109,
author = {Neeraj Kayal and
Nitin Saxena},
title = {On the Ring Isomorphism {\&} Automorphism Problems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-109}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-109/index.html},
eprinttype = {ECCC},
eprint = {TR04-109},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-109.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-110,
author = {Tomoyuki Yamakami and
Harumichi Nishimura},
title = {An Application of Quantum Finite Automata to Interactive Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-110}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-110/index.html},
eprinttype = {ECCC},
eprint = {TR04-110},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-110.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-111,
author = {Piotr Berman and
Marek Karpinski and
Alexander D. Scott},
title = {Computational Complexity of Some Restricted Instances of 3SAT},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-111}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-111/index.html},
eprinttype = {ECCC},
eprint = {TR04-111},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-111.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-112,
author = {Nicola Galesi and
Neil Thapen},
title = {Resolution and pebbling games},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-112}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-112/index.html},
eprinttype = {ECCC},
eprint = {TR04-112},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-112.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-113,
author = {M{\aa}rten Trolin},
title = {Lattices with Many Cycles Are Dense},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-113}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-113/index.html},
eprinttype = {ECCC},
eprint = {TR04-113},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-113.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-114,
author = {Vladimir Trifonov},
title = {An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-114}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-114/index.html},
eprinttype = {ECCC},
eprint = {TR04-114},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-114.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-115,
author = {Iftach Haitner and
Ronen Shaltiel},
title = {Statistical Zero-Knowledge Arguments for {NP} Using Approximable-Preimage-Size
One-Way Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-115}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-115/index.html},
eprinttype = {ECCC},
eprint = {TR04-115},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-115.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-116,
author = {Ludovic Perret},
title = {On the computational complexity of some equivalence problems of polynomial
systems of equations over finite fields},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-116}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-116/index.html},
eprinttype = {ECCC},
eprint = {TR04-116},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-116.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-117,
author = {Mikhail Alecknovich and
Sanjeev Arora and
Iannis Tourlakis},
title = {Towards strong nonapproximability results in the Lovasz-Schrijver
hierarchy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-117}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-117/index.html},
eprinttype = {ECCC},
eprint = {TR04-117},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-117.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-118,
author = {Marek Karpinski and
Yakov Nekrich},
title = {A Note on Traversing Skew Merkle Trees},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-118}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-118/index.html},
eprinttype = {ECCC},
eprint = {TR04-118},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-118.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-119,
author = {Uriel Feige and
Daniel Reichman},
title = {On The Hardness of Approximating Max-Satisfy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-119}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-119/index.html},
eprinttype = {ECCC},
eprint = {TR04-119},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-119.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-120,
author = {Andris Ambainis and
William I. Gasarch and
Aravind Srinivasan and
Andrey Utis},
title = {Lower bounds on the Deterministic and Quantum Communication Complexity
of HAM\({}_{\mbox{n}}\)\({}^{\mbox{a}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-120}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-120/index.html},
eprinttype = {ECCC},
eprint = {TR04-120},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-120.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR04-121,
author = {Vikraman Arvind and
Piyush P. Kurur and
T. C. Vijayaraghavan},
title = {Bounded Color Multiplicity Graph Isomorphism is in the {\#}L Hierarchy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR04-121}},
year = {2004},
url = {https://eccc.weizmann.ac.il/eccc-reports/2004/TR04-121/index.html},
eprinttype = {ECCC},
eprint = {TR04-121},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR04-121.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
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.
retrieved on 2024-04-23 17:49 CEST from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
