| References: [1] Aaronson, S., Impagliazzo, R., Moshkovitz, D. (2014). AM with multiple Merlins. In: Computational Complexity (CCC), 2014 IEEE 29th Conference on, p. 44–55, June 2014.
[2] Alon, N.,de la Vega, W. F. Kannan, R. Karpinski, M.(2003). Random sampling and approximation of max-CSPs. J. Comput. Syst. Sci., 67(2) 212–243, September 2003.
[3] Arora, S. Karger, D. Karpinski, M. (1995). Polynomial time approximation schemes for
dense instances of NP-hard problems. In: Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC’95, p. 284–293, New York, NY, USA, 1995. ACM.
[4] Barak, B., Hardt, M., Holenstein, T., Steurer. D.(2011). Subsampling mathematical relaxations and average-case complexity. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’11, p. 512–531. SIAM, 2011.
[5] Barak, B., Rao, A., Raz, R., Rosen, R. (2009) . Shaltiel. RStrong parallel repetition theorem for free projection games. In: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM’09, p.352–365, Berlin, Heidelberg, 2009. Springer-Verlag.
[6] Bellare, M., Goldreich, O., Sudan, M. (1998). Free bits, PCPs, and nonapproximability – towards tight results. SIAM Journal on Computing, 27(3)804–915, 1998.
[7] Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U. Vijayaraghavan, A. (2010).Detecting high log-densities: An O(n1/4) approximation for densest k-subgraph. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC’10, p. 201–210, New York, NY, USA, 2010. ACM.
[8] Brandao, F. G.S.L. , Harrow, A. W.(2013). Quantum de finetti theorems under local measurements with applications. In: Proceedings of the Forty-fifth Annual ACM Symposium Theory of Computing, STOC’13, p. 861–870, New York, NY, USA, 2013. ACM.
[9] Braverman, M., Ko, Y. K., Weinstein, O. (2015). Approximating the best nash equilibrium in no(log n)-time breaks the exponential time hypothesis. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’15, p.970–982. SIAM.
[10] Charikar, M. Hajiaghayi, M., Karloff, H. (2009). Improved approximation algorithms for label cover problems. In ESA, p.23–34.
[11] Feige, U., D. Peleg, D., Kortsarz, G. (2001). The dense k-subgraph problem. Algorithmica, 29(3) 410–421.
[12] Håstad. J. (2001). Some optimal inapproximability results. Journal of the ACM, 48(4):798–859.
[13] Khot, S. (2004). Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS’04, p. 136–145, Washington, DC, USA, 2004. IEEE Computer Society.
[14] Manurangsi, P., Moshkovitz, D (2013). Improved approximation algorithms for projection games. In Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 683–694. Springer Berlin Heidelberg.
[15] Moshkovitz, D. (2012). The projection games conjecture and the NP-hardness of ln napproximating set-cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques – 15th International Workshop, APPROX 2012, volume 7408, p. 276–287.
[16] Raz, R (1998). A parallel repetition theorem. SIAM Journal on Computing, volume 27, p. 763–803.
[17] Shaltiel, R. (2013).Derandomized parallel repetition theorems for free games. Comput. Complex., 22(3)565–594 .
[18] Suzuki, A., Tokuyama, T. (2005). . Dense subgraph problems with output-density conditions. In Xiaotie Deng and Ding-Zhu Du, editors, Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, p. 266–276. Springer Berlin Heidelberg, 2005. |
Author Rights 
