Disclaimer: 이 글은 지금 떡밥에서 구체적 예시들을 보면 재미있을것같아서 쓴 글이고, 다른 주장은 전혀 없음.

특히 pure/applied math는 개인의 취향이라고 생각하니까 이런얘기는 하지말아주셈.


밑줄 있는거는 링크가 있는것들임. 강조는 별 이유없이 내가 하고싶은거 함.

여러 결과는 TCSstackexchange의 이글에서 들고오고 내가 논문 좀 뒤적거리면서 좀 더 자세히 정리함.




1. Kelvin problem이라고 n(=3)차원에 단위부피를 가진 거품을 차원을 가득 채우도록 넣으면 거품이 어떻게 생기게 되는지를 묻는 문제가 있음. 

그러면 거품들은 (아마도) 잘 알려진대로 면적을 최소화하도록 어떻게 움직이는데, 그 최종 형태가 어떻게 될거냐는거지. 


FOCS'2008의 결과 Spherical Cubes and Rounding in High Dimensions 에서는 의미있는 결과를 냈는데, 

만약 거품이 Z^d변환에 보존되는 경우 각 거품의 표면적이 O(√d)가 되는 타일링이 있음을 보임. 

이건 volume-1구의 표면적이 대략 √(2πed)라서 상수배 팩터 내에서 optimal이고, 

이전 최적의 결과는 키아스 최재경 교수님이 밝힌 O(d)였다네.


증명도 TCS에서 주로 다루는 게임이론의 2-player game theory와 여기서 중요한 결과인 parallel repetition에서 영감을 받았다고 함.

그 관계도 2007년 complexity theory 학회에서 몇몇 저자+다른사람이 밝힘.




2. 작년 MIP*=RE를 빼먹을수 없지. 이건 아예 논문 제목 자체가 복잡계에서 다루는 대상이 같다는건데 (P=NP처럼), 

대충 두명의 양자적으로 얽혀있지만 서로 교류하지 않는 신에게 상담을 열심히 잘 하면, 계산불가능하다고 알려진 halting problem을 풀 수 있다는 말임.


근데 얘의 중요한 corollary가 뭐냐면, 함수해석학에서 50년 넘게 열린문제로 남아있던 Connes' embedding problem의 답이 false라는거임.

이거때문에 함수해석학 하시는 분들이 작년에 엄청 떠들썩했다고 들었음.


혹시 대체 저런 복잡계랑 함수해석의 문제랑 무슨 관계인가 정말 궁금한 사람은 저자중 하나의 Notices of AMS글 From Operator Algebras to Complexity Theory and Back을 찾아보면 꽤 친절하고 자세히 설명되어 있음. 굉장히 신기함.




3. Complexity Classes as Mathematical Axioms라는 Annals of math논문에서는 

컴퓨터과학에서 참이라고 믿어지는 복잡계 가정 P^#P≠NP를 (axiom처럼 참이라고..) 가정하면 3차원 토폴로지의 어떤 결과를 얻을수 있음을 밝힘.

이건 뭔소린지도 잘 모르겠으니 넘어감 -_-




4. Kakeya conjecture라는 문제가 있음. 대충 R^n에서 임의의 방향으로의 unit line segment를 가지면 이거의 (여러)차원이 n이라는 거.

이거의 finite field 버젼이 있는데, 다음과 같음:

임의의 finite field F에 대해 F^n의 subset 중 임의의 방향으로의 line을 갖는 집합을 생각하면, n에만 관계되는 함수 c(n)이 있어서 그 크기가 최소한 c(n)|F|^n이다.


이 결과는 2008년 On the size of Kakeya sets in finite fields라는 논문에서 풀림. 

TCS에서 주로 쓰는 아이디어를 들고오긴 했는데, 그렇게 말하기 민망할정도로 증명이 짧아서 님들도 그냥 볼 수 있음.

타오가 블로그에 증명을 소개하기도 함. 마치 작년의 Sensitivity conjecture의 증명을 보는듯 -_-


사실 이결과는 c(n)>=1/n!을 보인건데, 바로 그 다음해 다른사람들과의 협업으로 c(n)>=1/2^n을 보임 (이것도 상수배정도로 타이트함).

그 결과는 이링크에서 볼 수 있는데, randomness extractor라는 TCS의 중요한 오브젝트와 다른 몇가지 아이디어를 썼다네.




5. 또 일부 연구자들은 소수가 얼마든지 긴 등차수열을 가진다는 Green-Tao 정리 등과 관련된 Gower norm에 관련된 결과들이 TCS의 여러 아이디어들을 썼다고 생각한다네 (즉 Green-Tao정리가 TCS에서 아이디어를 얻었다는 주장은 아님)

구체적으로는 Green-Tao의 다른 논문의 reference를 보면 CCC/FOCS등의 TCS학회의 논문들이 인용되지. 

그리고 Green-Tao정리의 일반화인 Green-Tao-Ziegler의 정리의 핵심 보조정리인 Dense model theorem의 새로운 증명이 FOCS에 발표되기도 했었다고 함.

이 결과는 Hardcore theorem이라는 CS의 잘 알려진 결과에서 영감을 얻었다고.




쓰다보니 시간도 넘 됐고, 남은 내용들은 조합쪽이 많은듯해서 (잘모르기도 하고) -_- 대충 이름만 정리하면 아래와 같은것들이 있다네

-조합론의 Expander graph

-Invariance principle (Annals의 관련논문) (개인적인 생각으로는 boolean analysis 자체가 TCS에서 발전해서 수학에 종종 쓰이는듯한 느낌)

-여러 분야의 computability/computation theory (Group/graph isomorphism, random generator, 등등)

-symmetric function들의 approximation과 quantum proof (관련 survey)