Looking for PhD/MTech(thesis) students
Looking for students to work on research problems in the following areas. Read this
before contacting me.
- Quantum computing: designing new algorithms, proving lower bounds on communication & complexity of solving problems, comparing classical and
- Complexity theory: investigating problems and complexity classes in P and below, especially circuit classes
- Network/Graph algorithms: engineering algorithmic techniques for handling large and/or real-life graphs
What am I up to recently?
- Jan 2021: Teaching CSE322:(Theory of Computing)
- Aug 2020: Teaching CSE525:(Graduate Algorithms)
- Jan 2020: Teaching CSE622:(Introduction to Quantum Computing) and CSE322:Theory of Computing
- Aug 2019: Guiding Tharrma Shastha (Ph.D.) on quantum algorithms for Boolean functions.
- Aug 2019: Guiding Sagnik Chatterjee (Ph.D.) on quantum optimization techniques.
- Aug 2019: Teaching CSE525:(Graduate Algorithms)
- July 2019: Akshita Sawhney defended her MTech(CB) thesis on stage classification of renal cell carcinoma
- Apr 2019: Anuj Saxena defended his PhD thesis on "Enforcing Privacy for Location Based
- Jan 2019: Teaching CSE322:Theory of Computing
- Aug 2018: Teaching CSE525:(Graduate Algorithms) and CSE621:(Complexity Theory)
- Jan 2018: Teaching CSE622:(Introduction to Quantum Computing) and CSE322:Theory of Computing
- Aug 2017: Advising Shanu for MTech thesis on quantum amplitude amplification, Parth for BTP on applications of ear decomposition on path-based graph problems,
Gautam for BTP on enumeration of clique and related structures, Ankit for MTech thesis on classification of biological networks and Biswadeep for MTech thesis on
biclustering of food data.
- Aug 2017: Teaching CSE525:(Graduate Algorithms)
- Jan 2017: Teaching CSE622:(Introduction to Quantum Computing) and CSE322:Theory of Computing
- Aug 2016: Advising G. Venkatesh for MTech thesis on LSH for data mining problems
- Aug 2016: Teaching CSE525:(Graduate Algorithms)
- Jan 2016: Teaching CSE523:(Randomized Algorithms) and CSE322:Theory of Computing
- Aug 2015: Advising Amitesh Pandey for MTech thesis on universal turing machine simulator
- Aug 2015: Advising Shubham Srivastava for MTech thesis on utility vs privacy gurantees of differential privacy
- Aug 2015: Teaching CSE525 (Graduate
- Jan 2015: Teaching CSE622 (Quantum
- Jan 2015: Teaching CSE421/621 (Computational
- Aug 2014: Teaching CSE525 (Graduate
- May 2014: Advising Siddharth Dawar for PhD thesis on frequent itemset mining
- May 2014: Advising Khalique Newaz for MTech thesis on network analysis of prion disease
- Jan 2014: Teaching CSE523 (Probability in Computing)
- Aug 2013: Teaching CSE525 (Graduate Algorithms) and
another 2-credit course CSE526 (P vs NP)
- Jan 2013: Teaching (jointly with Rajiv Raman) CSE222 (Analysis and
Design of Algorithms)
- Aug 2012: Guiding Monalisa Jena (Ph.D.) on Rank Similarity
- Aug 2012: Teaching CSE320/520 (Advanced Algorithms) in Monsoon 2012
- Aug 2012: Guiding Akash Vanjani (B.Tech.) on Classroom
- Jan 2012: Teaching CSE523 (Probability in Computing) and
CSE524 (Theory of Modern Cryptography, co-instruct with Somitra
- Jan 2012: Guiding Pranav Raj (B.Tech.) on Combinatorial
- Dec 2011: Attending ICISS 2011 (Kolkata)
- Aug 2011: Video lecture at IIT-Delhi as part of MHRD
project on Introduction to Quantum Computing
- Jul 2011: Guiding Anuj Saxena (Ph.D.) on Location-Privacy in
Location Based Services
Some software projects I was involved with
FOSS Involvement:I started using GNU/Linux at IIT in 2000 (for the sake of brevity
I will write Linux to mean GNU/Linux).
Redhat Linux (now Fedora Core) was used at our computer center
but soon I moved to Mandrake Linux (now Mandriva Linux). The love thus started
is not over yet. I am still using Mandriva Linux.
Like many other FOSS believers, I was highly motivated by Eric S. Raymond's Cathedral
and the Bazaar when I read it in 2001. I wrote my first FOSS software and released
it under an open source licensed soon after.
Over the years, the developer's itch bothered me several times. This resulted
in several new softwares that I wrote. Some of these are not relevant anymore; but in their
days some of them were even included in some Linux distributions.
Since 2005 I am involved with the Beagle project, the first desktop search service for Linux.
Since 2006 December, I lead the development of the project and I am also one of the maintainers
of the Beagle project. I also wrote several softwares
related to Beagle and released them under open source licenses.
Other than the projects mentioned above, I have also contributed to numerous other open source
projects, including bug-fixes and new features.
I was a mentor for the Beagle project for Google Summer of Code in 2007.
My Research Interests
quantum computing, randomized algorithms, computational complexity
algorithms design and engineering in computational biology, networking & data-mining
Google scholar profile
Reports and Publications
- S. Chatterjee, D. Bera. Applying the Quantum Alternating Operator Ansatz to the Graph Matching problem accepted in AQIS 2020 (video, pre-print)
- B.L.K. Jolly, L. Jain, D. Bera, T. Chakraborty. Unsupervised Anomaly Detection in Journal-Level Citation Networks accepted in JCDL 2020
- D. Bera. Maximal Labeled-Cliques for Structural-Functional Communities accepted in Complex Networks 2020 (pre-print)
- A. Sharma, G. Bagler, D. Bera. Supervised learning of protein thermal stability using sequence mining and distribution statistics of network
- R. Pratap, D. Bera, K. Revanuru. Efficient Sketching Algorithm for Sparse Binary Data accepted in ICDM 2019 (draft)
- D. Bera, Tharrmashastha P.V. Error reduction of Quantum Algorithms accepted in Physical
Review A (pre-print)
- D. Bera, S. Maitra, D. Roy, P. Stǎnicǎ. Testing Nonlinearity: Limitation of the BLR Testing and Further Results (Extended Abstract) accepted in The
Eleventh International Workshop on Coding and Cryptography (WCC2019)
- D.Bera, S. Maitra, SAPV Tharrmashastha. Efficient Quantum Algorithms related to Autocorrelation Spectrum accepted in Indocrypt 2019 (pre-print, presentation)
- D. Bera. Detection and diagnosis of single faults in quantum circuits in IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems (TCAD), 37(3), 587‐600, 2017 (preprint version)
- S. Dawar, V. Goyal, D. Bera. A hybrid framework for mining high-utility itemsets in a sparse transaction database in Applied Intelligence 10(3):809-827, 2017
- M. Chaitanya, Debarshi Dutta, K. Kothapalli, D. Bera. Applications of Graph Ear Decomposition to Efficient Heterogeneous Shortest Path/Cycle
Problems in 19th Workshop on Advances in Parallel and Distributed Computational Models, 2017 IPDPS
- C. Pachorkar, M. Chaitanya, K. Kothapalli, D. Bera. Efficient Parallel Ear Decomposition of Graphs with Application to Betweenness-Centrality in HiPC 2016 (best paper award) (pre-print)
- J. Leeka, S. Bedathur, D. Bera, M. Atre. Quark-X: An Efficient Top-K Processing Framework for RDF Quad Stores in CIKM 2016
- D. Bera. Two-sided Quantum Amplitude Amplification and Exact-Error Algorithms in arXiv:1605.01828 [cs.CC] (pre-print)
- Preliminary version in D. Bera. Applications of Quantum Amplitude Amplification in ECCC Tech Report TR14-151 (revised April 2016)
- D.Bera, R. Pratap. Frequent-Itemset Mining using Locality-Sensitive Hashing in Proceedings of COCOON 2016 (preprint)
- A. Saxena, V. Goyal, D. Bera. Mintra: Mining anonymized trajectories with annotations in Proceedings of IDEAS 2016
- A. Saxena, V. Goyal, D. Bera. Efficient Enforcement of Privacy for Moving Object Trajectories in Proceedings of ICISS 2013
- A. Saxena, M. Pundir, V. Goyal, D. Bera. Preserving Location Privacy for Continuous Queries on Known Route in Proceedings of ICISS 2011
- F. Esposito, I. Matta, D. Bera, P. Michiardi. On the impact of seed scheduling in peer-to-peer networks in Computer
Networks 55(15), 3303-3317, 2011
- D. Bera. A lower bound method for quantum circuits Information Processing Letters, 111(15),
- D. Bera. Quantum Circuits: Power and Limitations Ph.D. Dissertation, 2009
- D. Bera, S. Homer. On Finding Sensitivity of Quantum and Classical Gates BUCS Tech Report 2009-019, 2009
- D.Bera, S. Fenner, F. Green, S. Homer. Efficient universal quantum circuits in Quantum Information and Computation, 10(1&2), 0016-0027, 2010
- D.Bera, F. Green, S. Homer. Small depth quantum circuits ACM SIGACT News article, 38(2), June 2007
My Erdos number is 4.
What have I been teaching?
I feel comfortable teaching theoretical Computer Science courses,
both undergraduate and advanced. The advanced courses stress on
formalism and rigorous analysis, whereas, the introductory courses on
breadth and competence in tools and techniques.
Assistant Professor at IIIT-Delhi (since Jan, 2010)
Many of these courses were also designed by me.
- CSE222 - Analysis and Design of Algorithms (Undergraduate
Taught in Winter 2010, Winter 2011, Winter
- CSE320/CSE520 - Advanced Algorithms
Taught in Monsoon
2010, Monsoon 2012.
- CSE322 - Theory of Computation
- CSE523 - Randomized Algorithm
- CSE524 - Theory of Modern Cryptography
Taught in Winter
- CSE525 - Graduate Algorithms
- CSE526A - P vs NP (2 credit)
Taught in Monsoon
- CSE421/621 - Computational Complexity Theory
In Winter 2015,
- CSE622 - Quantum Computing
- (co-taught) Algorithms in Computational Biology. Taught in Monsoon 2015.
Teaching Fellow at Boston University (2003 to 2009)
I formally got involved in teaching as Teaching Fellow for various
courses at Boston University since 2003. I enjoy teaching both
introductory and and advanced courses. Introductory classes require a
lot of patience and I enjoy the challenge of explaining completely new
concepts to students. On the other hand in the advanced classes I am
mostly acting as a tutor helping the students who get stuck. Students
and professors like me alike for my services. I was awarded The Best TF
award in the Computer Science department in 2007 by the College of Arts
and Science (CAS), Boston University. Following are some of the courses
which I oversaw as TF (many of them multiple times).
- CS111 - Introduction to Computing, both C++ and Java
- CS112 - Data Structures
- CS113 - Combinatoric Structures (Introductory Discrete
- CS235 - Algebraic Algorithms
- CS237 - Probability in Computing
- CS330 - Introduction to Analysis of Algorithms (Undergraduate
Where have I worked?
GMD-IPSI: I was a summer intern during the summer of 2001 at GMD-IPSI (later merged with Fraunhofer IPSI) in Darmstadt, Germany. There I worked for the OASYS group on the project Teachware on Demand.
Teachware on Demand tries to solve the courseware management problem where
courses are taken by students, written by authors and tagged by editors. The system allows each
group to work independently and allows efficient tagging to create courses from smaller concepts.
I was responsible for developing the intermediate web architecture using SOAP. I also did some theoretical work on integrating LOM
(Learning Object Metadata) and MPEG7 to allow tagging of courses in video formats.
Adobe Systems India Pvt. Ltd.: I worked for 5 months in 2002 after graduation from IIT Kanpur at Adobe's India R&D center in Noida, India.
I was responsible for reverse engineering and parsing Microsoft office file formats to be read by Adobe applications. I really liked the work there; also, we moved to a new building when I was there which was very nice.
VMWare, Inc.: I was a summer intern during the summer of 2006 at VMWare's R&D center at Palo Alto, USA. I designed the API and implemented the required infrastructure to allow (python and other) scripts to be submitted, managed and run on virtual machines using Virtual Center. It was a wonderful experience to work at a company which was growing extremely rapidly at that time.
Roads and bends taken so far ...
- 1980: Incubated in Kolkata
- (1983-1984) Pre-nursery in Springdal School, Rourkela
- (1984-1986) Pre-nursery in Olympus K.G. School, Paikpara, Kolkata
- (1986-1990) St. Mary's Orphanage and Day School, Dumdum,
- (1990-1996) Ramakrishna Mission Vidyalaya, Narendrapur,
- (1996-1998) Ramakrishna Mission Residential College,
- (1998-2002) B.Tech. at IIT-Kanpur
- (2002) Software developer at Adobe India Private Ltd.
- (2003-2009) Ph.D. at Boston University
- (2010-) Assistant Professor at IIIT-Delhi
For projects and thesis advisor
Possible domains (not exhaustive): Complexity theory, Algorithms,
Formal solutions for security and privacy, Quantum computing, Algorithms
for computer networks, Algorithms for data engineering.
If you want to do a project or thesis with me, I would require a
minimum of one of these skills:
- Good grades in these courses: programming, discrete
mathematics, data structures, algorithms
- For implementation work: good hold in your choice of
programming language, knowledge of standard libraries and expert
in finding and using multiple APIs, fully comfortable with new
tools and technologies
- For theoretical work: strength in mathematics, especially
algebra, probability and combinatorics, good grades in courses
like advanced (or any other elective) algorithms, theory of
computing, or other theoretical courses, ability to formulate a
problem in a formal manner, and ability to write a formal proof
- Students with Mathematics background, with some exposure
to theoretical computer science, are strongly desired
UG-PG thesis students
- Sudatta Bhattacharya: Upper and Lower bounds of various Centrality Measures on Planar and Sparse Graphs (2020)
- Akshita Sawhney: Stage classification of clear cell renal cancer based on gene expressions (2019)
- Shanu: Quantum algorithms for unitary operator identification (2018)
- Biswadeep Khan (co-guide G. Bagler):
Application of pattern mining on data of
flavor molecules, their percepts and molecular features (2018)
- Ankit Sharma (co-guide G. Bagler): Protein Classification on the basis of thermal stability using Supervised Learning (2018)
- G. Venkatesh: Design and Analysis of LSH Based Techniques for Inner Product (2017)
- Amitesh Pandey (capstone project): Universal Turing Machine Simulator (2016)
- Shubham Srivastava: Utility And Privacy Guarantees of Differential Privacy (2016)
- Khalique Newaz (co-guide K. Sriram): Network analysis of prion disease (2015)
- Siddharth Dawar (co-guide Vikram Goyal): Privacy Preserving Reverse Spatial and Textual Nearest Neighbour Query (2014)
- Pankaj Sahu (co-guide Vikram Goyal): Finding Top-k Influential Set in Directed Graphs (2014)
B.Tech. Project (BTP)
- Gautam Gupta (2018)
- Parth Mittal (2018)
- Alakh Dhruv Chopra (2017)
- Kshitij Jain & Sahil Mahajan (2015)
- Ishan Goel (2014)
- Divyanshu Bansal (2014)
- Akash Vanjani (2013)
- Pranav Raj (2013)
- SAPV Tharrmashastha: Quantum Algorithm for Computation of Auto-Correlation Spectrum of Boolean Functions (2018) for 5-year integrated MSc, Integrated
Science Education and Research Center, Visva Bharati
- Rohit Beriwal: Analysis of Quantum Circuit with Faulty Gates (2019) for B.E. (hons) thesis, C.S engineering at BITS-Pilani, Dubai
|(*) indicates current student|
Need a letter of recommendation?
I will only write a letter if you have worked with me for
at least two semester, where work means
- a course (including independent study) with A- or a better grade
- a successfully completed project (regular or internship)
- a properly done TA-ship
- some research, or other significant academic activity
Looking for internship or project under my guidance?
Contact me only if you want to solve challenging problems with provable theoretical bounds. The problem can be entirely theoretical or involve some implementation, but you must be prepared to approach the problem in a more structured and formal way. If you wish to work according to these terms, send me an email with a 2-3 paragraph writeup on the problem which excites you, including (a) why it is challenging (b) some initial idea that you have thought.