profile

Yiqun Xie

PhD candidate (started in 2015)
Computer Science and Engineering
University of Minnesota, Twin Cities
Email: xiexx347 at umn.edu

Advisor: Dr. Shashi Shekhar

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