Meena Mahajan

K. Vignesh

Inf. Process. Lett., January, 2024

Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs.

[BibT_eX]

[DOI]

Benjamin Böhm

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

On (simple) decision tree rank.

[BibT_eX]

[DOI]

Theor. Comput. Sci., November, 2023

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., April, 2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2023

New lower bounds for Polynomial Calculus over non-Boolean bases.

[BibT_eX]

[DOI]

Sasank Mouli

Electron. Colloquium Comput. Complex., 2023

Dependency schemes in CDCL-based QBF solving: a proof-theoretic study.

[BibT_eX]

[DOI]

Abhimanyu Choudhury

Electron. Colloquium Comput. Complex., 2023

Query Complexity of Search Problems.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2023

2022

QBF Merge Resolution is powerful but unnatural.

[BibT_eX]

[DOI]

Gaurav Sood

Electron. Colloquium Comput. Complex., 2022

2021

The Presburger Award for Young Scientists 2022 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2021

2020

MaxSAT Resolution and Subcube Sums.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Hard QBFs for Merge Resolution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution.

[BibT_eX]

[DOI]

Joshua Blinkhorn

Electron. Colloquium Comput. Complex., 2020

The Presburger Award for Young Scientists 2021 - Call for Nominations.

[BibT_eX]

[DOI]

Thore Husfeldt

Mikolaj Bojanczyk

Bull. EATCS, 2020

SAT and Interactions (Dagstuhl Seminar 20061).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2020

Lower bounds for linear decision lists.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Nikhil S. Mande

Chic. J. Theor. Comput. Sci., 2020

2019

The Presburger Award for Young Scientists 2020 - Call for Nominations.

[BibT_eX]

[DOI]

Thore Husfeldt

Anca Muscholl

Bull. EATCS, 2019

Research in theoretical computer science.

[BibT_eX]

[DOI]

Madhavan Mukund

Nitin Saxena

Commun. ACM, 2019

2018

Are Short Proofs Narrow? QBF Resolution Is Not So Simple.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2018

Sums of read-once formulas: How many summands are necessary?

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Shortest path length with bounded-alternation (min, +) formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Computing the maximum using (min, +) formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Short Proofs in QBF Expansion.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Building Strategies into QBF Proofs.

[BibT_eX]

[DOI]

Joshua Blinkhorn

Electron. Colloquium Comput. Complex., 2018

Lower Bound Techniques for QBF Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

2017

Understanding Cutting Planes for QBFs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

A Quest for Structure in Complexity.

[BibT_eX]

[DOI]

Vikraman Arvind

Bull. EATCS, 2017

Arithmetic Circuits: An Overview (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

VNP=VP in the multilinear world.

[BibT_eX]

[DOI]

Sébastien Tavenas

Inf. Process. Lett., 2016

Level-ordered Q-resolution and tree-like Q-resolution are incomparable.

[BibT_eX]

[DOI]

Anil Shukla

Inf. Process. Lett., 2016

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Relating two width measures for resolution proofs.

[BibT_eX]

[DOI]

Anil Shukla

Electron. Colloquium Comput. Complex., 2016

Homomorphism Polynomials Complete for VP.

[BibT_eX]

[DOI]

Arnaud Durand

Guillaume Malod

Nicolas de Rugy-Altherre

Chic. J. Theor. Comput. Sci., 2016

2015

Sums of read-once formulas: How many summands suffice?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Building above read-once polynomials: identity testing and hardness of representation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

The shifted partial derivative complexity of Elementary Symmetric Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Are Short Proofs Narrow? QBF Resolution is not Simple.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Feasible Interpolation for QBF Resolution Calculi.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Read-once polynomials: How many summands suffice?

[BibT_eX]

[DOI]

CoRR, 2015

2014

Monomials, multilinearity and identity testing in simple read-restricted circuits.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Space-Efficient Approximations for Subset Sum.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.

[BibT_eX]

[DOI]

Eric Allender

Vikraman Arvind

Theory Comput. Syst., 2013

Small Depth Proof Systems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Algebraic Complexity Classes.

[BibT_eX]

[DOI]

CoRR, 2013

Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas.

[BibT_eX]

[DOI]

Comput. Complex., 2013

Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits.

[BibT_eX]

[DOI]

Maurice J. Jansen

Comput. Complex., 2013

2012

The planar k-means problem is NP-hard.

[BibT_eX]

[DOI]

Kasturi R. Varadarajan

Theor. Comput. Sci., 2012

Counting classes and the fine structure between NC1 and L.

[BibT_eX]

[DOI]

Samir Datta

Gido Scharfenberger-Fabian

Michael Thomas

Heribert Vollmer

Theor. Comput. Sci., 2012

Verifying Proofs in Constant Depth.

[BibT_eX]

[DOI]

Michael Thomas

Heribert Vollmer

Electron. Colloquium Comput. Complex., 2012

Counting Paths in VPA Is Complete for #NC 1.

[BibT_eX]

[DOI]

Algorithmica, 2012

Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

The Complexity of Unary Subset Sum.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

Counting paths in planar width 2 branching programs.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, 2012

2011

Verifying Proofs in Constant Depth.

[BibT_eX]

[DOI]

Samir Datta

Gido Scharfenberger-Fabian

Michael Thomas

Heribert Vollmer

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Planarity, Determinants, Permanents, and (Unique) Matchings.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2010

On the Complexity of Matrix Rank and Rigidity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Arithmetizing Classes Around NC\textsf{NC}1 and L\textsf{L}.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Counting paths in VPA is complete for #NC1.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Longest Paths in Planar DAGs in Unambiguous Log-Space.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2010

Frontmatter, Table of Contents, Preface, Conference Organization, Author Index.

[BibT_eX]

[DOI]

Kamal Lodaya

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Parameterizing above or below guaranteed values.

[BibT_eX]

[DOI]

Somnath Sikdar

J. Comput. Syst. Sci., 2009

On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.

[BibT_eX]

[DOI]

Antoine Meyer

J. Autom. Lang. Comb., 2009

Upper Bounds for Monotone Planar Circuit Value and Variants.

[BibT_eX]

[DOI]

Comput. Complex., 2009

Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2009

Small-Space Analogues of Valiant's Classes.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

Small space analogues of Valiant's classes and the limitations of skew formula.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Longest Paths in Planar DAGs in Unambiguous Logspace.

[BibT_eX]

[DOI]

Proceedings of the Theory of Computing 2009, 2009

2008

Simultaneous matchings: Hardness and approximation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Rigidity of a simple extended lower triangular matrix.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Some perfect matchings and perfect half-integral matchings in NC.

[BibT_eX]

[DOI]

Raghav Kulkarni

Kasturi R. Varadarajan

Chic. J. Theor. Comput. Sci., 2008

2007

Block Sorting: A Characterization and some Heuristics.

[BibT_eX]

Nord. J. Comput., 2007

Arithmetizing classes around NC^1 and L.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Polynomial Size Log Depth Circuits: Between NC1 and AC1.

[BibT_eX]

Bull. EATCS, 2007

Arithmetizing Classes Around NC 1 and L.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

2006

Approximate Block Sorting.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2006

On the Complexity of Rank and Rigidity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Evaluating Monotone Circuits on Cylinders, Planes and Tori

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Parameterizing MAX SNP Problems Above Guaranteed Values.

[BibT_eX]

[DOI]

Somnath Sikdar

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

On the Bipartite Unique Perfect Matching Problem.

[BibT_eX]

[DOI]

Thanh Minh Hoang

Thomas Thierauf

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Simultaneous Matchings.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

The complexity of planarity testing.

[BibT_eX]

[DOI]

Eric Allender

Inf. Comput., 2004

The combinatorial approach yields an NC algorithm for computing Pfaffians.

[BibT_eX]

[DOI]

P. R. Subramanya

Discret. Appl. Math., 2004

Seeking a Vertex of the Planar Matching Polytope in NC.

[BibT_eX]

[DOI]

Raghav Kulkarni

Proceedings of the Algorithms, 2004

Towards Constructing Optimal Strip Move Sequences.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2003

On Sorting by 3-Bounded Transpositions.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2003

Merging and Sorting By Strip Moves.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2000

A note on the hardness of the characteristic polynomial

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).

[BibT_eX]

[DOI]

Kasturi R. Varadarajan

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Parameterizing above Guaranteed Values: MaxSat and MaxCut.

[BibT_eX]

[DOI]

J. Algorithms, 1999

A Combinatorial Algorithm for Pfaffians

[BibT_eX]

[DOI]

P. R. Subramanya

Electron. Colloquium Comput. Complex., 1999

Arithmetic Complexity, Kleene Closure, and Formal Power Series

[BibT_eX]

[DOI]

Eric Allender

Vikraman Arvind

Electron. Colloquium Comput. Complex., 1999

1998

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Determinant: Old Algorithms, New Insights

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Determinant: Old Algorithms, New Insights (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1998

1997

Parametrizing Above Guaranteed Values: MaxSat and MaxCut

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Determinant: Combinatorics, Algorithms, and Complexity.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1997

A Combinatorial Algorithm for the Determinant.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1995

Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

A Note on Mod and Generalised Mod Classes.

[BibT_eX]

[DOI]

N. V. Vinodchandran

Inf. Process. Lett., 1995

Logspace Verifiers, NC, and NP.

[BibT_eX]

[DOI]

Satyanarayana V. Lokam

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994

A Note on SpanP Functions.

[BibT_eX]

[DOI]

Thomas Thierauf

N. V. Vinodchandran

Inf. Process. Lett., 1994

Non-commutative Computation, Depth Reduction, and Skew Circuits (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993

Language Classes Defined by Time-Bounded Relativised Cellular Automata.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1993

1992

Some results on time-varying and relativised cellular automata.

[BibT_eX]

[DOI]

Int. J. Comput. Math., 1992

1991

Relativised Cellular Automata and Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

1990

Fuzzy L-systems.

[BibT_eX]

[DOI]

M. V. Nagendra Prasad

Int. J. Comput. Math., 1990

1989

Hexagonal Cellular Automata.

[BibT_eX]

[DOI]

Proceedings of the A Perspective in Theoretical Computer Science, 1989

Systolic Pyramid Automata, Cellular Automata and Array Languages.

[BibT_eX]

[DOI]

Proceedings of the Array Grammars, Patterns and Recognizers, 1989

Systolic Pyramid Automata, Cellular Automata and Array Languages.

[BibT_eX]

[DOI]