A Simple Model to Generate Hard Satisfiable Instances

Sep 12, 2005

Ke Xu, Frederic Boussemart, Fred Hemery, Christophe Lecoutre

Sep 12, 2005

Ke Xu, Frederic Boussemart, Fred Hemery, Christophe Lecoutre

* Proc. of 19th IJCAI, pp.337-342, Edinburgh, Scotland, 2005. For more information, please click http://www.nlsde.buaa.edu.cn/~kexu/papers/ijcai05-abstract.htm

**Click to Read Paper and Get Code**

* Under review. Supplementary material included in the paper as well

**Click to Read Paper and Get Code**

Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances

Nov 11, 2003

Ke Xu, Wei Li

This paper first analyzes the resolution complexity of two random CSP models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into CNF formulas, it is proved that almost all instances of Model RB/RD have no tree-like resolution proofs of less than exponential size. Thus, we not only introduce new families of CNF formulas hard for resolution, which is a central task of Proof-Complexity theory, but also propose models with both many hard instances and exact phase transitions. Then, the implications of such models are addressed. It is shown both theoretically and experimentally that an application of Model RB/RD might be in the generation of hard satisfiable instances, which is not only of practical importance but also related to some open problems in cryptography such as generating one-way functions. Subsequently, a further theoretical support for the generation method is shown by establishing exponential lower bounds on the complexity of solving random satisfiable and forced satisfiable instances of RB/RD near the threshold. Finally, conclusions are presented, as well as a detailed comparison of Model RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively, exhibit three different kinds of phase transition behavior in NP-complete problems.
Nov 11, 2003

Ke Xu, Wei Li

* 19 pages, corrected mistakes in Theorems 5 and 6

**Click to Read Paper and Get Code**

On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs

Apr 07, 2002

Ke Xu, Wei Li

Apr 07, 2002

Ke Xu, Wei Li

* Discrete Applied Mathematics, 136(2004):125-149.

* 22 pages, the final version to appear in Discrete Applied Mathematics

**Click to Read Paper and Get Code**

* The SAT Phase Transition. Science in China, Series E, 42(5):494-501, 1999

* 13 pages, 3 figures

**Click to Read Paper and Get Code**

An Average Analysis of Backtracking on Random Constraint Satisfaction Problems

May 09, 2000

Ke Xu, Wei Li

In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. It is proved that Model GB in which each constraint is easy to satisfy exhibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) as the number of variables approaches infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1)) of the average number of nodes in a search tree used by the backtracking algorithm on Model GB is also presented. It is shown that the average number of nodes required for finding all solutions or proving that no solution exists grows exponentially with the number of variables. So this model might be an interesting distribution for studying the nature of hard instances and evaluating the performance of CSP algorithms. In addition, we further investigate the behaviour of the average number of nodes as r (the ratio of constraints to variables) varies. The results indicate that as r increases, random CSP instances get easier and easier to solve, and the base for the average number of nodes that is exponential in r tends to 1 as r approaches infinity. Therefore, although the average number of nodes used by the backtracking algorithm on random CSP is exponential, many CSP instances will be very easy to solve when r is sufficiently large.
May 09, 2000

Ke Xu, Wei Li

* Annals of Mathematics and Artificial Intelligence, 33:21-37, 2001.

* 20 pages, submitted to Annals of Mathematics and Artificial Intelligence

**Click to Read Paper and Get Code**

In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.

* Journal of Artificial Intelligence Research, Vol 12, (2000), 93-103.

* See http://www.jair.org/ for any accompanying files

* Journal of Artificial Intelligence Research, Vol 12, (2000), 93-103.

* See http://www.jair.org/ for any accompanying files

**Click to Read Paper and Get Code**
Robust Ordinal Embedding from Contaminated Relative Comparisons

Dec 05, 2018

Ke Ma, Qianqian Xu, Xiaochun Cao

Dec 05, 2018

Ke Ma, Qianqian Xu, Xiaochun Cao

* Accepted by AAAI 2019

**Click to Read Paper and Get Code**

Learning a Repression Network for Precise Vehicle Search

Aug 08, 2017

Qiantong Xu, Ke Yan, Yonghong Tian

The growing explosion in the use of surveillance cameras in public security highlights the importance of vehicle search from large-scale image databases. Precise vehicle search, aiming at finding out all instances for a given query vehicle image, is a challenging task as different vehicles will look very similar to each other if they share same visual attributes. To address this problem, we propose the Repression Network (RepNet), a novel multi-task learning framework, to learn discriminative features for each vehicle image from both coarse-grained and detailed level simultaneously. Besides, benefited from the satisfactory accuracy of attribute classification, a bucket search method is proposed to reduce the retrieval time while still maintaining competitive performance. We conduct extensive experiments on the revised VehcileID dataset. Experimental results show that our RepNet achieves the state-of-the-art performance and the bucket search method can reduce the retrieval time by about 24 times.
Aug 08, 2017

Qiantong Xu, Ke Yan, Yonghong Tian

**Click to Read Paper and Get Code**

Word Network Topic Model: A Simple but General Solution for Short and Imbalanced Texts

Dec 17, 2014

Yuan Zuo, Jichang Zhao, Ke Xu

Dec 17, 2014

Yuan Zuo, Jichang Zhao, Ke Xu

**Click to Read Paper and Get Code**

Adaptive Mesh Representation and Restoration of Biomedical Images

Jun 27, 2014

Ke Liu, Ming Xu, Zeyun Yu

Jun 27, 2014

Ke Liu, Ming Xu, Zeyun Yu

**Click to Read Paper and Get Code**

Phase Transitions in Knowledge Compilation: an Experimental Study

Jun 03, 2011

Jian Gao, Minghao Yin, Ke Xu

Jun 03, 2011

Jian Gao, Minghao Yin, Ke Xu

**Click to Read Paper and Get Code**

Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

Nov 19, 2008

Liang Li, Tian Liu, Ke Xu

Backtracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any dead-end during a backtracking search, implying that the instance is easy to solve. We prove an exact phase transition of backtrack-free search in some random CSPs, namely in Model RB and in Model RD. This is the first time an exact phase transition of backtrack-free search can be identified on some random CSPs. Our technical results also have interesting implications on the power of greedy algorithms, on the width of random hypergraphs and on the exact satisfiability threshold of random CSPs.
Nov 19, 2008

Liang Li, Tian Liu, Ke Xu

**Click to Read Paper and Get Code**

This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by $r_{cr}$ or $p_{cr}$. For this model, we establish the scaling window $W(n,\delta)=(r_{-}(n,\delta), r_{+}(n,\delta))$ such that the probability of a random instance being satisfiable is greater than $1-\delta$ for $r<r_{-}(n,\delta)$ and is less than $\delta$ for $r>r_{+}(n,\delta)$. Specifically, we obtain the following result $$W(n,\delta)=(r_{cr}-\Theta(\frac{1}{n^{1-\epsilon}\ln n}), \ r_{cr}+\Theta(\frac{1}{n\ln n})),$$ where $0\leq\epsilon<1$ is a constant. A similar result with respect to the other parameter $p$ is also obtained. Since the instances generated by model RB have been shown to be hard at the threshold, this is the first attempt, as far as we know, to analyze the scaling window of such a model with hard instances.

**Click to Read Paper and Get Code**
When to Update the sequential patterns of stream data?

Jan 26, 2003

Qingguo Zheng, Ke Xu, Shilong Ma

Jan 26, 2003

Qingguo Zheng, Ke Xu, Shilong Ma

* 12 pages, 5 figures

**Click to Read Paper and Get Code**

The limit behavior of inductive logic programs has not been explored, but when considering incremental or online inductive learning algorithms which usually run ongoingly, such behavior of the programs should be taken into account. An example is given to show that some inductive learning algorithm may not be correct in the long run if the limit behavior is not considered. An inductive logic program is convergent if given an increasing sequence of example sets, the program produces a corresponding sequence of the Horn logic programs which has the set-theoretic limit, and is limit-correct if the limit of the produced sequence of the Horn logic programs is correct with respect to the limit of the sequence of the example sets. It is shown that the GOLEM system is not limit-correct. Finally, a limit-correct inductive logic system, called the prioritized GOLEM system, is proposed as a solution.

* 9 pages. Welcome any comments to kexu@nlsde.buaa.edu.cn

* 9 pages. Welcome any comments to kexu@nlsde.buaa.edu.cn

**Click to Read Paper and Get Code**
Learning Influence Functions from Incomplete Observations

Nov 07, 2016

Xinran He, Ke Xu, David Kempe, Yan Liu

Nov 07, 2016

Xinran He, Ke Xu, David Kempe, Yan Liu

* Full version of paper "Learning Influence Functions from Incomplete Observations" in NIPS16

**Click to Read Paper and Get Code**

Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bounds on running time for restricted SAT with bounded clause length k (k-SAT) can be classified into three styles: DPLL-like, PPSZ-like and Local Search, with local search algorithms having already been generalized to CSP with bounded constraint arity k (k-CSP). We generalize a DPLL-like algorithm in its simplest form and a PPSZ-like algorithm from k-SAT to k-CSP. As far as we know, this is the first attempt to use PPSZ-like strategy to solve k-CSP, and before little work has been focused on the DPLL-like or PPSZ-like strategies for k-CSP.

**Click to Read Paper and Get Code**
Visualizing and Understanding the Effectiveness of BERT

Aug 15, 2019

Yaru Hao, Li Dong, Furu Wei, Ke Xu

Aug 15, 2019

Yaru Hao, Li Dong, Furu Wei, Ke Xu

* Accepted by EMNLP-19

**Click to Read Paper and Get Code**

Less but Better: Generalization Enhancement of Ordinal Embedding via Distributional Margin

Dec 05, 2018

Ke Ma, Qianqian Xu, Zhiyong Yang, Xiaochun Cao

Dec 05, 2018

Ke Ma, Qianqian Xu, Zhiyong Yang, Xiaochun Cao

* Accepted by AAAI 2019

**Click to Read Paper and Get Code**