Meena Mahajan

Sasank Mouli

Proceedings of the 27th International Conference on Theory and Applications of Satisfiability Testing, 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

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

Linear threshold functions in decision lists, decision trees, and depth-2 circuits.

[BibT_eX]

[DOI]

K. Vignesh

Electron. Colloquium Comput. Complex., 2023

Query Complexity of Search Problems.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Dependency Schemes in CDCL-Based QBF Solving: A Proof-Theoretic Study.

[BibT_eX]

[DOI]

Abhimanyu Choudhury

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

QBF Merge Resolution Is Powerful but Unnatural.

[BibT_eX]

[DOI]

Gaurav Sood

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 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

On (Simple) Decision Tree Rank.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

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

MaxSAT Resolution and Subcube Sums.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

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

[BibT_eX]

[DOI]

Joshua Blinkhorn

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Hard QBFs for Merge Resolution.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Lower Bounds for Linear Decision Lists.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Nikhil S. Mande

Electron. Colloquium Comput. Complex., 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

Building Strategies into QBF Proofs.

[BibT_eX]

[DOI]

Joshua Blinkhorn

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Short Proofs in QBF Expansion.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 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

Lower Bound Techniques for QBF Proof Systems.

[BibT_eX]

[DOI]

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

2017

A Quest for Structure in Complexity.

[BibT_eX]

[DOI]

Vikraman Arvind

Bull. EATCS, 2017

Computing the Maximum using (min, +) Formulas.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 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

Relating two width measures for resolution proofs.

[BibT_eX]

[DOI]

Anil Shukla

Electron. Colloquium Comput. Complex., 2016

Are Short Proofs Narrow? QBF Resolution is not Simple.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Understanding Cutting Planes for QBFs.

[BibT_eX]

[DOI]

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Sums of Read-Once Formulas: How Many Summands Suffice?

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

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

The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Feasible Interpolation for QBF Resolution Calculi.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 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

Homomorphism Polynomials Complete for VP.

[BibT_eX]

[DOI]

Arnaud Durand

Guillaume Malod

Nicolas de Rugy-Altherre

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Building above Read-once Polynomials: Identity Testing and Hardness of Representation.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 20th International Conference, 2014

2013

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

[BibT_eX]

[DOI]

Eric Allender

Vikraman Arvind

Theory Comput. Syst., 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

Small Depth Proof Systems.

[BibT_eX]

[DOI]

Gido Scharfenberger-Fabian

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

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

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

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Longest Paths in Planar DAGs in Unambiguous Log-Space.

[BibT_eX]

[DOI]

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

Counting Classes and the Fine Structure between NC1 and L.

[BibT_eX]

[DOI]

Samir Datta

Michael Thomas

Heribert Vollmer

Proceedings of the Mathematical Foundations of Computer Science 2010, 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

Counting Paths in VPA Is Complete for #NC1.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

2009

Parameterizing above or below guaranteed values.

[BibT_eX]

[DOI]

Somnath Sikdar

J. Comput. Syst. Sci., 2009

Upper Bounds for Monotone Planar Circuit Value and Variants.

[BibT_eX]

[DOI]

Comput. Complex., 2009

The Planar k-Means Problem is NP-Hard.

[BibT_eX]

[DOI]

Kasturi R. Varadarajan

Proceedings of the WALCOM: Algorithms and Computation, Third International Workshop, 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

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

[BibT_eX]

[DOI]

Raghav Kulkarni

Kasturi R. Varadarajan

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

Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

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

[BibT_eX]

[DOI]

Antoine Meyer

Proceedings of the Computer Science, 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

On the Complexity of Matrix Rank and Rigidity.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

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

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 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]

Proceedings of the STACS 2006, 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 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

Arithmetic Complexity, Kleene Closure, and Formal Power Series.

[BibT_eX]

[DOI]

Eric Allender

Vikraman Arvind

Theory Comput. Syst., 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

The Complexity of Planarity Testing.

[BibT_eX]

[DOI]

Eric Allender

Proceedings of the STACS 2000, 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

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

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

Determinant: Combinatorics, Algorithms, and Complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Parametrizing Above Guaranteed Values: MaxSat and MaxCut

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

A Combinatorial Algorithm for the Determinant.

[BibT_eX]

[DOI]

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

1995

A Note on Mod and Generalised Mod Classes.

[BibT_eX]

[DOI]

N. V. Vinodchandran

Inf. Process. Lett., 1995

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Nondeterministic, Probabilistic and Alternating Computations on Cellular Array Models.

[BibT_eX]

Proceedings of the Developments in Language Theory, 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]