Yiqun Xie

Assistant Professor
Geospatial Information Science
University of Maryland, College Park

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

Email: xie@umd.edu

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)

Optimization

• 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)
• LASSO
• 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