Yiqun Xie

Assistant Professor
Geospatial Information Science
University of Maryland, College Park

Ph.D in Computer Science
University of Minnesota, Twin Cities


Useful Resources (under construction)

This page is currently under construction and links have not been added to bullets.

Proofs on NP-hardness and beyond: theories and concrete examples
It could be much easier to prove NP-hardness than APX-hardness and NPO-completeness. For spatial problems, it may be very helpful to prove the hardness using a simplified version (try multiple of them) of a real problem as a first step.
  • P vs NP: A Millennium Problem
  • Karp's 21 Problems
  • Frequently used hardness classes: Definitions (e.g., NP-hard, APX-hard, NPO-complete)
  • Hardness: Deterministic and non-deterministic Turing machines
  • Hardness of approximation: PCP Theorem
  • Examples:
    • Proof of NPO-completeness:
    • Proof of APX-hardness:
    • Proof of NP-completeness:
  • Pseudopolynomial: Strong NP-hard vs. weak NP-hard
  • Approximation: Polynomial-Time Approximation Scheme (PTAS) and Fully Polynomial-Time Approximation Scheme (F-PTAS)
  • Common misconceptions
    • Direction of reduction/proof
    • Parameters: Fixed value / bounded values vs. flexible values
  • Classic Problems:
  • Recent Problems:
  • Mapping 3-Satisfiability (3-SAT) problem to two-dimensional spatial problems
Deep learning: Convolutional Neural Network (CNN) and its variations
  • Convoluational Neural Network for theme classification:
  • r-CNN framework for object detection:
  • You-Only-Look-Once (YOLO) and YOLOv2 frameworks for object detection:
  • Libraries: tensorflow, keras, darknet ...
  • Open-source repositories on Github: Implemented with tensorflow - ; Darknet - ;
  • Visualizing kernels of deep networks:
  • Deconvolutional neural networks:
  • Adverserial learning:
  • Will it converge?
  • Limitations of deep networks: interpretability, success and failure modes, robustness against pixel manipulation...
Deep learning for time series related problems
  • Recurrent Neural Networks (RNN)
  • Gated RNNs, e.g., Long Short-Term Memory (LSTM)
  • Problem formulations and reformulations
  • Dual problems
  • Linear programming
  • Convex optimization
  • Convergence
  • Gradient descent
    • Descent direction
    • Step size
    • Optimal first-order approaches
    • Coordinate gradient descent
    • Non-smooth functions and Subgradient
    • Projected gradient descent and Proximal gradient methods
  • Alternating direction method of multipliers (ADMM)
  • Semidefinite programming
Combinatorial Optimization
  • Integer programming
  • Exact algorithms
    • Branch and bound, Branch and price, Branch and cut, etc.
    • Column generation
    • Dynamic programming (sometimes pseudo-polynomial)
    • Cutting-Planes
  • Approximation algorithms
    • Randomized algorithms
    • LP relaxition and integrality gap
    • Problem-specific algorithms
  • Heuristic algorithms (meta-heuristics)
    • Genetic algorithms
    • Simmulated annealing
    • Tabu search
    • Others: Ant colony optimization, particle swarm optimization, Metropolis heuristic, etc.
  • Backdoors to combinatorial optimization
  • Classic problem: Knapsack problem and its variations
    • 0-1 Knapsack problem
      • Common misconceptions about its hardness
        • In what sense it is NP-complete?
        • Is the pseudo-polynomial algorithm good enough for common real problems?
        • Indirect effect of number of items
      • Approximation algorithms and accelerations
    • Multiple-choice Knapsack problem
    • Multi-dimensional and Multiple-choice Knapsack problem
    • 2D Knapsack problem
Statistics in data mining and machine learning
  • Distributions
  • Stochastic processes
  • Significance testing
  • Common misconceptions of p-value
  • Statistical power
  • Frequentist vs. Bayesian
  • Computer science and statistics
  • Autocorrelation and spatial statistics
Matrix and Numerical Algorithms
  • Derivatives of Matrices
  • Matrix factorizations (e.g., QR, SVD) and numerical stability
  • Numerical stability of gradient checking
  • Tricks to improve numerical stability
  • Arbitrary precision arithmetic
  • Solving linear systems, Accelerations
  • Matrix operations and positive (semi)definite matrix
  • Hadamard operations and positive (semi)definite matrix
  • Matrix cookbook
Interesting math problems
  • What is the value of 0.99999999...?
  • What is the value of 0^0 (zero raise to the power of zero)?
  • Under construction