Please note that I have left MIT and my webpages here will probably
cease to be maintained in a not too distant future.
This page is currently just a mirror of
www.csc.kth.se/~jakobn/research.
I will try to keep the lists below current, but the webpage at
KTH Royal Institute of Technology
will always be the most up-to-date version.
Research
On this webpage you find my
papers,
PhD thesis,
Master's thesis,
slides for
some presentations
and
miscellaneous other stuff.
Papers
-
Jakob Nordström.
New Wine into Old Wineskins: A Survey of Some
Pebbling Classics with Supplemental Results.
Manuscript in preparation.
To appear in
Foundations and Trends in Theoretical Computer Science.
Current draft version available for download—comments are welcome.
-
Jakob Nordström.
Pebble Games, Proof Complexity, and Time-Space Trade-offs.
To appear in
Logical Methods in Computer Science,
2013.
-
Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals.
Towards an Understanding of Polynomial Calculus: New Separations and
Lower Bounds (Extended Abstract).
To appear in
Proceedings of the 40th International Colloquium on
Automata, Languages and Programming (ICALP '13),
July 2013.
-
Chris Beck, Jakob Nordström, and Bansheng Tang.
Some Trade-off Results for Polynomial Calculus (Extended Abstract).
In
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC '13),
pages 813-822,
June 2013.
-
Jakob Nordström and Johan Håstad.
Towards an Optimal Separation of Space and Length in Resolution.
Theory of Computing,
volume 9, article 14, pages 471-557, May 2013.
-
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, and Neil Thapen.
Space Complexity in Polynomial Calculus.
Technical Report TR12-132,
Electronic Colloquium on Computational Complexity (ECCC),
October 2012.
-
Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný.
Relating Proof Complexity Measures and Practical Hardness of SAT.
In
Proceedings of the 18th International Conference on
Principles and Practice of Constraint Programming (CP '12),
pages 316-331, October 2012.
-
Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, and Noga Ron-Zewi.
Space Complexity in Polynomial Calculus (Extended Abstract).
In
Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC '12),
pages 334-344, June 2012.
-
Trinh Huynh and Jakob Nordström.
On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
Time-Space Trade-offs in Proof Complexity (Extended Abstract).
In
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12),
pages 233-248, May 2012.
-
Jakob Nordström.
On the Relative Strength of Pebbling and Resolution.
ACM Transactions on Computational Logic,
volume 13, issue 2, article 16, April 2012.
-
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, and Ning Xie.
On the Semantics of Local Characterizations for Linear-Invariant Properties.
Manuscript, 2011.
-
Jakob Nordström and Alexander Razborov.
On Minimal Unsatisfiability and
Time-Space Trade-offs for k-DNF Resolution.
In
Proceedings of the 38th International Colloquium on
Automata, Languages and Programming (ICALP '11),
pages 642-653, July 2011.
-
Eli Ben-Sasson and Jakob Nordström.
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions (Extended Abstract).
In
Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11),
pages 401-416, January 2011.
-
Eli Ben-Sasson and Jakob Nordström.
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
Technical Report TR10-125,
Electronic Colloquium on Computational Complexity (ECCC),
August 2010.
This is a merged and updated version of the two ECCC technical reports
TR09-034
and
TR09-047,
which two papers it subsumes.
-
Jakob Nordström.
On the Relative Strength of Pebbling and Resolution (Extended Abstract).
In
Proceedings of the 25th Annual IEEE Conference on
Computational Complexity (CCC '10),
pages 151-162, June 2010.
-
Jakob Nordström.
A Simplified Way of Proving Trade-off Results for Resolution.
Information Processing Letters,
volume 109, number 18, pages 1030-1035, August 2009.
-
Jakob Nordström.
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
SIAM Journal on Computing,
volume 39, issue 1, pages 59-121, May 2009.
(Special issue on STOC '06.)
-
Eli Ben-Sasson and Jakob Nordström.
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.
Technical Report TR09-002,
Electronic Colloquium on Computational Complexity (ECCC),
January 2009.
-
Eli Ben-Sasson and Jakob Nordström.
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.
In
Proceedings of the 49th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '08),
pages 709-718,
October 2008.
-
Jakob Nordström and Johan Håstad.
Towards an Optimal Separation of Space and Length in Resolution (Extended Abstract).
In
Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC '08),
pages 701-710,
May 2008.
-
Jakob Nordström.
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution (Extended Abstract).
In
Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC '06),
pages 507-516,
May 2006.
Co-winner of the Danny Lewin Best Student Paper Award.
PhD Thesis
Jakob Nordström.
Short Proofs May Be Spacious: Understanding Space in Resolution.
PhD thesis,
Royal Institute of Technology,
Stockholm, Sweden, May 2008.
Received the Ackermann Award 2009
for outstanding dissertations in
Logic in Computer Science from the
European Association for Computer Science Logic.
Master's Thesis
Jakob Nordström.
Stålmarck's Method Versus Resolution: A Comparative Theoretical Study.
Master's thesis TRITA-NA-E0184,
Stockholm University,
Stockholm, Sweden,
2001.
Some Presentations
-
Relating Proof Complexity Measures and Practical Hardness of SAT.
Talk given at the
First Symposium on Structure in Hard Combinatorial Problems
in Vienna, Austria, May 2013.
-
Rediscovering the Joys of Pebbling.
Talk given in the KTH Theory reading group,
April 2013.
-
Relating Proof Complexity Measures and Practical Hardness of SAT.
Talk given at the Dagstuhl seminar
SAT Interactions,
November 2012,
and at the University of Toronto, January 2013.
-
Relating Proof Complexity Measures and Practical Hardness of SAT.
Brief overview talk given at
CP '12, October 2012.
-
On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
Time-Space Trade-offs in Proof Complexity.
Talk given at the
Limits of Theorem Proving workshop in Rome, Italy, September 2012,
and (slightly modified) in the KTH Theory reading group, October 2012,
and at the Tata Institute of Fundamental Research in Mumbai, India, March 2013.
-
On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
Time-Space Trade-offs in Proof Complexity.
Brief overview talk given at
STOC '12, May 2012.
-
Understanding the Hardness of Proving Formulas in Propositional Logic.
Updated version of a
survey talk about SAT solving, proof complexity, and time-space trade-offs in resolution and other proof systems
given at Stockholm University,
November 2011.
-
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.
Brief talk given at
ICALP '11,
July 2011.
-
On Proof Complexity Lower Bounds and Possible Connections to SAT Solving.
Brief talk given at the
Synergies in Lower Bounds
workshop at Aarhus University, Denmark,
June-July 2011,
and (slightly modified)
at the Oberwolfach workshop
Mathematical Logic: Proof Theory, Constructive Mathematics,
November 2011.
-
On the Semantics of Local Characterizations
for Linear-Invariant Properties.
Brief talk given at the Dagstuhl seminar on
Computational Complexity of Discrete Problems,
March 2011.
-
On the Semantics of Local Characterizations
for Linear-Invariant Properties.
Talk given
in the KTH Theory Group seminar series, November 2010,
and (slightly modified) at the
Technion – Israel Institute of Technology in Haifa, Israel,
December 2010.
-
Understanding the Hardness of Proving Formulas in Propositional Logic.
Survey talk about SAT solving, proof complexity, and resolution time-space trade-offs
given at Lund University,
October 2010
and in a slightly expanded and more technical version at the
Complexity and Finite Models (CMF 2011) workshop
in Paris, June 2011.
-
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
Brief overview talk, with a slightly more applied angle, given at the
Propositional Proof Complexity: Theory and Practice workshop at
FLoC '10,
July 2010,
and (in a slightly shorter version) at
ICS '11,
January 2011.
-
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
Yet another survey talk
about my PhD thesis and some subsequent work,
but with a slightly more applied angle, given at the
International Workshop on Tractability
at Microsoft Research Cambridge, UK, July 2010.
-
On the Relative Strength of Pebbling and Resolution.
Brief overview talk given at
CCC '10,
June 2010,
and in the KTH Theory Group seminar series, October 2010.
(also available in video
from Harvard)
-
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
Survey talk about my PhD thesis and some subsequent work given
in the CSAIL Theory of Computation Colloquium series,
April 2010 and then (slightly modified) at the University of Toronto and
at KTH, May 2010.
Yet another modified and updated version of this talk, but with the title
Understanding the Hardness of Proving Formulas in Propositional Logic,
was given at the proof complexity workshop
at the Banff International Research Station in Canada, October 2011.
-
Understanding Space in Proof Complexity.
Survey talk about my PhD thesis and some subsequent work given
at the Ackermann Award ceremony at
CSL '09,
September 2009.
-
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
Brief overwiev talk
about the ECCC reports
TR09-034
and
TR09-047
given at the Barriers in Computational Complexity workshop in Princeton, USA, August 2009.
(also available in video
from the Center for Computational Intractability)
-
Guest lectures about proof complexity in the MIT Advanced Complexity Theory course,
April 2009.
Handwritten
lecture notes
and (mostly accurate)
scribed notes for lecture 1
and
lecture 2.
-
Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs.
Talk
about our
FOCS '08 paper
and
ECCC report TR09-034
given at the Dagstuhl seminar on
Computational Complexity of Discrete Problems,
September 2008,
and (slightly modified) in the MIT CSAIL Algorithms and Complexity Seminar series, October 2008.
-
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.
Brief overview talk given at
FOCS '08,
October 2008.
-
Towards an Optimal Separation of Space and Length in Resolution.
Brief overview talk given at
STOC '08
and at the NORDITA
Physics of distributed information systems (PhysDIS)
workshop in Stockholm, May 2008.
-
Towards an Optimal Separation of Space and Length in Resolution.
Talk given at
the Technion – Israel Institute of Technology in Haifa
and
the Weizmann Institute of Science in Rehovot,
Israel, March 2008.
Some technical slides in the appendix.
-
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Very detailed technical talk in the KTH Theory Group seminar series, June 2006.
-
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Brief overview talk given at
STOC '06,
May 2006.
-
Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Somewhat detailed talk given at
the Dagstuhl seminar on
Complexity of Boolean Functions in March 2006
and (slightly modified) at the Isaac Newton Institute Workshop
New Directions in Proof Complexity in Cambridge, UK, in April 2006.
(also available in audio
from the Isaac Newton Institute)
-
Short Proofs Are Narrow (Well, Sort of), But Are They Tight?
Fairly technical talk about width and space in resolution
in the KTH Theory Group PhD student seminar series, April 2006.
-
Stålmarck's Method versus Resolution: A Comparative Theoretical Study.
Rather informal overview of the subject matter of my Master's thesis, November 2001.
-
Stålmarck's Method versus Resolution: A Comparative Theoretical Study.
More technical account of the most important results in my Master's thesis, November 2001.
Miscellaneous
-
[in Swedish] Jakob Nordström.
Kort populärvetenskaplig
sammanfattning av min doktorsavhandling.
Försök till kort (knappt 2 sidor)
sammanfattning av ungefär vad min doktorsavhandling handlar om
och varför man är intresserad av att undersöka
den typen av frågor,
september 2009.
-
[in Swedish] Jakob Nordström.
Om formler, bevis och andra komplexa saker.
Något förkortad och översatt version av inledningskapitlet
i min doktorsavhandling
Short Proofs May Be Spacious:
Understanding Space in Resolution,
maj 2008.
Last updated: June 30, 2013.