Stasys Jukna

According to our database1, Stasys Jukna authored at least 90 papers between 1986 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
Greedy can beat pure dynamic programming.
Inf. Process. Lett., 2019

Lower Bounds for DeMorgan Circuits of Bounded Negation Width.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018
Incremental versus non-incremental dynamic programming.
Oper. Res. Lett., 2018

Approximation Limitations of Tropical Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Greedy can also beat pure dynamic programming.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Lower Bounds for Circuits of Bounded Negation Width.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Derandomizing Dynamic Programming and Beyond.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Incremental versus Non-Incremental Dynamic Programming.
Electronic Colloquium on Computational Complexity (ECCC), 2018

2016
On the optimality of Bellman-Ford-Moore shortest path algorithm.
Theor. Comput. Sci., 2016

Tropical Complexity, Sidon Sets, and Dynamic Programming.
SIAM J. Discrete Math., 2016

Tropical Complexity, Sidon Sets, and Dynamic Programming.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Lower bounds for monotone counting circuits.
Discrete Applied Mathematics, 2016

2015
Lower Bounds for Tropical Circuits and Dynamic Programs.
Theory Comput. Syst., 2015

On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm.
Electronic Colloquium on Computational Complexity (ECCC), 2015

2014
Lower Bounds for Monotone Counting Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Lower Bounds for Tropical Circuits and Dynamic Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Boolean Function Complexity Advances and Frontiers.
Bulletin of the EATCS, 2014

Limitations of Incremental Dynamic Programming.
Algorithmica, 2014

2013
Complexity of Linear Boolean Operators.
Foundations and Trends in Theoretical Computer Science, 2013

2012
Cutting planes cannot approximate some integer programs.
Oper. Res. Lett., 2012

Clique problem, cutting plane proofs and communication complexity.
Inf. Process. Lett., 2012

Limitations of Incremental Dynamic Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Clique Problem, Cutting Plane Proofs, and Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Boolean Function Complexity - Advances and Frontiers.
Algorithms and combinatorics 27, Springer, ISBN: 978-3-642-24507-7, 2012

2011
Extremal Combinatorics - With Applications in Computer Science
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-642-17364-6, 2011

Yet harder knapsack problems.
Theor. Comput. Sci., 2011

Min-rank conjecture for log-depth circuits.
J. Comput. Syst. Sci., 2011

2010
On convex complexity measures.
Theor. Comput. Sci., 2010

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits.
Theory Comput. Syst., 2010

Representing (0, 1)-matrices by boolean circuits.
Discrete Mathematics, 2010

2009
On set intersection representations of graphs.
Journal of Graph Theory, 2009

A nondeterministic space-time tradeoff for linear codes.
Inf. Process. Lett., 2009

Min-Rank Conjecture for Log-Depth Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2009

On convex complexity measures.
Electronic Colloquium on Computational Complexity (ECCC), 2009

On covering graphs by complete bipartite subgraphs.
Discrete Mathematics, 2009

2008
Expanders and time-restricted branching programs.
Theor. Comput. Sci., 2008

Entropy of operators or why matrix multiplication is hard for small depth circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Crashkurs Mathematik für Informatiker.
Leitfäden der Informatik, Teubner, ISBN: 978-3-8351-0216-3, 2008

2006
Disproving the Single Level Conjecture.
SIAM J. Comput., 2006

On Graph Complexity.
Combinatorics, Probability & Computing, 2006

Graphs and Circuits: Some Further Remarks.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Very Large Cliques are Easy to Detect.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005
On the P versus NP intersected with co-NP question in communication complexity.
Inf. Process. Lett., 2005

Expanders and time-restricted branching programs
Electronic Colloquium on Computational Complexity (ECCC), 2005

Disproving the single level conjecture
Electronic Colloquium on Computational Complexity (ECCC), 2005

2004
On the minimum number of negations leading to super-polynomial savings.
Inf. Process. Lett., 2004

On multi-partition communication complexity.
Inf. Comput., 2004

A note on the P versus NP intersected with co-NP question in communication complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

On Graph Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

2003
On uncertainty versus size in branching programs.
Theor. Comput. Sci., 2003

2002
Triangle-Freeness Is Hard To Detect.
Combinatorics, Probability & Computing, 2002

2001
On Multipartition Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2001

A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Multi-Partition Communication Complexity of Triangle-Freeness
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Uncertainty versus Size in Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 2001

On Multipartition Communication Complexity.
Proceedings of the STACS 2001, 2001

Extremal Combinatorics - With Applications in Computer Science.
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-04650-0, 2001

2000
Some Notes on the Information Flow in Read-Once Branching Programs.
Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

1999
Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs.
Inf. Process. Lett., 1999

Combinatorics of Monotone Computations.
Combinatorica, 1999

On P versus NP cap co-NP for decision trees and read-once branching programs.
Computational Complexity, 1999

1998
Combinatorics of Monotone Computations
Electronic Colloquium on Computational Complexity (ECCC), 1998

On Branching Programs With Bounded Uncertainty
Electronic Colloquium on Computational Complexity (ECCC), 1998

Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discrete Applied Mathematics, 1998

On Branching Programs With Bounded Uncertainty (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1997

Exponential Lower Bounds for Semantic Resolution
Electronic Colloquium on Computational Complexity (ECCC), 1997

On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Finite Limits and Monotone Computations: The Lower Bounds Criterion.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Neither Reading Few Bits Twice nor Reading Illegally Helps Much
Electronic Colloquium on Computational Complexity (ECCC), 1996

Finite Limits and Monotone Computations
Electronic Colloquium on Computational Complexity (ECCC), 1996

Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
Proceedings of the STACS 96, 1996

Exponential lower bounds for semantic resolution.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

On Communication Games with More than Two Players
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

The Graph of Integer Multiplication is Hard for Read-k-Times Networks
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

On Multiparity Games for Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

A Note on Read-k Times Branching Programs.
ITA, 1995

Computing Threshold Functions by Depth-3 Threshold Circuits with Smaller Thresholds of Their Gates.
Inf. Process. Lett., 1995

Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Electronic Colloquium on Computational Complexity (ECCC), 1995

Top-Down Lower Bounds for Depth-Three Circuits.
Computational Complexity, 1995

1994
Finite Limits and Lower Bounds for Circuits Size
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1994

A Note on Read-k Times Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1994

1993
Top-Down Lower Bounds for Depth 3 Circuits
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1991
Optimal versus Stable in Boolean Formulae.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1989
The Effect of Null-Chains on the Complexity of Contact Schemes.
Proceedings of the Fundamentals of Computation Theory, 1989

1988
Entropy of Contact Circuits and Lower Bounds on Their Complexity.
Theor. Comput. Sci., 1988

Two Lower Bounds for Circuits over the Basis (&, V, -).
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1987
Information Flow and Width of Branching Programs (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 1987

1986
Lower Bounds on the Complexity of Local Circuits (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986


  Loading...