Ali Çivril


İstinye Üniversitesi, Bilgisayar Mühendisliği Bölümü’nde doçent olarak görev yapmaktayım.

CV-İng
CV-Tr


Araştırma Alanları:


En geniş manasıyla kuramsal bilgisayar bilimiyle ilgileniyor, ve şu an hesapsal karmaşıklığın şema-kuramsal yorumu ve yaklaştırma algoritmaları üzerine araştırma yapıyorum.

Google Scholar sayfası



Yay
ınlanmamış Çalışmalar:

A. Çivril. Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over C, R, and Z, 2021. pdf

- A. Çivril. Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP, 2021. pdf

Bu, hesapsal karmaşıklığa şema-kuramsal yaklaşımı ortaya koyan makale olup P ve NP problemini çözmektedir. Bu makalede bir embriyo halinde ortaya konan teori, uzun vadede alanı kategori-kuramsal ve cebirsel-geometrik yöntemlerle matematiğin ana gövdesine eklemlemeyi hedeflemektedir. Özellikle konuya yabancı olanlar için daha somut olmak adına, makalenin katkıları şu şekilde sıralanabilir:


0) Hesapsal problemlerin kategorisinde TRIVIAL problemi tanımlıyor (alan için 0’ın keşfi), ve bu kategoriden şemaların kategorisine anlamlı bir fonktör tanımlıyor.
1) Algoritma denilen şeyi eldeki probleme karşılık gelen şemayı, şemaların kategorisindeki son objeye indirgeyen bir geometrik büzme prosedürü olarak ele alıyor.
2) Bir problemin zaman karmaşıklığını ona karşılık gelen şemanın belli bir alt-şemasının geometrisiyle ilişkilendiriyor.
3) 3-SAT’a karşılık gelen şemanın bağlantılı bir alt-şemasının geometrini ele alarak P’yi NP’den ayırıyor.

- A. Çivril. Dual Growth with Variable Rates: An Improved Integrality Gap for Steiner Tree, 2019. pdf


Yayınlanmış Bazı Çalışmalar:

- A. Çivril. Approximation of Steiner Forest via the Bidirected Cut Relaxation, Journal of Combinatorial Optimization, 38(4): 1196-1212, 2019. pdf

- A. Çivril. Sparse Approximation is Provably Hard under Coherent Dictionaries, Journal of Computer and System Sciences, 84(1): 32-43, 2017. pdf

- A. Çivril. Column Subset Selection Problem is UG-hard, Journal of Computer and System Sciences, 80(4): 849-859, 2014. pdf

Not: Yaroslav Shitov tarafından çok daha basit bir NP-hardness ispatı var. Burada

- A. Çivril. A Note on the Hardness of Sparse Approximation, Information Processing Letters, 113(14-16):543-545, 2013. pdf

- A. Çivril and M. Magdon-Ismail. Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix, Algorithmica, 65(1): 159-176, 2013. pdf

- A. Çivril and M. Magdon-Ismail. Column Subset Selection via Sparse Approximation of SVD. Theoretical Computer Science, 421:1-14, 2012. pdf

- A. Çivril and M. Magdon-Ismail. On Selecting A Maximum Volume Sub-matrix of a Matrix and Related Problems. Theoretical Computer Science, 410(47-49):4801-4811, 2009. pdf

- Y. Koren and A. Çivril. Binary Stress Model for graph Drawing. Graph Drawing 2008, 193-205. pdf

- A. Çivril, M. Magdon-Ismail and E. Bocek-Rivele. SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding. Graph Drawing 2006, 30-41. pdf