 ### Yiqun Xie

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

### Useful Resources (under construction)

##### 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:
• 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
• Descent direction
• Step size
• Optimal first-order approaches
• 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)?