p7cs.CC

Category

cs.CC

212 papers

A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length

Daniel M. Kane

1210.1280

Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity

Amit Daniely, Roy Frostig, Yoram Singer

1602.05897

New lower bounds for the rank of matrix multiplication

J. M. Landsberg

1206.1530

The Illusion of State in State-Space Models

William Merrill, Jackson Petty, Ashish Sabharwal

2404.08819

The Complexity of Computing the Optimal Composition of Differential Privacy

Jack Murtagh, Salil Vadhan

1507.03113

Communication-Optimal Convolutional Neural Nets

James Demmel, Grace Dinh

1802.06905

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

Vitaly Feldman, David Xiao

1402.6278

Learning from Untrusted Data

Moses Charikar, Jacob Steinhardt, Gregory Valiant

1611.02315

Recurrent Neural Networks as Weighted Language Recognizers

Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight

1711.05408

Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard

Jonathan Ullman

1207.6945

Reliably Learning the ReLU in Polynomial Time

Surbhi Goel, Varun Kanade, Adam Klivans, Justin Thaler

1611.10258

From average case complexity to improper learning complexity

Amit Daniely, Nati Linial, Shai Shalev-Shwartz

1311.2272

Convex Optimization: Algorithms and Complexity

Sébastien Bubeck

1405.4980

Consensus Halving is PPA-Complete

Aris Filos-Ratsikas, Paul W. Goldberg

1711.04503

On the Complexity of Learning Neural Networks

Le Song, Santosh Vempala, John Wilmes, Bo Xie

1707.04615

Preventing False Discovery in Interactive Data Analysis is Hard

Moritz Hardt, Jonathan Ullman

1408.1655

Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing

Alexandr Andoni, Ilya Razenshteyn

1507.04299

An optimal randomized incremental gradient method

Guanghui Lan, Yi Zhou

1507.02000

Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

Prasad Raghavendra, Tselil Schramm

1507.05136

Relative Error Tensor Low Rank Approximation

Zhao Song, David P. Woodruff, Peilin Zhong

1704.08246

Interactive Privacy via the Median Mechanism

Aaron Roth, Tim Roughgarden

0911.1813

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

1512.02337

Fairness Through Computationally-Bounded Awareness

Michael P. Kim, Omer Reingold, Guy N. Rothblum

1803.03239

Non-convex Finite-Sum Optimization Via SCSG Methods

Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan

1706.09156

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

1604.03084

A Parallel Approximation Algorithm for Positive Semidefinite Programming

Rahul Jain, Penghui Yao

1104.2502

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, Avi Wigderson

1503.06447

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Yash Deshpande, Andrea Montanari

1502.06590

Sum-of-Squares Lower Bounds for Sparse PCA

Tengyu Ma, Avi Wigderson

1507.06370

Sum of Squares Lower Bounds from Pairwise Independence

Boaz Barak, Siu On Chan, Pravesh Kothari

1501.00734

SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin

1507.05230

Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

1201.1214

Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou

1205.4484

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou

1110.1360

Non-commutative Edmonds' problem and matrix semi-invariants

Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

1508.00690

Operator scaling: theory and applications

Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson

1511.03730

Optimal Algorithms for Distributed Optimization

César A. Uribe, Soomin Lee, Alexander Gasnikov, Angelia Nedić

1712.00232

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

Jacob Steinhardt, Moses Charikar, Gregory Valiant

1703.04940

List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1711.07211

The power of sum-of-squares for detecting hidden structures

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

1710.05017

The Complexity of Constrained Min-Max Optimization

Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis

2009.09623

Tree Polymatrix Games are PPAD-hard

Argyrios Deligkas, John Fearnley, Rahul Savani

2002.12119

A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting

Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

2003.11974

Consensus-Halving: Does It Ever Get Easier?

Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

2002.11437

On the Geometry of Differential Privacy

Moritz Hardt, Kunal Talwar

0907.3754

Understanding Deep Neural Networks with Rectified Linear Units

Raman Arora, Amitabh Basu, Poorya Mianjy, Anirbit Mukherjee

1611.01491

On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem

Mika Göös, Pritish Kamath, Katerina Sotiraki, Manolis Zampetakis

1912.04467

Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents

Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender

2007.15125

Settling the complexity of computing approximate two-player Nash equilibria

Aviad Rubinstein

1606.04550

The Classes PPA-$k$: Existence from Arguments Modulo $k$

Alexandros Hollender

1912.03729

Hardness Results for Consensus-Halving

Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

1609.05136

The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

2011.01929

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash

Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein

1504.02411

The Hairy Ball Problem is PPAD-Complete

Paul W. Goldberg, Alexandros Hollender

1902.07657

Inapproximability of NP-Complete Variants of Nash Equilibrium

Per Austrin, Mark Braverman, Eden Chlamtac

1104.3760

PPP-Completeness with Connections to Cryptography

Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis

1808.06407

The Complexity of Non-Monotone Markets

Xi Chen, Dimitris Paparas, Mihalis Yannakakis

1211.4918

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Aris Filos-Ratsikas, Paul W. Goldberg

1805.12559

Unique End of Potential Line

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

1811.03841

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games

Xi Chen, Yu Cheng, Bo Tang

1511.00785

The Hardness of Approximation of Euclidean k-means

Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop

1502.03316

Two-message quantum interactive proofs are in PSPACE

Rahul Jain, Sarvagya Upadhyay, John Watrous

0905.1300

Quantum walk based search algorithms

Miklos Santha

0808.0059

Fairness Through Awareness

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Rich Zemel

1104.3913

Lower bounds on the size of semidefinite programming relaxations

James R. Lee, Prasad Raghavendra, David Steurer

1411.6317

A Converse to Banach's Fixed Point Theorem and its CLS Completeness

Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis

1702.07339

AM with Multiple Merlins

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

1401.6848

CLS: New Problems and Completeness

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

1702.06017

ARRIVAL: Next Stop in CLS

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad, Veronika Slívová

1802.07702

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

1801.02602

Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

1608.06580

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz

Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang

1710.08602

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1611.03473

Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, David Steurer

1104.4680

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Venkatesan Guruswami, Ali Kemal Sinop

1104.4746

Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

1601.06319

Generalized Wong sequences and their applications to Edmonds' problems

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

1307.6429

Constructive noncommutative rank computation is in deterministic polynomial time

Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

1512.03531

Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Anna R. Karlin, Claire Mathieu, C. Thach Nguyen

1007.1283

Making the long code shorter, with applications to the Unique Games Conjecture

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer

1111.0405

Spectral Algorithms for Unique Games

Alexandra Kolla

1102.2300

Reductions Between Expansion Problems

Prasad Raghavendra, David Steurer, Madhur Tulsiani

1011.2586

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Göös, Aviad Rubinstein

1805.06387

Tensor principal component analysis via sum-of-squares proofs

Samuel B. Hopkins, Jonathan Shi, David Steurer

1507.03269

Sum-of-squares proofs and the quest toward optimal algorithms

Boaz Barak, David Steurer

1404.5236

Trading Determinism for Time in Space Bounded Computations

Vivek Anand T Kallampally, Raghunath Tewari

1606.04649

Constant Inapproximability for PPA

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

2201.10011

Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

1406.6625

The Matching Problem in General Graphs is in Quasi-NC

Ola Svensson, Jakub Tarnawski

1704.01929

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Cong Fang, Zhouchen Lin, Tong Zhang

1902.00247

Learning Geometric Concepts with Nasty Noise

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1707.01242

Polynomial degree bounds for matrix semi-invariants

Harm Derksen, Visu Makam

1512.03393

Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh B. Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

1703.07521

Pseudorandomness via the discrete Fourier transform

Parikshit Gopalan, Daniel Kane, Raghu Meka

1506.04350

Exact tensor completion with sum-of-squares

Aaron Potechin, David Steurer

1702.06237

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

0907.0774

Approximating Continuous Functions by ReLU Nets of Minimal Width

Boris Hanin, Mark Sellke

1710.11278

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Michael A. Forbes, Amir Shpilka

1209.2408

Adversarial examples from computational constraints

Sébastien Bubeck, Eric Price, Ilya Razenshteyn

1805.10204

Approximability and proof complexity

Ryan O'Donnell, Yuan Zhou

1211.1958

Information-theoretic thresholds for community detection in sparse networks

Jess Banks, Cristopher Moore

1601.02658

Sum of squares lower bounds for refuting any CSP

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer

1701.04521

Query-to-Communication Lifting for BPP

Mika Göös, Toniann Pitassi, Thomas Watson

1703.07666

Efficient Algorithms and Lower Bounds for Robust Linear Regression

Ilias Diakonikolas, Weihao Kong, Alistair Stewart

1806.00040

Minimizing Communication in Linear Algebra

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

0905.2485

Gaussian Noise Sensitivity and BosonSampling

Gil Kalai, Guy Kindler

1409.3093

On the Bit Complexity of Sum-of-Squares Proofs

Prasad Raghavendra, Benjamin Weitz

1702.05139

Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information

Peng Xu, Fred Roosta, Michael W. Mahoney

1708.07164

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Pasin Manurangsi

1611.05991

Communication lower bounds and optimal algorithms for programs that reference arrays -- Part 1

Michael Christ, James Demmel, Nicholas Knight, Thomas Scanlon, Katherine Yelick

1308.0068

Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap

Emmanuel Abbe, Colin Sandon

1512.09080

New algorithms and lower bounds for monotonicity testing

Xi Chen, Rocco A. Servedio, Li-Yang Tan

1412.5655

The Communication Complexity of Local Search

Yakov Babichenko, Shahar Dobzinski, Noam Nisan

1804.02676

Analysis of Boolean Functions

Li-Yang Tan

1205.0314

On vanishing of Kronecker coefficients

Christian Ikenmeyer, Ketan D. Mulmuley, Michael Walter

1507.02955

Algorithms and Hardness for Subspace Approximation

Amit Deshpande, Kasturi Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi

0912.1403

An average-case depth hierarchy theorem for Boolean circuits

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

1504.03398

What Can We Learn Privately?

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith

0803.0924

Lower bounds in differential privacy

Anindya De

1107.2183

Pure-Circuit: Tight Inapproximability for PPAD

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

2209.15149

Graph Expansion and Communication Costs of Fast Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

1109.1693

Communication is bounded by root of rank

Shachar Lovett

1306.1877

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Michael A. Forbes, Amir Shpilka

1303.0084

Inequalities and tail bounds for elementary symmetric polynomial with applications

Parikshit Gopalan, Amir Yehudayoff

1402.3543

Estimating operator norms using covering nets

Fernando G. S. L. Brandao, Aram W. Harrow

1509.05065

On the Power of Unambiguity in Logspace

Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran

1001.2034

Nuclear Norm of Higher-Order Tensors

Shmuel Friedland, Lek-Heng Lim

1410.6072

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Adrien Taylor, Francis Bach

1902.00947

Quasi-polynomial Hitting-set for Set-depth-Delta Formulas

Manindra Agrawal, Chandan Saha, Nitin Saxena

1209.2333

Integer factoring and modular square roots

Emil Jeřábek

1207.5220

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis

1909.03210

A General Characterization of the Statistical Query Complexity

Vitaly Feldman

1608.02198

Saturated Transformers are Constant-Depth Threshold Circuits

William Merrill, Ashish Sabharwal, Noah A. Smith

2106.16213

The Parallelism Tradeoff: Limitations of Log-Precision Transformers

William Merrill, Ashish Sabharwal

2207.00729

Community Detection and Stochastic Block Models

Emmanuel Abbe

1703.10146

The Computational Complexity of Random Serial Dictatorship

Haris Aziz, Felix Brandt, Markus Brill

1304.3169

Strongly Refuting Random CSPs Below the Spectral Threshold

Prasad Raghavendra, Satish Rao, Tselil Schramm

1605.00058

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models

Jan van den Brand, Zhao Song, Tianyi Zhou

2304.02207

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

1004.5080

The Rainbow at the End of the Line --- A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein

1608.01921

Geometric Complexity Theory V: Efficient algorithms for Noether Normalization

Ketan D. Mulmuley

1209.5993

The Complexity of Finding Fair Independent Sets in Cycles

Ishay Haviv

2011.01770

Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size

V. Arvind, Partha Mukhopadhyay

0804.0957

Fast Attention Requires Bounded Entries

Josh Alman, Zhao Song

2302.13214

Better Pseudorandom Generators from Milder Pseudorandom Restrictions

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

1210.0049

Almost Optimal Pseudorandom Generators for Spherical Caps

Pravesh Kothari, Raghu Meka

1411.6299

Complexity theoretic limitations on learning DNF's

Amit Daniely, Shai Shalev-Shwatz

1404.3378

Hypercontractive inequalities via SOS, and the Frankl--Rödl graph

Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou

1212.5324

On QMA Protocols with Two Short Quantum Proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

1108.4306

Trading GRH for algebra: algorithms for factoring polynomials and related structures

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

0811.3165

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

1911.05416

Bounded Independence Fools Halfspaces

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

0902.3757

Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1209.2184

Certifying the restricted isometry property is hard

Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin

1204.1580

Can Adversarially Robust Learning Leverage Computational Hardness?

Saeed Mahloujifar, Mohammad Mahmoody

1810.01407

Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3177

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

1610.02704

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel, Guus Regts

1607.01167

Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Ali Civril, Malik Magdon-Ismail

1006.4349

The Densest k-Subhypergraph Problem

Eden Chlamtáč, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca

1605.04284

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Yiding Hao, Dana Angluin, Robert Frank

2204.06618

Membership in moment polytopes is in NP and coNP

Peter Bürgisser, Matthias Christandl, Ketan D. Mulmuley, Michael Walter

1511.03675

Computational Complexity of the $α$-Ham-Sandwich Problem

Man-Kwun Chiu, Aruni Choudhary, Wolfgang Mulzer

2003.09266

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers

Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Yufa Zhou

2410.09375

InstaHide: Instance-hiding Schemes for Private Distributed Learning

Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora

2010.02772

On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

Cristobal Guzman, Arkadi Nemirovski

1307.5001

Pizza Sharing is PPA-hard

Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

2012.14236

The Average Sensitivity of Bounded-Depth Formulas

Benjamin Rossman

1508.07677

Testing Shape Restrictions of Discrete Distributions

Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld

1507.03558

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Oded Regev

2401.03703

Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3173

On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

1311.4821

The Computational Complexity of Duality

Shmuel Friedland, Lek-Heng Lim

1601.07629

Faster all-pairs shortest paths via circuit complexity

Ryan Williams

1312.6680

The Complexity of Pacing for Second-Price Auctions

Xi Chen, Christian Kroer, Rachitesh Kumar

2103.13969

Boson-Sampling in the light of sample complexity

C. Gogolin, M. Kliesch, L. Aolita, J. Eisert

1306.3995

BQP and the Polynomial Hierarchy

Scott Aaronson

0910.4698

A Linear-Optical Proof that the Permanent is #P-Hard

Scott Aaronson

1109.1674

Approximation Limits of Linear Programs (Beyond Hierarchies)

Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer

1204.0957

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song

2412.06148

A Refined Laser Method and Faster Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

2010.05846

Statistical Physics of Hard Optimization Problems

Lenka Zdeborová

0806.4112

Barriers for fast matrix multiplication from irreversibility

Matthias Christandl, Péter Vrana, Jeroen Zuiddam

1812.06952

Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

Saeed Ghadimi, Guanghui Lan

1309.5549

A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

0909.4727

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf

1111.0837

Further limitations of the known approaches for matrix multiplication

Josh Alman, Virginia Vassilevska Williams

1712.07246

Provable limitations of deep learning

Emmanuel Abbe, Colin Sandon

1812.06369

Computational Feasibility of Clustering under Clusterability Assumptions

Shai Ben-David

1501.00437

Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacy

Zhiqi Bu, Jialin Mao, Shiyun Xu

2205.10683

On the Hardness of Entropy Minimization and Related Problems

Mladen Kovačević, Ivan Stanojević, Vojin Šenk

1207.1238

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

Daniel M. Kane, Ryan Williams

1511.07860

Circuit Complexity Bounds for Visual Autoregressive Model

Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song

2501.04299

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

1810.08671

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$

Subhash A. Khot, Nisheeth K. Vishnoi

1305.4581

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Mingda Wan

2412.18040

Algorithms and Hardness for Linear Algebra on Geometric Graphs

Josh Alman, Timothy Chu, Aaron Schild, Zhao Song

2011.02466

Computing the Independence Polynomial: from the Tree Threshold down to the Roots

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

1608.02282

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang

2501.06444

PonderNet: Learning to Ponder

Andrea Banino, Jan Balaguer, Charles Blundell

2107.05407

The Computational Complexity of Training ReLU(s)

Pasin Manurangsi, Daniel Reichman

1810.04207

Planar Graph Perfect Matching is in NC

Nima Anari, Vijay V. Vazirani

1709.07822

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

1708.02222

The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure

Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody

1809.03063

Hidden cliques and the certification of the restricted isometry property

Pascal Koiran, Anastasios Zouzias

1211.0665

Computational Lower Bounds for Sparse PCA

Quentin Berthet, Philippe Rigollet

1304.0828

How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation

Josh Alman, Zhao Song

2310.04064

Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng

1010.2921

On the Complexity of Fair House Allocation

Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong

2106.06925

Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation

Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian

0709.1667

Entropy, Optimization and Counting

Mohit Singh, Nisheeth K. Vishnoi

1304.8108

Matching is as Easy as the Decision Problem, in the NC Model

Nima Anari, Vijay V. Vazirani

1901.10387