Barna Saha

According to our database1, Barna Saha authored at least 65 papers between 2006 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
CoRR, 2020

Efficient and Effective ER with Progressive Blocking.
CoRR, 2020

Fair Correlation Clustering.
CoRR, 2020

Does preprocessing help in fast sequence comparisons?
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.
SIAM J. Comput., 2019

Min-Max Correlation Clustering via MultiCut.
CoRR, 2019

Dynamic set cover: improved algorithms and lower bounds.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Crowd-Sourced Entity Resolution with Control Queries.
Proceedings of the 27th Italian Symposium on Advanced Database Systems, 2019

Paper Matching with Local Fairness Constraints.
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Min-Max Correlation Clustering via MultiCut.
Proceedings of the Integer Programming and Combinatorial Optimization, 2019

Sublinear Algorithms for Gap Edit Distance.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Connectivity of Random Annulus Graphs and the Geometric Block Model.
Proceedings of the Approximation, 2019

2018
Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.
ACM Trans. Algorithms, 2018

A new approximation technique for resource-allocation problems.
Random Struct. Algorithms, 2018

Robust Entity Resolution Using a CrowdOracle.
IEEE Data Eng. Bull., 2018

Fully Dynamic Set Cover - Improved and Simple.
CoRR, 2018

Robust Entity Resolution using Random Graphs.
Proceedings of the 2018 International Conference on Management of Data, 2018

The Geometric Block Model and Applications.
Proceedings of the 56th Annual Allerton Conference on Communication, 2018

The Geometric Block Model.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017
Clustering with Noisy Queries.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Query Complexity of Clustering with Side Information.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
A Constant Factor Approximation Algorithm for Fault-Tolerant <i>k</i>-Median.
ACM Trans. Algorithms, 2016

Online Entity Resolution Using an Oracle.
Proc. VLDB Endow., 2016

Clustering Via Crowdsourcing.
CoRR, 2016

New Approximation Results for Resource Replication Problems.
Algorithmica, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Clustering with an oracle.
Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015
TreeScope: Finding Structural Anomalies In Semi-Structured Data.
Proc. VLDB Endow., 2015

Facility Location with Matroid or Knapsack Constraints.
Math. Oper. Res., 2015

Size-Constrained Weighted Set Cover.
Proceedings of the 31st IEEE International Conference on Data Engineering, 2015

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Discovering Conservation Rules.
IEEE Trans. Knowl. Data Eng., 2014

Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems.
CoRR, 2014

Distributed data placement to minimize communication costs via graph partitioning.
Proceedings of the Conference on Scientific and Statistical Database Management, 2014

Hierarchical graph partitioning.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Data quality: The other face of Big Data.
Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, 2014

The Dyck Language Edit Distance Problem in Near-Linear Time.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
On Repairing Structural Problems In Semi-structured Data.
Proc. VLDB Endow., 2013

Efficiently Computing Edit Distance to Dyck Language.
CoRR, 2013

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median.
CoRR, 2013

Distributed Data Placement via Graph Partitioning.
CoRR, 2013

On Chebyshev radius of a set in Hamming space and the closest string problem.
Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013

Renting a Cloud.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Firewall placement in cloud data centers.
Proceedings of the ACM Symposium on Cloud Computing, SOCC '13, 2013

2012
Less is More: Selecting Sources Wisely for Integration.
Proc. VLDB Endow., 2012

Set Cover Revisited: Hypergraph Cover with Hard Capacities.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Approximation Algorithms for Resource Allocation.
PhD thesis, 2011

New Constructive Aspects of the Lovász Local Lemma.
J. ACM, 2011

The Matroid Median Problem.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Link Prediction for Annotation Graphs Using Graph Summarization.
Proceedings of the Semantic Web - ISWC 2011, 2011

AdCell: Ad Allocation in Cellular Networks.
Proceedings of the Algorithms - ESA 2011, 2011

On Capacitated Set Cover Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs.
Proceedings of the Research in Computational Molecular Biology, 2010

Schema covering: a step towards enabling reuse in information integration.
Proceedings of the 26th International Conference on Data Engineering, 2010

Energy Efficient Scheduling via Partial Shutdown.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

2009
A Unified Approach to Ranking in Probabilistic Databases.
Proc. VLDB Endow., 2009

On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch.
Proceedings of the SIAM International Conference on Data Mining, 2009

On Finding Dense Subgraphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008
Simplifying Information Integration: Object-Based Flow-of-Mappings Framework for Integration.
Proceedings of the Business Intelligence for the Real-Time Enterprise, 2008

2006
On Estimating Path Aggregates over Streaming Graphs.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree.
Proceedings of the Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), 2006


  Loading...