Types of Research Tasks

• (T1) Improving an existing algorithm

  A specific algorithm (e.g., Dijkstra’s shortest path, PageRank, or SGD for optimization) is important and widely used. The research goal is to improve its performance (speed, accuracy, scalability, robustness, memory efficiency, etc.).

  • Example: Speeding up the Fast Fourier Transform for large-scale data.
  • Example: Making gradient descent methods more stable in non-convex optimization.

• (T2) Designing a solution for a problem

  Given a well-defined problem (e.g., detecting communities in networks, scheduling tasks, learning embeddings), we want to find or design an algorithm to solve it.

  • Example: Creating an algorithm for efficient graph coloring.
  • Example: Designing a robust algorithm for image denoising.

Common Procedure for Both Tasks

Regardless of whether you are working on (T1) or (T2), the following fundamental procedure should guide your research:

1. Formulate the design/decision space
   • Define the problem clearly (formal mathematical statement if possible).
   • Identify the canonical framework or standard algorithmic approaches used for it.
   • Ask: What assumptions are typically made? What input/output structures are expected?
2. Identify the aspects for improvement (literature review & gap analysis)
   • For T1: Identify where the current algorithm struggles. Is it too slow for large inputs? Does it fail under noise? Is it hard to parallelize?
   • For T2: Identify why existing solutions are unsatisfactory. Do they rely on unrealistic assumptions? Do they scale poorly? Do they fail in edge cases?
3. Formulate clear research questions
   • What specific property are you trying to improve (time, memory, robustness, accuracy)?
   • What are the trade-offs you’re willing to accept?

General Research Approaches

Algorithmic research can be pursued through two complementary lenses:

• Top-down approach (empirically driven, idea first → justification later)
• Bottom-up approach (theory driven, framework first → algorithm later)

Top-down Approach (common in many recent papers)

1. Generate working ideas
   • Use intuition, heuristics, or inspiration from related problems.
   • Don’t worry too much about theory at the beginning—just find something that seems to work.
2. Test quickly via experiments
   • Run small-scale experiments to validate feasibility.
   • Benchmark against standard datasets or synthetic test cases.
3. Refine and strengthen the idea
   • Analyze failures and edge cases.
   • Improve based on observed patterns.
4. Back up with theory (if possible)
   • Develop proofs, bounds, or formal justification once you have empirical evidence.
   • Even partial theoretical insights (e.g., under certain assumptions) make the result more convincing.