List of Publications

--------------------

Book Chapter

  1. S. Chakraborty, "Reasoning about Heap Manipulating Programs using Automata Techniques", in Modern Applications of Automata Theory , ed. Deepak D'Souza and Priti Shankar, World Scientific, May 2012

Edited Volumes

  1. S. Chakraborty and A. Kumar (editors), Proceedings of 31st International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Leibniz International Proceedings in Informatics (LIPIcs), Dec 2011 [LIPIcs webportal]
  2. S. Chakraborty and M. Mukund (editors), Proceedings of 10th International Symposium on Automated Technology for Verification and Analysis (ATVA 2012), Lecture Notes in Computer Science (LNCS 7561), Springer, Oct 2012 [Online version]

Journals

  1. S. Chakraborty, Z. Khasidashvili, C.-J. H. Seger, R. Gajavelly, T. Haldankar, D. Chhatani and R. Mistry, "Symbolic Trajectory Evaluation for Word-Level Verification: Theory and Practice", in Formal Methods in System Design, February 2017, pages 1-36 [PDF of preprint] (The final publication is available at Springer)

  2. A. John and S. Chakraborty, "A Layered Algorithm for Quantifier Elimination from Linear Modular Constraints", in Formal Methods in System Design, Vol 49, Issue 3, pages 272-323, December 2016 [PDF of preprint] ( The final publication is available at Springer)

  3. A. Sankaran, B. Adsul and S. Chakraborty, "A Generalization of the Łoś-Tarski Preservation Theorem", in Annals of Pure and Applied Logic, Vol 167, Issue 3, pages 189-210 March 2016 [PDF of preprint]

  4. B. Gulavani, S. Chakraborty, G. Ramalingam and A. Nori, "Bottom-up Shape Analysis using LISF", in ACM Transactions on Programming Languages and Systems, Vol. 33, Issue 5, Nov 2011 [PDF of preprint]

  5. B. Gulavani, S. Chakraborty, A. Nori and S. Rajamani, "Refining Abstract Interpretations", in Information Processing Letters, Vol 119, Issue 16, pp. 666-671, Aug 2010 [gzip'd PS of preprint]

  6. D. Thomas, S. Chakraborty and P. K. Pandya, "Efficient Guided Symbolic Reachability using Reachability Expressions", in International Journal on Software Tools for Technology Transfer, Vol. 10, No. 2, pp. 113-129, Jan 2008 [gzip'd PS of preprint]

  7. S. Chakraborty, J. Mekie and D. K. Sharma, "Reasoning about Synchronization in GALS Systems", in Formal Methods in System Design, Vol. 28, No. 2, pp. 153-169, May 2006 [gzip'd PS of preprint]

  8. S. Chakraborty, D. L. Dill and K. Y. Yun, "Efficient Algorithms for Approximate Time Separation of Events", in Sadhana: Academy Proceedings in Engineering Sciences, The Indian Academy of Sciences Vol 27 Part 2, pp. 129-162, April 2002 [gzip'd PS]

  9. K. Y. Yun, K. W. James, R. Fairlie-Cuninghame, S. Chakraborty and R. L. Cruz, "A Self-Timed Real-Time Sorting Network", in IEEE Transactions on VLSI Systems, Vol. 8, No. 3, pp. 356-363, Jun 2000 . [gzip'd PS]

  10. S. Chakraborty, K. Y. Yun and D. L. Dill, "Timing Analysis of Asynchronous Systems Using Time Separation of Events", in IEEE Transactions on CAD, Vol. 18, No. 8, pp. 1061-1076, Aug 1999 [gzip'd PS]

  11. S. Chakraborty, D. L. Dill and K. Y. Yun, "Min-max Timing Analysis and an Application to Asynchronous Circuits", in Proc. of the IEEE, Vol. 87, No. 2, pp. 332-346, Feb 1999. [gzip'd PS]

  12. S. Chakraborty, D. R. Chowdhury and P. Pal Chaudhuri, "Theory and Application of Non-Group Cellular Automata for Synthesis of Easily Testable Finite State Machines", in IEEE Transactions on Computers, Vol. 45, No. 7, pp. 769-781, Jul 1996.

  13. S. Nandi, B. Vamsi, S. Chakraborty and P. Pal Chaudhuri, "Cellular Automata as a BIST structure for testing CMOS circuits", in IEE Proceedings - Computers and Digital Techniques, Vol. 141, No. 1, pp. 41-47, Jan 1994.

Conferences and Workshops

  1. S. Akshay, S. Chakraborty, A. John and S. Shah, "Towards Parallel Boolean Functional Synthesis", to appear in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), April 2017 [PDF of extended version on arXiv.org]

  2. S. Chakraborty, A. Gupta and R. Jain, "Matching Multiplications in Bit-vector Formulas", in Proc. of International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI), pg. 131-150, Jan 2017 [PDF of extended version on arXiv.org]

  3. S. Chakraborty, K.S. Meel and M.Y. Vardi, "Improving Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Solver Calls", in Proc. of International Joint Conference on Artificial Intelligence (IJCAI), pg.3569-3576, July 2016 [PDF]

  4. K. S. Meel, M. Y. Vardi, S. Chakraborty, D. Fremont, S. Seshia, D. Fried, A. Ivrii and S. Malik, "Constrained Counting and Sampling: Universal Hashing meets SAT Solving", in Proc. of AAAI-16 Workshop on Beyond NP, Feb 2016 [PDF]

  5. S. Chakraborty, K. S. Meel, R. Mistry and M. Y. Vardi, "Approximate Probabilistic Inference via Word-level Counting", in Proc. of AAAI International Conference on Artificial Intelligence (AAAI), Feb 2016 [PDF of extended version on arXiv.org]

  6. A. John, S. Shah, S. Chakraborty, A. Trivedi and S. Akshay, "Skolem Functions for Factored Formulas", in Proc. of International Conference on Formal Methods for Computer-Aided Design (FMCAD), pg. 73-80, Sep 2015 [PDF of extended version on arXiv.org]

  7. S. Chakraborty, Z. Khasidashvili, C-H. J. Seger, R. Gajavelly, T. Haldankar, D. Chhatani and R. Mistry, "Word-level Symbolic Trajectory Evaluation", in Proc. of International Conference on Computer-Aided Verification (CAV), pg. 128-143, July 2015 [PDF of extended version on arXiv.org]

  8. S. Chakraborty, D. Fried, K. S. Meel and M. Y. Vardi, "From Weighted to Unweighted Model Counting", in Proc. of International Joint Conference on Artificial Intelligence (IJCAI), pg. 689-695, July 2015 [PDF of pre-print]

  9. S. Chakraborty, D. J. Fremont, K. S. Meel, S. A. Seshia and M. Y. Vardi, "On Parallel Scalable Uniform SAT Witness Generation", in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pp. 304-319, April 2015 [PDF of extended version]

  10. A. John and S. Chakraborty, "Quantifier Elimination for Linear Modular Constraints", in Proc. of International Congress of Mathematical Software, pp. 295-302, August 2014 [PDF of preprint]

  11. A. Sankaran, B. Adsul and S. Chakraborty, "A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures", in Proc. of International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 474-485, August 2014 [PDF of extended version on arXiv.org]

  12. S. Chakraborty, D. J. Fremont, K. S. Meel, S. A. Seshia and M. Y. Vardi, "Distribution-Aware Sampling and Weighted Model Counting for SAT", in Proc. of AAAI International Conference on Artificial Intelligence (AAAI), pp. 1722-1730, July 2014 [PDF of extended version on arXiv.org]

  13. S. Chakraborty, K. S. Meel and M. Y. Vardi, "Balancing Scalability and Uniformity in SAT Witness Generator", in Proc. of ACM/IEEE Design Automation Conference (DAC), pp. 1-6, June 2014 [PDF of extended version on arXiv.org]

  14. H. Karmarkar, M. Joglekar and S. Chakraborty, "Improved Upper and Lower Bounds for Büchi Disambiguation", in Proc. of International Conference on Automated Technology for Verification and Analysis (ATVA), pp. 40-54, Oct 2013 [PDF of pre-print]

  15. S. Chakraborty, K. S. Meel and M. Y. Vardi, "A Scalable Approximate Model Counter", in Proc. of International Conference on Principles and Practice of Constraint Programming (CP), Sept 2013 [PDF of extended version on arXiv.org]

  16. S. Jayasankar and S. Chakraborty, "Improving Approximate Reachability by Dynamic Interleaving of Projections-based Heuristics", in Proc. of IEEE Conference on Computer-Aided Control System Design (CACSD), pp. 25-30, Aug 2013 [PDF of pre-print]

  17. S. Chakraborty, K. S. Meel and M. Y. Vardi, "A Scalable and Nearly Uniform Generator of SAT Witnesses", in Proc. of International Conference on Computer-Aided Verification (CAV), pp. 608-623, July 2013 [PDF of extended version on arXiv.org]

  18. A. John and S. Chakraborty, "Extending Quantifier Elimination to Linear Inequalities on Bit-vectors", in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pp. 78-92, March 2013 [PDF of pre-print]

  19. A. Sankaran, B. Adsul, V. Madan, P. Kamath and S. Chakraborty, "Preservation under Substructures modulo Bounded Cores" in Proc. of International Workshop on Logic, Language, Information and Computation (WoLLIC), pp. 291-305, Sept 2012 [PDF of extended version on arXiv.org]

  20. A. John and S. Chakraborty, "A Quantifier Elimination Algorithm for Linear Modular Equations and Disequations", in Proc. of International Conference on Computer-Aided Verification (CAV), pp. 486-503, July 2011 [PDF of pre-print]

  21. J. Edmonds and S. Chakraborty, "Bounding Variance and Expectation of Longest Path Lengths in DAGs", in Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 766-781, January 2010 [gzip'd PS of pre-print]

  22. H. Karmarkar and S. Chakraborty, "On Minimal Odd Rankings for Büchi Complementation", in Proc. of International Symposium on Automated Technology for Verification and Analysis (ATVA), pp. 228-243, October 2009 [gzip'd PS]

  23. B. Gulavani, S. Chakraborty, G. Ramalingam and A. Nori, "Bottom-up Shape Analysis", in Proc. of International Static Analysis Symposium (SAS), pp. 181-204, August 2009 [gzip'd PS]

  24. B. Gulavani, S. Chakraborty, A. Nori and S. Rajamani, "Automatically Refining Abstract Interpretations", in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pp. 443-458, March 2008 [gzip'd PS] [gzip'd PS of Tech Report]

  25. S. Sunkari, S. Chakraborty, V. Vedula and K. Maneparambil, "A Scalable Symbolic Simulator for Verilog RTL", in Proc. of IEEE International Workshop on Microprocessor Testing and Verification, December 2007 [gzip'd PS]

  26. S. Juvekar, A. Taly, V. Kanade and S. Chakraborty, "Approximate Symbolic Reachability of Networks of Transition Systems", invited paper in Proc. of GM R&D Workshop on Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems, pp. 117-136, January 2007 [gzip'd PS]

  27. D. Thomas, S. Chakraborty and P. K. Pandya, "Efficient Guided Symbolic Reachability using Reachability Expressions", in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pp. 120-134, March 2006 [gzip'd PS]

  28. J. Mekie, S. Chakraborty, G. Venkataramani, P. S. Thiagarajan and D. K. Sharma, "Interface Design for Rationally Clocked GALS Systems", in Proc. of IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), pp. 160-171, March 2006 [gzip'd PS]

  29. B. Sharma, P. K. Pandya and S. Chakraborty, "Bounded Validity Checking of Interval Duration Logic", in Proc. of International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pp. 301-316, April 2005 [gzip'd PS]

  30. J. Mekie, S. Chakraborty and D. K. Sharma, "Evaluation of Pausible Clocking Scheme for Interfacing High Speed IP Cores in GALS Framework" in Proc. of IEEE International Conference on VLSI Design, pp. 559-564, Jan 2004 [gzip'd PS]

  31. G. T, Hazari, M. P. Desai, A. Gupta and S. Chakraborty, "A Novel Technique Towards Eliminating the Global Clock in VLSI Circuits", in Proc. of IEEE International Conference on VLSI Design, pp. 565-570, Jan 2004 [gzip'd PS]

  32. S. Chakraborty, J. Mekie and D. K. Sharma, "Reasoning about Synchronization Issues in GALS Systems: A Unified Approach", invited paper in Proc. of Workshop on Formal Methods in GALS Architectures (FMGALS), Formal Methods Europe Symposium, Sept 2003 [gzip'd PS]

  33. S. Chakraborty and R. Angrish, "Probabilistic Timing Analysis of Asynchronous Systems with Moments of Delays", in Proc. of IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), pp. 99-108, April 2002 [gzip'd PS]

  34. S. Chakraborty and R. Murgai, "Layout-driven Timing Optimization by Generalized DeMorgan Transform", in Proc. of Joint IEEE Asia-South Pacific Design Automation Conference/IEEE VLSI Design Conference (ASP-DAC/VLSI), pp. 647-654, Jan 2002 [gzip'd PS]
    (preliminary version also in Proc. of International Workshop on Logic Synthesis, June 2001)

  35. R. Carragher, R. Murgai, S. Chakraborty, T. Shibuya, Y. Kanazawa, M. R. Prasad, A. Srivastava, N. Vemuri and H. Yoshida, "Layout-driven Logic Optimization", in Designer's Forum Proc. of the Design Automation and Test in Europe (DATE) Conference, Mar 2001 [gzip'd PS]
    (preliminary version also in Proc. of International Workshop on Logic Synthesis, May 2000)

  36. S. Chakraborty and R. Murgai, "Complexity of Minimum-delay Gate Resizing", in Proc. of IEEE International Conference on VLSI Design, pp. 425-430, Jan 2001 [gzip'd PS]

  37. K. Y. Yun, S. Chakraborty, K. W. James, R. Fairlie-Cuninghame and R. L. Cruz, "A Self-Timed Real-Time Sorting Network", in Proc. of IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp. 427-434, Oct 1998.   (Best Paper in Algorithms and Architecture track). [gzip'd PS]

  38. S. Chakraborty, K. Y. Yun and D. L. Dill, "Practical Timing Analysis of Asynchronous Circuits using Time Separation of Events"   in Proc. of IEEE Custom Integrated Circuits Conference, pp. 455-458, May 1998. [gzip'd PS]
    (extended version also in Proc.of 5th ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (TAU), pp. 209-217, Dec 1997.)

  39. S. Chakraborty, P. A. Subrahmanyam and D. L. Dill, "Approximate Time Separation of Events in Practice", in Proc. of 5th ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (TAU), pp. 77-82, Dec 1997. [gzip'd PS]

  40. S. Chakraborty and D. L. Dill, "Approximate Algorithms for Time Separation of Events", in Proc. of IEEE/ACM International Conference on CAD, pp. 190-194, Nov 1997. [gzip'd PS]

  41. S. Chakraborty and D. L. Dill, "More Accurate Polynomial-Time Min-Max Timing Simulation", in Proc. of 3rd IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), pp. 112-123, Apr 1997. [gzip'd PS]

  42. S. Chakraborty, D. L. Dill, K. Y. Yun and K. Y. Chang, "Timing Analysis for Extended Burst-Mode Circuits", in Proc. of 3rd IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), pp. 101-111, Apr 1997. [gzip'd PS]

  43. D. R. Chowdhury, S. Chakraborty, B. Vamsi and P. Pal Chaudhuri, "Cellular Automata Based Synthesis of Easily and Fully Testable FSMs", in Proc. of IEEE/ACM International Conference on CAD, pp. 650-653, Nov 1993.

  44. S. Nandi, B. Vamsi, S. Chakraborty, P. Pal Chaudhuri and S. Roy, "Delay Fault Test Generation with Cellular Automata", in Proc. of 6th IEEE International Conference on VLSI Design, pp. 281-286, Jan 1993.

  45. D. R. Chowdhury, S. Chakraborty and P. Pal Chaudhuri, "Synthesis of Self-Checking Sequential Machines using Cellular Automata" (poster paper), in Proc. of 6th IEEE International Conference on VLSI Design, pp. 107-107, Jan 1993.

Ph.D. dissertation