14.2k citations
- Pennsylvania State UniversityUS156 papers
- Tata Institute of Fundamental ResearchIN156 papers
- Cardiff UniversityGB146 papers
- Centre National de la Recherche ScientifiqueFR144 papers
- Max Planck Institute for Gravitational PhysicsDE143 papers
- California Institute of TechnologyUS136 papers
- Inter-University Centre for Astronomy and AstrophysicsIN134 papers
- Leibniz University HannoverDE133 papers
- Montclair State UniversityUS133 papers
- University of BirminghamGB133 papers
- University of MississippiUS133 papers
- University of FloridaUS131 papers
23 papers · 1 filter
A Lower Bound on Conservative Elementary Object Systems Coverability
Francesco Di Cosmo, Soumodev Mal, Tephilla Prince
Elementary Object Systems (EOS) are a form of Petri Net (PN) where tokens carry internal PN. This model has been recently proposed for analysis of robustness of Multi Agent Systems…
Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth- reduction result by Agrawal and Vinay (FOCS 2008) has made PIT for depth- circuits…
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree
Suryajith Chillara
Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers and such that , any syntactic depth four circuit of bounded…
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit…
Verification of Flat FIFO Systems
Alain Finkel, M. Praveen
The decidability and complexity of reachability problems and model-checking for flat counter machines have been explored in detail. However, only few results are known for flat (lo…
Efficient Black-Box Identity Testing over Free Group Algebra
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised…