5 papers
Sublinear-Space Approximation Algorithms for Max r-SAT
Arindam Biswas, Venkatesh Raman
In the Max -SAT problem, the input is a CNF formula with variables where each clause is a disjunction of at most literals. The objective is to compute an assignment whic…
On non-surjective word maps on
Arindam Biswas, Jyoti Prakash Saha
Jambor--Liebeck--O'Brien showed that there exist non-proper-power word maps which are not surjective on for infinitely many . This provided th…
Approximation in (Poly-) Logarithmic Space
Arindam Biswas, Venkatesh Raman, Saket Saurabh
We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d-Hitt…
Summarizing User-generated Textual Content: Motivation and Methods for Fairness in Algorithmic Summaries
Abhisek Dash, Anurag Shandilya, Arindam Biswas +3
As the amount of user-generated textual content grows rapidly, text summarization algorithms are increasingly being used to provide users a quick overview of the information conten…
A Simple Condition for the Existence of Transversals
Arindam Biswas
Hall's Theorem is a basic result in Combinatorics which states that the obvious necesssary condition for a finite family of sets to have a transversal is also sufficient. We presen…