Stasys Jukna

Orcid: 0000-0002-2786-9326

Affiliations:
  • Vilnius University, Lithuania
  • Goethe University of Frankfurt, Germany (former)
  • University of Trier, Germany (former)


According to our database1, Stasys Jukna authored at least 84 papers between 1986 and 2022.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
Lower bounds for Boolean circuits of bounded negation width.
J. Comput. Syst. Sci., 2022

Notes on Monotone Read-k Circuits.
Electron. Colloquium Comput. Complex., 2022

Notes on Boolean Read-k and Multilinear Circuits.
CoRR, 2022

2021
Notes on Hazard-Free Circuits.
SIAM J. Discret. Math., 2021

Tropical Kirchhoff's formula and postoptimality in matroid optimization.
Discret. Appl. Math., 2021

2020
Coin Flipping in Dynamic Programming Is Almost Useless.
ACM Trans. Comput. Theory, 2020

Approximation Limitations of Pure Dynamic Programming.
SIAM J. Comput., 2020

Sorting can exponentially speed up pure dynamic programming.
Inf. Process. Lett., 2020

Reciprocal Inputs in Arithmetic and Tropical Circuits.
Electron. Colloquium Comput. Complex., 2020

2019
Coin Flipping Cannot Shorten Arithmetic Computations.
Am. Math. Mon., 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.
Electron. Colloquium Comput. Complex., 2018

Greedy can also beat pure dynamic programming.
Electron. Colloquium Comput. Complex., 2018

Lower Bounds for Circuits of Bounded Negation Width.
Electron. Colloquium Comput. Complex., 2018

Derandomizing Dynamic Programming and Beyond.
Electron. Colloquium Comput. Complex., 2018

2017
Minkowski Complexity of Sets: An Easy Lower Bound.
Am. Math. Mon., 2017

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

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

2014
Lower Bounds for Monotone Counting Circuits.
Electron. Colloquium Comput. Complex., 2014

Lower Bounds for Tropical Circuits and Dynamic Programs.
Electron. Colloquium Comput. Complex., 2014

Boolean Function Complexity Advances and Frontiers.
Bull. EATCS, 2014

Limitations of Incremental Dynamic Programming.
Algorithmica, 2014

2013
Complexity of Linear Boolean Operators.
Found. Trends Theor. Comput. Sci., 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.
Electron. Colloquium Comput. Complex., 2012

Independent set problem for individual graphs has small communication complexity
CoRR, 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.
Discret. Math., 2010

Circuits with arbitrary gates for random operators
CoRR, 2010

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

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

On covering graphs by complete bipartite subgraphs.
Discret. Math., 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.
Electron. Colloquium Comput. Complex., 2008

Very large cliques are easy to detect.
Discret. Math., 2008

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

2006
On Graph Complexity.
Comb. Probab. Comput., 2006

Graphs and Circuits: Some Further Remarks.
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

Disproving the single level conjecture
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 2004

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

2002
Triangle-Freeness Is Hard To Detect.
Comb. Probab. Comput., 2002

2001
On Multipartition Communication Complexity
Electron. Colloquium Comput. Complex., 2001

A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
Electron. Colloquium Comput. Complex., 2001

On Multi-Partition Communication Complexity of Triangle-Freeness
Electron. Colloquium Comput. Complex., 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.
Comb., 1999

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

1998
On Branching Programs With Bounded Uncertainty
Electron. Colloquium Comput. Complex., 1998

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

1997
Exponential Lower Bounds for Semantic Resolution
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 1996

Finite Limits and Monotone Computations
Electron. Colloquium Comput. Complex., 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-<i>k</i> Times Branching Programs.
RAIRO Theor. Informatics Appl., 1995

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

Top-Down Lower Bounds for Depth-Three Circuits.
Comput. Complex., 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
Electron. Colloquium Comput. Complex., 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...