我與計算機科學漫長而愉快的互動可以追溯到壹年半以前，那時我剛開始學習編程。在上大學之前，我學習計算機科學的主要動機是參加計算機奧林匹克競賽。我的成績連續多年獲得羅馬尼亞全國奧林匹克壹等獎，並獲得國際獎項(其中兩枚金牌1銀牌IOI)。
在大學裏，我自然吸引了理論計算機科學的研究。我在這個領域工作了三年，在埃裏克·德梅因的指導下。下面，我將觸及的貢獻，在此期間，我作出了壹些。我的主要研究興趣與復雜性、具體計算模型(下限)以及高級數據結構和算法有關。
理論計算機科學的研究集中在我的博士項目上。讀完博士後，我可能想在學術界謀得壹個職位。在這裏，我充滿了活力，我在教學方面的良好經驗，包括壹門新的研究生課程，在麻省理工學院擔任助教。
混凝土的復雜性。我對動態cellprobe復雜性最廣泛的貢獻是通過壹系列論文發表在SICOMP、STOC、SODA和ICALP上。細胞檢測模型是壹個強大的異構計算模型，用於分析靜態或動態數據結構問題。對於動力學問題，下界已經被證明使用了Fredman和Saks計時技術，這可以追溯到STOC的89。從這個文件中的壹個下界(LG N/LG LG N)導出，其中N是數字問題的表示。雖然疾風驟雨般的作品顯示了各種問題的類似下限，但沒有更高的下限來證明在15中，這個極限被確定為論文和調查開放領域問題的中心。
我們與西康普、STOC和蘇達艾力克合作？Demaine出現在文件中，用display的下界(LG N)來維持部分動態連接，打破了這個長期存在的障礙。我們的組合體現了民俗學的最優解(增強型二叉樹)，是典型的動態計算。盡管有密集的學習，即使在較弱的代數模型中也有嚴格的限制。我們的約束動態連接的證明包括著名的Sleator和Tarjan的動態樹的動態圖算法的最優性。
我在這些問題上的工作被公認為2004年最佳本科生研究計算機研究協會獎。有趣的是，我們最初的做法似乎是壹種完全不同的計時技術。但是在科裏納和塔尼特壹起工作？a(帕特拉？立方米)，我們發現了壹個微妙的變化，計時技術，這是相當。利用這種更好的理解，我們提供了壹個最佳下限探針模型來解決第壹個公開問題。米爾特森的壹項調查顯示，這幾乎是第二次改善。我們的作品獲得了ICALP最佳學生論文獎。
在最近提交的論文米克爾·托魯普中，我們在靜態細胞探針的復雜性方面取得了突破。到目前為止，基本上有壹個被已知技術證明的時空平衡的靜態數據結構:降低非對稱通信的復雜度。但據了解，這種方法無法證明superconstant的下限是最自然的查詢和壹個機器字的參數設置:O(LG N) bit。此外，通信復雜性無法區分多項式因子的空間，以及最自然的問題，其中有趣的現象發生在多項式域。我們證明了第壹個下限，打破了溝通障礙，不受這些限制。我們的結果的壹個基本意義是第壹多項式與近線性空間(任意空間N1+O(1))之間的距離。我們的邊界給出了對前任搜索的完整理解，這是最基本和最深入的研究問題之壹。壹個驚人的結論是，範？Underboas是著名的準線性空間數據結構，在動態情況下表現最好。另壹個有趣的結論適用於外部存儲器模型:使用基於比較的經典B樹或最佳RAM總是最佳解決方案，而忽略了外部存儲器的好處。
這些結果為許多關於細胞探針復雜性的有趣問題打開了大門，我打算對此進行研究。在動態情況下，可能需要證明多對數的下限(例如，在連續大小範圍查詢中)或N(1)(例如，在有向圖的動態問題中)。在這兩種情況下，這些問題都在上側得到了廣泛的研究，但我們不能希望知道它們進展的下限。在靜態情況下，我們可以要求更高的下限。現在，我們不局限於交流的復雜性。特別是，這將是壹個有趣的證明世界的演示嗎？次元災難？這是保持猜測的壹個至關重要的問題。
雖然我專註於強大的計算模型，如電路和分支規劃，如細胞探針模型分析，我仍然保持積極的興趣。我在細胞探針模型中使用的信息論工具和直覺也將被證明是有用的，在其他情況下，這是很有可能的。舉個例子，阿德勒、德梅因、哈維在《聯袂工作》中出現了，我們用工具從通信的復雜性來分析整個非對稱信道的信息傳遞。這個問題已經得到了廣泛的研究，並且在傳感器網絡中提出了許多協議。我們已經證明了這個問題，其中最著名的解決方案幾乎是用行為下限。
數據結構和算法。我早期的計算機奧林匹克競賽訓練，程序員和參賽者自然讓我對算法產生了強烈的欣賞。盡管我的工作很復雜，但我認為我有壹種本能的模式推理算法。
我最有影響力的壹篇論文發表在SICOMP和FOCS雜誌上，這是壹份關註競爭力的二叉查找樹。著名的動態最優猜測Sleator和Tarjan斷言八字樹是O(1)競爭的。但是對於平凡的O(LG N)卻沒有競爭，這是二十多年來被證明是八字樹或者其他任何二叉查找樹。在德梅因、哈蒙和雅科諾的聯合工作中，我們描述了壹種新的搜索樹可證明為O(LG LG N)競爭。當然，關於這個結果有兩個重要的開放性問題:它是O(1)競爭搜索樹嗎？splay tree O(LG N)有競爭力嗎？
現代數據結構的研究集中在整數搜索這壹重要領域。？下博阿斯遞歸可能是最著名的領域，它的優雅有助於動機的壹般領域。對於前任的問題，算法被證明是緊張我最近的工作米克爾托魯普上面提到的。然而，在壹維動態範圍報告中，結果並非如此。與STOC的mortensen和Pagh壹起工作，我們開發了壹個基本的新遞歸思想，它在查詢方面產生了驚人的指數級改進。適用於二分搜索法路上的特裏？反對的安德·博阿斯使用了更復雜的遞歸路徑(類似於凡·安德的博阿斯搜索本身)。不過算法非常幹凈優雅。
最近對哈希及其應用非常感興趣。我們上面提到的STOC文件需要開發壹個令人驚訝的哈希原始數據結構，使用次線性內存(，沒有實際內存集)，從而為壹組動態範圍報表維護壹個完美的哈希函數。
德梅因、邁耶·AUF·德·海德和帕格的嚴格上下界在我後來的拉丁文論文裏。我們開發中的壹個重要因素是，動態字典同時緊湊地使用漸近最優的空間，該空間以高概率與每次操作的時間固定在壹起。以前的字典只能達到這些要求中的壹個。Balaam和Demaine，我的WADS論文的另壹組使用散列的思想，達到第壹個二次算法的著名的3SUM問題，使用？平行？RAM或外部存儲器模式(位，分別封裝，更大的存儲器頁面)。
有許多有趣的開放式問題是我想研究的。也許最根本的是確定性字典的表示，這是計算隨機性的主要目的之壹。其他有趣的問題包括置換散列族，它在密碼學中也起著重要的作用。在拉美文獻中，如上所述，我們安排了hash函數，它沒有k K- wise大到可以獨立開發壹個有趣的家族，但也有類似的濃度邊界。
我也對算法數論感興趣，在該領域有三個發表的結果。此外，在壹個正在進行的合作研究項目中，我們正在尋找計算平面中原始晶格形狀的問題。幾何數論的交集是壹個激動人心的問題，在數學中有著悠久的歷史，可以追溯到高斯。我們的算法適用於多邊形，速度明顯比以前的方法更準確。R&S科裏納塔爾尼特的壹張紙？a(佩特雷？立方米)中，我們描述了壹種特定三角形的快速算法。我們
用這個來建立算法的排序，選擇查詢的Farey序列，這是第二個速度比枚舉的順序。
教學。我認為做研究是教學不可或缺的壹部分。如果沒有，可以想辦法呈現給別人。這壹發現遠未完成。更重要的是，大量的論證結果是有組織的，研究人員必須與老師分享，因為沒有它，研究人員就無法獲得明確的方向，他的工作是壹項重要的技能。
我早年的經歷和學生來到羅馬尼亞國家奧林匹克競賽，成為巴爾幹奧林匹克科學委員會成員。沒錯，人是有問題的，原始而優雅，同時衡量著從壹個群體中選出最優秀的天才學生的難度。這需要也許是最難以捉摸的技能。老師進入學生頭腦，根據自己的能力，在五個小時內判斷難度。雖然這不是壹項技能，但我不能指望完全掌握它。比賽結果表明，我的提問是高層委員會成員對我貢獻的褒獎。
我最顯著、最愉快的教學經歷，是作為研究生課程助教的Erik Demaine教授的《高級數據結構》。我創建並評分習題集，和四個講座教授。然而，最有趣的方面是從頭到尾與埃裏克壹起工作？創造？這個過程。我們必須決定什麽應該涵蓋廣泛的主題，以及如何最好地呈現每個主題。在這樣壹個古老而多樣化的領域，這是壹項非常具有挑戰性但在智力上有回報的任務。對於那些宣稱對其他大學課程的廣度和壹致性印象深刻的人來說，這尤其令人鼓舞。
結論。我期待著繼續我的博士生研究生涯。這是壹些開放性的問題，激勵著我，我會繼續努力。另外，這件事發生在麻省理工學院，理論小組的成員給了我壹個寶貴的機會，讓我在壹個意想不到的時刻開闊了眼界，從事了很多研究領域的工作。鑒於我的背景，我相信我有能力在這項事業中做出重要貢獻。
通過美國計算機CS專業文檔的分享，相信很多打算申請美國研究生的同學可以參考以上信息，提前做好申請美國研究生的準備和計劃。