imported>Etone |
imported>TCSseminar |
| Line 1: |
Line 1: |
| == Problem 1 ==
| | * 这是南京大学理论计算机科学学习小组的主页。 |
| (Erdős-Spencer 1974)
| | * 本学习小组由学生组织，旨在学习理论计算机科学的基础知识。 |
| | * 本学习小组对外开放，欢迎各方向的老师、研究生、以及本科生来参加。 |
|
| |
|
| Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.
| | ==计算复杂性 Computational Complexity== |
| | | |
| This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.
| | :{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" |
| | | |- |
| * Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
| | |bgcolor="#A7C1F2" align="center"|'''时间地点''' |
| * Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>.
| | |bgcolor="#A7C1F2" align="center"|'''Speakers''' |
| | | |bgcolor="#A7C1F2" align="center"|'''Topics''' |
| (This gives a lower bound for the number of weighings required to determine the weights of <math>n</math> coins.)
| | |bgcolor="#A7C1F2" align="center"|'''Readings''' |
| | | |- |
| | | |align="center"| |
| == Problem 2== | | 3:00'''pm''', <font color=red>2018/4/20</font><br> 计算机系楼 <font color = red>224</font> |
| Let <math>\mathcal{H}\subset{[n]\choose k}</math> be a <math>k</math>-uniform hypergraph with vertex set <math>[n]</math>. A '''blocking set''' for <math>\mathcal{H}</math> is a set <math>B\subseteq[n]</math> of vertices such that every hyperedge <math>S\in\mathcal{H}</math> intersects with <math>B</math>, i.e. <math>T\cap S\neq\emptyset</math>.
| | |align="center"| |
| | | 刘雅辉 |
| In particular, when <math>k=2</math>, the hypergraph <math>\mathcal{H}</math> degenerates to a graph, and a blocking set <math>B</math> is now a vertex cover. Indeed, the notion of blocking set is a generalization of vertex cover to hypergraphs. Like the minimum vertex cover problem, finding a minimum blocking set for a hypergraph is NP-hard.
| | || |
| | | :Polynomial Hierarchy. |
| *Prove this: For any hypergraph <math>\mathcal{H}\subset{[n]\choose k}</math> with <math>|\mathcal{H}|=m</math>, there is a blocking set <math>B</math> of size at most <math>\left\lceil\frac{n\ln (m+1)}{k}\right\rceil</math>.
| | || |
| | | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 5 |
| == Problem 3 ==
| | |- |
| | | |align="center"| |
| A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a [http://en.wikipedia.org/wiki/Dominating_set ''dominating set''] if for every <math>v\in V</math>, it holds that <math>v\in D</math> or <math>v</math> is adjacent to a vertex in <math>D</math>. The problem of computing minimum dominating set is NP-hard.
| | 3:00'''pm''', 2018/4/12<br> 计算机系楼 229 |
| | | |align="center"| |
| * Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>.
| | 潘笑吟 |
| | | || |
| * Try to obtain an upper bound for the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one?
| | :Space Complexity. |
| | | || |
| | | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 4 |
| == Problem 4 ==
| | |- |
| Let <math>H(W,F)</math> be a graph and <math>n>|W|</math> be an integer. It is known that for some graph <math>G(V,E)</math> such that <math>|V|=n</math>, <math>|E|=m</math>, <math>G</math> does not contain <math>H</math> as a subgraph. Prove that for <math>k>\frac{n^2\ln n}{m}</math>, there is an edge <math>k</math>-coloring for <math>K_n</math> that <math>K_n</math> contains no monochromatic <math>H</math>.
| | |align="center"| |
| | | 3:00'''pm''', 2018/3/29<br> 计算机系楼 319 |
| Remark: Let <math>E=\binom{V}{2}</math> be the edge set of <math>K_n</math>. "An edge <math>k</math>-coloring for <math>K_n</math>" is a mapping <math>f:E\to[k]</math>.
| | |align="center"| |
| | | 陈海敏<br> |
| == Problem 5 == | | 凤维明 |
| | | || |
| Let <math>G(V,E)</math> be a cycle of length <math>k\cdot n</math> and let <math>V=V_1\cup V_2\cup\dots V_n</math> be a partition of its <math>k\cdot n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality <math>k</math>.
| | :Class coNP and Randomized Computation. |
| For <math>k\ge 11</math> show that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>.
| | || |
| | | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 2, Chapter 7. |
| ==Problem 6 == | | |- |
| (Erdős-Lovász 1975)
| | |align="center"| |
| | | 3:00'''pm''', 2018/3/22<br> 计算机系楼 319 |
| Let <math>\mathcal{H}\subseteq{V\choose k}</math> be a <math>k</math>-uniform <math>k</math>-regular hypergraph, so that for each <math>v\in V</math> there are ''exact'' <math>k</math> many <math>S\in\mathcal{H}</math> having <math>v\in S</math>.
| | |align="center"| |
| | | 凤维明 |
| Use the probabilistic method to prove: For <math>k\ge 10</math>, there is a 2-coloring <math>f:V\rightarrow\{0,1\}</math> such that <math>\mathcal{H}</math> does not contain any monochromatic hyperedge <math>S\in\mathcal{H}</math>.
| | || |
| | :Class NP and Reductions. |
| | || |
| | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 2 |
| | |- |
| | |align="center"| |
| | 3:00'''pm''', 2018/3/15<br> 计算机系楼 319 |
| | |align="center"| |
| | 樊一麟 |
| | || |
| | :Turing Machines and Class P. |
| | || |
| | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 1 |
| | |- |
| | |} |