Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Nathan Segerlind
@article{DBLP:journals/siamcomp/PitassiS12,
author = {Toniann Pitassi and
Nathan Segerlind},
title = {Exponential Lower Bounds and Integrality Gaps for Tree-Like Lov{\'{a}}sz-Schrijver
Procedures},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {1},
pages = {128--159},
year = {2012},
url = {https://doi.org/10.1137/100816833},
doi = {10.1137/100816833},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/PitassiS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/BeameIPS10,
author = {Paul Beame and
Russell Impagliazzo and
Toniann Pitassi and
Nathan Segerlind},
title = {Formula Caching in {DPLL}},
journal = {{ACM} Trans. Comput. Theory},
volume = {1},
number = {3},
pages = {9:1--9:33},
year = {2010},
url = {https://doi.org/10.1145/1714450.1714452},
doi = {10.1145/1714450.1714452},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/BeameIPS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/PitassiS09,
author = {Toniann Pitassi and
Nathan Segerlind},
editor = {Claire Mathieu},
title = {Exponential lower bounds and integrality gaps for tree-like Lov{\'{a}}sz-Schrijver
procedures},
booktitle = {Proceedings of the Twentieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2009, New York, NY, USA, January 4-6, 2009},
pages = {355--364},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611973068.40},
doi = {10.1137/1.9781611973068.40},
timestamp = {Mon, 12 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/PitassiS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Segerlind08,
author = {Nathan Segerlind},
title = {On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary
Decision Diagram Proofs},
booktitle = {Proceedings of the 23rd Annual {IEEE} Conference on Computational
Complexity, {CCC} 2008, 23-26 June 2008, College Park, Maryland, {USA}},
pages = {100--111},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/CCC.2008.34},
doi = {10.1109/CCC.2008.34},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Segerlind08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/bsl/Segerlind07,
author = {Nathan Segerlind},
title = {The Complexity of Propositional Proofs},
journal = {Bull. Symb. Log.},
volume = {13},
number = {4},
pages = {417--481},
year = {2007},
url = {https://doi.org/10.2178/bsl/1203350879},
doi = {10.2178/BSL/1203350879},
timestamp = {Fri, 03 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/bsl/Segerlind07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BeamePS07,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind},
title = {Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow
from Multiparty Communication Complexity},
journal = {{SIAM} J. Comput.},
volume = {37},
number = {3},
pages = {845--869},
year = {2007},
url = {https://doi.org/10.1137/060654645},
doi = {10.1137/060654645},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BeamePS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0701054,
author = {Nathan Segerlind},
title = {Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination
Algorithms and OBDD-Based Proofs of Unsatisfiability},
journal = {CoRR},
volume = {abs/cs/0701054},
year = {2007},
url = {http://arxiv.org/abs/cs/0701054},
eprinttype = {arXiv},
eprint = {cs/0701054},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0701054.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Segerlind07,
author = {Nathan Segerlind},
title = {Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination
Algorithms and OBDD-Based Proofs of Unsatisfiability},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-009}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-009/index.html},
eprinttype = {ECCC},
eprint = {TR07-009},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Segerlind07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Segerlind07a,
author = {Nathan Segerlind},
title = {On the relative efficiency of resolution-like proofs and ordered binary
decision diagram proofs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-126}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-126/index.html},
eprinttype = {ECCC},
eprint = {TR07-126},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Segerlind07a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/SegerlindP07,
author = {Nathan Segerlind and
Toniann Pitassi},
title = {Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver
procedures},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-107}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-107/index.html},
eprinttype = {ECCC},
eprint = {TR07-107},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/SegerlindP07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BeamePSW06,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind and
Avi Wigderson},
title = {A Strong Direct Product Theorem for Corruption and the Multiparty
Communication Complexity of Disjointness},
journal = {Comput. Complex.},
volume = {15},
number = {4},
pages = {391--432},
year = {2006},
url = {https://doi.org/10.1007/s00037-007-0220-2},
doi = {10.1007/S00037-007-0220-2},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/BeamePSW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/ImpagliazzoS06,
author = {Russell Impagliazzo and
Nathan Segerlind},
title = {Constant-depth Frege systems with counting axioms polynomially simulate
Nullstellensatz refutations},
journal = {{ACM} Trans. Comput. Log.},
volume = {7},
number = {2},
pages = {199--218},
year = {2006},
url = {https://doi.org/10.1145/1131313.1131314},
doi = {10.1145/1131313.1131314},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tocl/ImpagliazzoS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeameIPS06,
author = {Paul Beame and
Russell Impagliazzo and
Toniann Pitassi and
Nathan Segerlind},
title = {Formula Caching in {DPLL}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-140}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-140/index.html},
eprinttype = {ECCC},
eprint = {TR06-140},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeameIPS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Segerlind05,
author = {Nathan Segerlind},
title = {Exponential separation between Res(\emph{k}) and Res(\emph{k}+1) for
\emph{k} leq varepsilonlog\emph{n}},
journal = {Inf. Process. Lett.},
volume = {93},
number = {4},
pages = {185--190},
year = {2005},
url = {https://doi.org/10.1016/j.ipl.2004.09.024},
doi = {10.1016/J.IPL.2004.09.024},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Segerlind05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BeamePSW05,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind and
Avi Wigderson},
title = {A Direct Sum Theorem for Corruption and the Multiparty {NOF} Communication
Complexity of Set Disjointness},
booktitle = {20th Annual {IEEE} Conference on Computational Complexity {(CCC} 2005),
11-15 June 2005, San Jose, CA, {USA}},
pages = {52--66},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/CCC.2005.1},
doi = {10.1109/CCC.2005.1},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/BeamePSW05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BeamePS05,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind},
editor = {Lu{\'{\i}}s Caires and
Giuseppe F. Italiano and
Lu{\'{\i}}s Monteiro and
Catuscia Palamidessi and
Moti Yung},
title = {Lower Bounds for Lov{\'{a}}sz-Schrijver Systems and Beyond Follow
from Multiparty Communication Complexity},
booktitle = {Automata, Languages and Programming, 32nd International Colloquium,
{ICALP} 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3580},
pages = {1176--1188},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11523468\_95},
doi = {10.1007/11523468\_95},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/BeamePS05.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/siamcomp/SegerlindBI04,
author = {Nathan Segerlind and
Samuel R. Buss and
Russell Impagliazzo},
title = {A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF
Resolution},
journal = {{SIAM} J. Comput.},
volume = {33},
number = {5},
pages = {1171--1200},
year = {2004},
url = {https://doi.org/10.1137/S0097539703428555},
doi = {10.1137/S0097539703428555},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/SegerlindBI04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BeameIPS03,
author = {Paul Beame and
Russell Impagliazzo and
Toniann Pitassi and
Nathan Segerlind},
title = {Memoization and {DPLL:} Formula Caching Proof Systems},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {248},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214425},
doi = {10.1109/CCC.2003.1214425},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/BeameIPS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/cs-CC-0308012,
author = {Russell Impagliazzo and
Nathan Segerlind},
title = {Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate
Nullstellensatz Refutations},
journal = {CoRR},
volume = {cs.CC/0308012},
year = {2003},
url = {http://arxiv.org/abs/cs/0308012},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-CC-0308012.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/SegerlindBI02,
author = {Nathan Segerlind and
Samuel R. Buss and
Russell Impagliazzo},
title = {A Switching Lemma for Small Restrictions and Lower Bounds for k -
{DNF} Resolution},
booktitle = {43rd Symposium on Foundations of Computer Science {(FOCS} 2002), 16-19
November 2002, Vancouver, BC, Canada, Proceedings},
pages = {604},
publisher = {{IEEE} Computer Society},
year = {2002},
url = {https://doi.org/10.1109/SFCS.2002.1181984},
doi = {10.1109/SFCS.2002.1181984},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/SegerlindBI02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ImpagliazzoS02,
author = {Russell Impagliazzo and
Nathan Segerlind},
editor = {Peter Widmayer and
Francisco Triguero Ruiz and
Rafael Morales Bueno and
Matthew Hennessy and
Stephan J. Eidenbenz and
Ricardo Conejo},
title = {Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate
Nullstellensatz Refutations},
booktitle = {Automata, Languages and Programming, 29th International Colloquium,
{ICALP} 2002, Malaga, Spain, July 8-13, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2380},
pages = {208--219},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45465-9\_19},
doi = {10.1007/3-540-45465-9\_19},
timestamp = {Wed, 11 Sep 2019 13:15:53 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ImpagliazzoS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ImpagliazzoS01,
author = {Russell Impagliazzo and
Nathan Segerlind},
title = {Counting Axioms Do Not Polynomially Simulate Counting Gates},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {200--209},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959894},
doi = {10.1109/SFCS.2001.959894},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ImpagliazzoS01.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.
last updated on 2024-04-25 01:20 CEST 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:
