Nikolai K. Vereshchagin

Theor. Comput. Sci., 2023

Half-duplex communication complexity with adversary? can be less than the classical communication complexity.

[BibT_eX]

[DOI]

Mikhail Dektiarev

Electron. Colloquium Comput. Complex., 2023

On information content in certain objects.

[BibT_eX]

[DOI]

CoRR, 2023

2022

How much randomness is needed to convert MA protocols to AM protocols?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A Family of Non-Periodic Tilings of the Plane by Right Golden Triangles.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2022

2021

Proofs of conservation inequalities for Levin's notion of mutual information of 1974.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

High Entropy Random Selection Protocols.

[BibT_eX]

[DOI]

Algorithmica, 2021

2020

Descriptive complexity of computable sequences revisited.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

On the Structure of Ammann A2 Tilings.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

2019

Sparse Selfreducible Sets and Nonuniform Lower Bounds.

[BibT_eX]

[DOI]

Leen Torenvliet

Falk Unger

Algorithmica, 2019

2018

A Conditional Information Inequality and Its Combinatorial Applications.

[BibT_eX]

[DOI]

Tarik Kaced

IEEE Trans. Inf. Theory, 2018

Short lists with short programs in short time.

[BibT_eX]

[DOI]

Bruno Bauwens

Anton Makhlin

Marius Zimand

Comput. Complex., 2018

2017

Short lists with short programs from programs of functions and strings.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Stochasticity in Algorithmic Statistics for Polynomial Time.

[BibT_eX]

[DOI]

Alexey Milovanov

Electron. Colloquium Comput. Complex., 2017

Algorithmic Statistics: Forty Years Later.

[BibT_eX]

[DOI]

Proceedings of the Computability and Complexity, 2017

2016

Algorithmic Minimal Sufficient Statistics: a New Approach.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

Algorithmic statistics revisited.

[BibT_eX]

[DOI]

CoRR, 2015

Conditional Information Inequalities and Combinatorial Applications.

[BibT_eX]

[DOI]

Tarik Kaced

CoRR, 2015

2014

Editorial.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Encoding Invariance in Average Case Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Aperiodic Tilings by Right Triangles.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2014

Randomized Communication Complexity of Approximating Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Randomized communication complexity of appropximating Kolmogorov complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On Algorithmic Strong Sufficient Statistics.

[BibT_eX]

[DOI]

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

2012

Limit complexities revisited [once more]

[BibT_eX]

[DOI]

Laurent Bienvenu

CoRR, 2012

2011

Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances".

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

2010

Rate distortion and denoising of individual data using Kolmogorov complexity.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2010

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Limit Complexities Revisited.

[BibT_eX]

[DOI]

Laurent Bienvenu

Theory Comput. Syst., 2010

On abstract resource semantics and computability logic.

[BibT_eX]

[DOI]

Ilya Mezhirov

J. Comput. Syst. Sci., 2010

An Encoding Invariant Version of Polynomial Time Computable Distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Algorithmic Minimal Sufficient Statistics: a New Definition.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Game interpretation of Kolmogorov complexity

[BibT_eX]

[DOI]

Ilya Mezhirov

CoRR, 2010

2009

Kolmogorov Complexity and Model Selection.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2009

Algorithmic Minimal Sufficient Statistic Revisited.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

Kolmogorov Complexity and Games.

[BibT_eX]

Bull. EATCS, 2008

On Game Semantics of the Affine and Intuitionistic Logics.

[BibT_eX]

[DOI]

Ilya Mezhirov

Proceedings of the Logic, 2008

Randomised Individual Communication Complexity.

[BibT_eX]

[DOI]

Michal Koucký

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

On-Line Probability, Complexity and Randomness.

[BibT_eX]

[DOI]

Alexey V. Chernov

Vladimir Vovk

Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007

Non-reducible descriptions for conditional Kolmogorov complexity.

[BibT_eX]

[DOI]

Mikhail Ustinov

Michael V. Vyugin

Theor. Comput. Sci., 2007

Individual communication complexity.

[BibT_eX]

[DOI]

Hartmut Klauck

J. Comput. Syst. Sci., 2007

Kolmogorov complexity of enumerating finite sets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.

[BibT_eX]

[DOI]

Eur. J. Comb., 2007

Inverting Onto Functions and Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

On Computation and Communication with Small Bias.

[BibT_eX]

[DOI]

Ronald de Wolf

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Inverting onto functions might not be hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On Algorithmic Rate-Distortion Function.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Shannon Entropy vs. Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2006

2004

Kolmogorov's structure functions and model selection.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2004

Kolmogorov-Loveland stochasticity for finite strings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Increasing Kolmogorov Complexity

[BibT_eX]

[DOI]

Lance Fortnow

Ilan Newman

Electron. Colloquium Comput. Complex., 2004

Kolmogorov Complexity with Error

[BibT_eX]

[DOI]

Lance Fortnow

Troy Lee

Electron. Colloquium Comput. Complex., 2004

Non-reducible descriptions for conditional Kolmogorov complexity

[BibT_eX]

[DOI]

Michael V. Vyugin

Electron. Colloquium Comput. Complex., 2004

A Theory of Lossy Compression for Individual Data

[BibT_eX]

[DOI]

CoRR, 2004

Individual Communication Complexity: Extended Abstract.

[BibT_eX]

[DOI]

Hartmut Klauck

Proceedings of the STACS 2004, 2004

Ecological Turing Machines.

[BibT_eX]

[DOI]

Maxim Ushakov

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Do stronger definitions of randomness exist?

[BibT_eX]

[DOI]

Vladimir Kanovei

Vladimir A. Uspensky

Theor. Comput. Sci., 2003

How to use several noisy channels with unknown error probabilities.

[BibT_eX]

[DOI]

Olga Mitina

Inf. Comput., 2003

2002

Independent minimum length programs to translate between given strings.

[BibT_eX]

[DOI]

Michael V. Vyugin

Theor. Comput. Sci., 2002

Kolmogorov complexity conditional to large integers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Logical operations and Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Combinatorial interpretation of Kolmogorov complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Descriptive complexity of computable sequences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Upper semi-lattice of binary strings with the relation "x is simple conditional to y".

[BibT_eX]

[DOI]

Alexey V. Chernov

Theor. Comput. Sci., 2002

A new class of non-Shannon-type inequalities for entropies.

[BibT_eX]

[DOI]

Konstantin Makarychev

Yury Makarychev

Commun. Inf. Syst., 2002

Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middle.

[BibT_eX]

[DOI]

Alexey V. Chernov

Dmitrij P. Skvortsov

Elena Z. Skvortsova

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

Basic set theory.

[BibT_eX]

Student mathematical library 17, American Mathematical Society, ISBN: 978-0-8218-2731-4, 2002

2001

Logical operations and Kolmogorov complexity. II

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

An enumerable undecidable set with low prefix complexity: a simplified proof

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

2000

Inequalities for Shannon Entropy and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Daniel Hammer

J. Comput. Syst. Sci., 2000

1999

Arthur-Merlin Games in Boolean Decision Trees.

[BibT_eX]

[DOI]

Ran Raz

Gábor Tardos

Oleg Verbitsky

J. Comput. Syst. Sci., 1999

One Property of Cross-Intersecting Families

[BibT_eX]

[DOI]

Alexander A. Razborov

Electron. Colloquium Comput. Complex., 1999

Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y".

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Provability, complexity, grammars.

[BibT_eX]

Lev D. Beklemishev

Mati Pentus

American Mathematical Society translations series 2 192, American Mathematical Society, ISBN: 978-0-8218-1078-1, 1999

1998

Randomized Boolean Decision Trees: Several Remarks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Deterministic Rational Transducers and Random Sequences.

[BibT_eX]

[DOI]

Sylvain Porrot

Max Dauchet

Proceedings of the Foundations of Software Science and Computation Structure, 1998

1997

Inequalities for Shannon entropies and Kolmogorov complexities.

[BibT_eX]

[DOI]

Daniel Hammer

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

A General Method to Construct Oracles Realizing Given Relationships Between Complexity Classes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

1995

Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP.

[BibT_eX]

[DOI]

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

NP-sets are Co-NP-immune Relative to a Random Oracle.

[BibT_eX]

[DOI]

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknown.

[BibT_eX]

[DOI]

Olga Mitina

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1993

Banishing Robust Turing Completeness.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Sanjay Jain

Int. J. Found. Comput. Sci., 1993

Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On The Power of PP.

[BibT_eX]

[DOI]